d4-conf-aaai-2010-0376 (d4-conf-aaai-2010-0376)

Given item kinds \(X\), a finite set \(T\) of buyer types with rational masses \(\mu_t\), posted prices \(p\), explicitly listed integral-bundle demand families \(D_t(p)\), and rational per-capita supplies \(q_a\), decide whether nonnegative assignment masses \(\lambda_{tB}\) exist such that \(\sum_{B\in D_t(p)}\lambda_{tB}=\mu_t\) for every \(t\), and \(\sum_{t\in T}\sum_{\substack{B\in D_t(p)\a\in B}}\lambda_{tB}=q_a\) for every \(a\in X\).

Let \(X\) be a finite set of \(m\) item kinds; a bundle \(B\subseteq X\) contains at most one unit of each kind and may be empty.
A society is given by its support: the list of the \(\tau\) buyer types with positive binary rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Input also includes nonnegative binary rational posted prices \(p_a\), nonnegative binary rational per-capita supplies \(q_a\), and explicitly listed nonempty demand families \(D_t(p)\).
These families are promised to be the complete utility-maximizing bundle sets for normalized, monotone, nonnegative integer valuations with quasilinear preferences; all ties are retained. Valuations are not additional input, and no gross-substitutes restriction is imposed.
An assignment may split each type's mass among its demanded integral bundles. Feasibility means that real masses \(\lambda_{tB}\geq0\) satisfy \(\sum_{B\in D_t(p)}\lambda_{tB}=\mu_t\) for every type and \(\sum_{t}\sum_{B\in D_t(p):\,a\in B}\lambda_{tB}=q_a\) for every item kind; all supply must be allocated.
Let \(K=\sum_t|D_t(p)|\) and let \(L\) be the total binary input length. State running times in \(m,\tau,K,L\).

Is this continuous allocation-feasibility problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

The discrete problem of selecting one demanded bundle per buyer so that the selected bundles partition the items is stated to be \(\mathrm{NP}\)-complete in [Dynamic Auction: a Tractable Auction Procedure](https://ojs.aaai.org/index.php/AAAI/article/download/7633/7494).
No result settling exactly the continuous problem above was verified.

Result

The continuous allocation-feasibility problem is in \(\mathrm{P}\). It is decidable exactly in deterministic bit time
\[ \bigl((m+\tau)K+L\bigr)^{O(1)}. \]
Consequently, it can be \(\mathrm{NP}\)-hard under polynomial-time reductions only if \(\mathrm{P}=\mathrm{NP}\).

1. Exact linear-programming formulation

Let \(\mathcal I=\{(t,B):1\leq t\leq\tau,\ B\in D_t(p)\}\). By definition, \(|\mathcal I|=K\).

Introduce one real variable \(\lambda_{tB}\) for each \((t,B)\in\mathcal I\), and impose:

• Nonnegativity: \(\lambda_{tB}\geq0\) for every \((t,B)\in\mathcal I\).
• Type-mass conservation: \(\sum_{B\in D_t(p)}\lambda_{tB}=\mu_t\) for every type \(t\).
• Exact supply allocation: \(\sum_{(t,B)\in\mathcal I:\,a\in B}\lambda_{tB}=q_a\) for every item kind \(a\).

This is a rational linear feasibility problem with \(K\) variables, \(\tau+m\) equality constraints, and \(K\) nonnegativity constraints.

The equivalence with the requested allocation problem holds in both directions. Any allowed allocation supplies values of these variables satisfying all the constraints. Conversely, any feasible vector specifies how much of each type receives each demanded integral bundle; the type equations allocate its entire mass, and the item equations allocate precisely the prescribed supplies.

Thus the linear program expresses exactly the stated problem.

2. Encoding size and running time

Write the equality constraints as \(A\lambda=b\), where \(A\) has \(\tau+m\) rows and \(K\) columns. The column indexed by \((t,B)\) has a \(1\) in type row \(t\), a \(1\) in each item row belonging to \(B\), and zeros elsewhere. Hence every matrix entry belongs to \(\{0,1\}\). The right-hand side is \(b=(\mu_1,\ldots,\mu_\tau,q_1,\ldots,q_m)\).

A dense encoding of this linear program has length
\(\ell_{\mathrm{LP}}=O((m+\tau)K+L)\):
the matrix contributes \(O((m+\tau)K)\) bits, and the rational right-hand side is already part of the input. Constructing this encoding takes polynomial time in \(m,\tau,K,L\).

We apply the standard polynomial-time rational linear-programming theorem: feasibility of an explicitly encoded finite system of rational linear equalities and inequalities can be decided exactly in time polynomial in its total binary encoding length. This theorem concerns real feasibility, including systems whose feasible sets have empty interior; it does not require approximate satisfaction of the equations. Polynomial-time algorithms covering the degenerate feasibility case are given, for example, by [Dadush, Végh, and Zambelli](https://arxiv.org/abs/1611.06427).

All hypotheses hold here: the variables and constraints are explicitly listed, all coefficients are rational, and their total encoding length is polynomially bounded as above. Therefore the running time is
\(\bigl((m+\tau)K+L\bigr)^{O(1)}\).

Under the stated explicit input representation, \(m,\tau,K\) are bounded by the input length, so this is also polynomial in \(L\). No expansion of rational masses into individual buyers is needed.

The valuation promise requires no additional computation: the algorithm uses the supplied complete demand families directly. In fact, the same algorithm works for arbitrary explicitly listed nonempty bundle families.

3. Why discrete hardness does not transfer

The cited paper states the discrete efficient-allocation problem to be \(\mathrm{NP}\)-complete in Proposition 1. Its equilibrium allocation requires each buyer to receive one demanded bundle, with the bundles forming a partition. [Dynamic Auction: a Tractable Auction Procedure](https://ojs.aaai.org/index.php/AAAI/article/download/7633/7494)

Splitting mass changes feasibility, even for demand families satisfying every promise in the question.

Take \(X=\{a,b,c\}\), prices \(p_a=p_b=p_c=1\), and one type of mass \(1\). Define its valuation by \(v(B)=0\) when \(|B|\leq1\), and \(v(B)=2\) when \(|B|\geq2\). This valuation is normalized, monotone, nonnegative, and integer-valued.

The utilities for bundle sizes zero, one, two, and three are respectively \(0,-1,0,-1\). Thus its complete demand family is
\(D(p)=\{\varnothing,\{a,b\},\{a,c\},\{b,c\}\}\).

Set \(q_a=q_b=q_c=1/2\). Assign mass \(1/4\) to each of the four demanded bundles. The masses sum to \(1\), and each item occurs in exactly two of the three pairs, so each receives total allocated mass \(1/2\). The continuous instance is feasible.

Now consider two discrete buyers with this same valuation and one unit of each item. Normalizing by the number of buyers gives precisely the preceding type mass and supplies. Each buyer must choose either the empty bundle or a pair. Any two pairs intersect, so a disjoint selection contains at most one pair and cannot cover all three items. The discrete instance is infeasible.

This verifies that continuous feasibility does not imply discrete feasibility under the valuation promise. The polynomial-time linear-programming argument therefore settles the stated continuous problem independently of the discrete hardness result.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated problem correctly: continuous allocation feasibility is in \(\mathrm{P}\) under the explicit demand-family representation. I found no mathematical errors, unjustified applications of theorems, or gaps requiring clarification.

• Variables and constraints exactly match the task.

The index set \(\mathcal I\) contains precisely one coordinate for each listed type–bundle pair, so it has \(K\) elements. The nonnegativity constraints, type equations, and item equations are exactly the feasibility conditions in USER_TASK.

Both directions of the claimed equivalence hold. An admissible allocation gives a feasible vector, and a feasible vector specifies the permitted splitting of each type’s mass. There is no additional integrality requirement on these masses. Empty bundles are handled correctly: their variables enter the corresponding type equation and no item equation.

• The matrix description and constraint counts are correct.

There are \(K\) variables, \(\tau+m\) equality constraints, and \(K\) nonnegativity constraints. Each column has one entry equal to \(1\) in its type row and entries equal to \(1\) in precisely its bundle’s item rows. All other entries are zero. The right-hand side contains exactly the input masses and supplies.

Redundant equations, zero supplies, and items absent from all demanded bundles do not invalidate this formulation. They are ordinary cases of linear feasibility.

• The encoding and construction bounds are sufficient.

The equality matrix requires \(O((m+\tau)K)\) bits in dense form. The rational right-hand side contributes at most \(O(L)\) bits. Nonnegativity can be encoded as \(K\) variable bounds, without introducing a dense matrix of additional coefficients.

Dimensions and encoding overhead fit the stated bound. In particular, normalization forces \(\tau\geq1\), and nonempty demand families give \(K\geq\tau\). Explicitly listing the item data, types, and demanded bundles ensures that \(m,\tau,K\) are bounded by the input length. Consequently, the claimed running time
\(\bigl((m+\tau)K+L\bigr)^{O(1)}\)
is polynomial in \(L\).

• The linear-programming theorem is stated adequately and applies.

The prover explicitly invokes exact real feasibility for finite, explicitly encoded rational linear systems, with polynomial running time in binary encoding length. Every hypothesis is satisfied here. Neither full dimensionality nor approximate feasibility is assumed.

The cited paper explicitly discusses degenerate feasibility and reduction of general LP feasibility to its maximum-support problems, supporting the citation’s stated purpose. [Dadush, Végh, and Zambelli](https://arxiv.org/html/1611.06427v5)

The valuation promise adds no computational obligation: the task supplies the complete demand families and asks for feasibility on promised inputs.

• The separation example is correct in every stated respect.

The valuation is normalized, monotone, nonnegative, and integer-valued. Subtracting bundle prices gives utilities \(0,-1,0,-1\) for sizes \(0,1,2,3\), respectively. Thus the stated demand family includes all and only maximizing bundles.

Four masses of \(1/4\) sum to \(1\), and each item belongs to exactly two assigned pairs, giving supply \(1/2\). For two discrete buyers, every demanded bundle has size zero or two, and any two pairs intersect. A disjoint selection therefore cannot cover three items. The normalization by two buyers is also correct.

• The final complexity conclusion follows.

Polynomial-time feasibility settles the continuous problem independently of discrete hardness. The conditional statement about NP-hardness is correct under standard polynomial-time reductions. The cited auction paper states Proposition 1 and defines equilibrium allocations through demanded bundles partitioning the items. [Dynamic Auction: a Tractable Auction Procedure](https://ojs.aaai.org/index.php/AAAI/article/download/7633/7494)

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩