Answer: Polynomial-time solvable in the total explicit-table binary input length; the ordinary and strengthened allocation families describe exactly the same type-uniform core price set as absence of blocking coalitions.
Theorem 1 (Weakly Stronger Core Constraints) — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe two sets of constraints (C2) and (C3) describe the same core.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite item set \(G\), finitely many bidder types \(T\) with rational masses \(\mu_t\), explicit bundle-value menus \(v_t(S)\), and rational per-capita supplies \(b_g\), what is the complexity of computing a welfare-maximizing allocation and minimum-payment type-uniform prices \(p_t\) whose outcome has no blocking measurable coalition? Does the continuous allocation-based formulation that omits payments of nonconflicting incumbent mass preserve exactly the same core price set?
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. Normalize \(\sum_t\mu_t=1\), and realize each type as an atomless interval of length \(\mu_t\), with measure \(\lambda\).
Let \(G\) contain \(m\geq1\) goods, with binary-rational supplies \(b_g\geq0\). Each type has an explicit rational value table \(v_t:2^G\to\mathbb Q\), with \(v_t(\varnothing)=0\); values may have either sign. The seller owns all supplies and values retained goods at zero.
An allocation \(X\) measurably assigns one bundle to each bidder and is feasible when \(\lambda\{a:g\in X(a)\}\leq b_g\) for every \(g\). Write \(V(X)=\int v_{t(a)}(X(a))\,d\lambda(a)\). Represent allocations by their type–bundle masses.
Choose a welfare-maximizing allocation, resolving ties by lexicographically maximizing its mass table in a fixed input order, and call it \(X^*\). Let \(W=\{a:X^*(a)\ne\varnothing\}\). Type-uniform payments mean \(p(a)=p_{t(a)}\geq0\) on \(W\), and zero otherwise; require \(p(a)\leq v_{t(a)}(X^*(a))\) almost everywhere, and set \(p_t=0\) for types with no winning mass.
Utilities are quasilinear. A blocking coalition consists of the seller and a measurable bidder set \(C\): it can assign feasible bundles only to \(C\), with integrable transfers, so that every member of \(C\) weakly improves almost everywhere and the seller receives strictly more than \(\int_Wp\,d\lambda\). Deviation transfers may be signed and need not be type-uniform. A core outcome has no such coalition.
For any feasible alternative allocation \(Y\), put \(D=\{a:Y(a)\ne\varnothing\}\). Its ordinary allocation constraint is \(\int_{W\setminus D}p\,d\lambda\geq V(Y)-\int_Dv_{t(a)}(X^*(a))\,d\lambda\).
A retained incumbent set \(R\subseteq W\setminus D\) is nonconflicting when assigning \(Y\) on \(D\) and \(X^*\) on \(R\) is jointly feasible. The strengthened family requires \(\int_{W\setminus(D\cup R)}p\,d\lambda\geq V(Y)-\int_Dv_{t(a)}(X^*(a))\,d\lambda\) for every feasible \(Y\) and every such measurable \(R\).
Is computing \(X^*\) and core type-uniform payments minimizing \(\int_Wp\,d\lambda\), or determining that no such payments exist, polynomial-time solvable or NP-hard?
For every \(X^*\), does the strengthened allocation family describe exactly the same type-uniform core price set as the ordinary family and absence of blocking coalitions?
State running times in \(m\), \(\tau\), and the total binary input length \(L\), including the explicit value tables.
In discrete combinatorial auctions, omitting nonconflicting incumbent payments preserves the core price polytope; winner determination is NP-hard ([Bünz–Seuken–Lubin](https://people.bu.edu/blubin/papers/md/CCGAlgorithm2015AAAI.pdf)).
For continuum quasilinear bundle markets, Walrasian equilibrium existence is known, but this is a different question from minimum type-uniform core payments and the strengthened constraint identity ([Azevedo–Weyl–White](https://eduardomazevedo.github.io/papers/Azevedo-et-al-Walrasian.pdf)); no result settling these exact questions was identified.
The problem is polynomial-time solvable in the total binary input length \(L\), including the explicit value tables. One can compute the prescribed allocation \(X^*\), find minimum-revenue type-uniform core payments, or correctly report that no such payments exist.
The ordinary allocation constraints, the strengthened allocation constraints, and absence of blocking coalitions describe exactly the same price set, subject to the payment restrictions in the question. This equivalence holds for every welfare-maximizing \(X^*\).
The proof uses finite rational linear programs. Type-uniform core payments need not exist.
Let \(\mathcal B=2^G\), let \(M=2^m\), and let \(N=\tau M\). Write \(x_{t,S}\) for the mass of type \(t\) receiving bundle \(S\).
The welfare problem is the rational linear program
\[ \max_x \sum_t\sum_{S\in\mathcal B}v_t(S)x_{t,S}, \]
with constraints
\[ \sum_{S\in\mathcal B}x_{t,S}=\mu_t\quad\text{for every }t, \]
\[ \sum_t\sum_{\substack{S\in\mathcal B\\g\in S}}x_{t,S}\leq b_g \quad\text{for every }g, \qquad x_{t,S}\geq0. \]
Every allocation yields a feasible mass table. Conversely, every feasible table is realizable by partitioning each type interval into measurable pieces of the prescribed masses. Thus this LP exactly represents welfare maximization.
Its feasible set is nonempty, because everyone can receive \(\varnothing\), and compact, because \(0\leq x_{t,S}\leq\mu_t\). Hence an optimum exists.
First maximize welfare. Fix its optimal value, then successively maximize each mass-table coordinate in the prescribed input order, fixing each coordinate after optimization. This computes \(x^*\) using at most \(N+1\) rational LP solves.
No positive-mass winning cell has negative incumbent value. Indeed, replacing a positive mass assigned bundle \(S\) with \(\varnothing\) preserves feasibility and strictly increases welfare when \(v_t(S)<0\).
For later use, the lexicographically selected \(x^*\) is a vertex of the original feasible polytope. To prove this, suppose \(x^*=(y+z)/2\) for distinct feasible \(y,z\). Welfare optimality and linearity imply that both are welfare-optimal. At the first coordinate where \(y,z\) differ, one exceeds \(x^*\), while all preceding coordinates equal those of \(x^*\). This contradicts lexicographic optimality.
Consequently, if
\[ K=\{(t,S):x^*_{t,S}>0\},\qquad k=|K|, \]
then \(k\leq\tau+m\). Otherwise, the \(k\) columns recording type membership and good consumption would have a nonzero linear dependence. Perturbing the positive coordinates slightly in both directions along that dependence would preserve every type mass and every good consumption, contradicting that \(x^*\) is a vertex.
Fix any incumbent allocation and payments satisfying the restrictions in the question. Define current bidder utility and seller revenue by
\[ u(a)=v_{t(a)}(X^*(a))-p(a), \qquad P=\int_Wp\,d\lambda. \]
The payment restrictions imply \(u(a)\geq0\) almost everywhere; outside \(W\), utility is zero.
For an alternative allocation \(Y\), with nonempty-bundle recipient set \(D\), its ordinary constraint is equivalent to
\[ V(Y)-\int_Du\,d\lambda\leq P. \]
Indeed,
\[ \int_Du\,d\lambda = \int_Dv_{t(a)}(X^*(a))\,d\lambda - \int_{D\cap W}p\,d\lambda, \]
and \(P-\int_{D\cap W}p\,d\lambda=\int_{W\setminus D}p\,d\lambda\).
A violated ordinary constraint produces a blocking coalition. Take the bidder coalition to be \(D\), assign \(Y\), and charge each coalition bidder
\[ q(a)=v_{t(a)}(Y(a))-u(a). \]
These transfers are measurable and integrable: there are finitely many types and bundles, all table values are finite, and current payments are finite. Signed transfers are permitted. Each bidder retains exactly utility \(u(a)\), while seller revenue is
\[ \int_Dq\,d\lambda = V(Y)-\int_Du\,d\lambda>P. \]
Thus the seller strictly improves.
Every blocking coalition violates an ordinary constraint. Suppose a coalition \(C\) assigns feasible bundles and uses integrable net payments \(q(a)\) to the seller. Extend its assignment to an allocation \(Y\) by giving \(\varnothing\) outside \(C\), and let \(D\subseteq C\) be its nonempty-bundle recipients.
Weak improvement gives, almost everywhere on \(C\),
\[ q(a)\leq v_{t(a)}(Y(a))-u(a). \]
Therefore its seller revenue is at most
\[ \int_Cq\,d\lambda \leq V(Y)-\int_Cu\,d\lambda = V(Y)-\int_Du\,d\lambda-\int_{C\setminus D}u\,d\lambda \leq V(Y)-\int_Du\,d\lambda. \]
The last inequality uses \(u\geq0\). If seller revenue strictly exceeds \(P\), the ordinary constraint for \(Y\) is violated.
This proves the claimed equivalence, including coalitions containing bidders who receive empty bundles.
Let \(Y\) be feasible, with recipient set \(D\), and let \(R\subseteq W\setminus D\) satisfy the specified joint-feasibility condition. Define \(Z\) by assigning \(Y\) on \(D\), retaining \(X^*\) on \(R\), and assigning \(\varnothing\) elsewhere.
By hypothesis, \(Z\) is feasible. Its recipient set is \(D\cup R\), and
\[ V(Z)=V(Y)+\int_Rv_{t(a)}(X^*(a))\,d\lambda. \]
Applying the ordinary constraint to \(Z\) yields
\[ \int_{W\setminus(D\cup R)}p\,d\lambda \geq V(Z)-\int_{D\cup R}v_{t(a)}(X^*(a))\,d\lambda = V(Y)-\int_Dv_{t(a)}(X^*(a))\,d\lambda. \]
This is exactly the strengthened constraint for \((Y,R)\). Conversely, taking \(R=\varnothing\) recovers every ordinary constraint.
Hence the families are equivalent. This argument does not require optimality or type-uniformity; its essential hypothesis is joint feasibility of the whole retained set. It establishes the continuum identity directly, alongside the discrete identity in [Bünz–Seuken–Lubin, Theorem 1](https://people.bu.edu/blubin/papers/md/CCGAlgorithm2015AAAI.pdf).
Partition bidders into incumbent cells
\[ A_{t,S}=\{a:t(a)=t,\ X^*(a)=S\}, \qquad \lambda(A_{t,S})=x^*_{t,S}, \]
using only positive-mass cells \((t,S)\in K\). Define
\[ h_S= \begin{cases} 1,&S\ne\varnothing,\\ 0,&S=\varnothing, \end{cases} \qquad w_t=\sum_{S\ne\varnothing}x^*_{t,S}. \]
For admissible type payments \(p\), current utility on cell \(A_{t,S}\) is \(v_t(S)-h_Sp_t\), and revenue is
\[ P(p)=\sum_tw_tp_t. \]
Introduce \(z_{t,S,T}\geq0\) for each \((t,S)\in K\) and each nonempty \(T\subseteq G\). This variable is the mass from incumbent cell \(A_{t,S}\) receiving \(T\) in a deviation. Its constraints are
\[ \sum_{T\ne\varnothing}z_{t,S,T}\leq x^*_{t,S} \quad\text{for every }(t,S)\in K, \]
\[ \sum_{(t,S)\in K}\sum_{\substack{T\ne\varnothing\\g\in T}}z_{t,S,T} \leq b_g \quad\text{for every }g. \]
Atomlessness makes this description exact. Every alternative allocation gives these masses; conversely, each feasible \(z\) can be realized by measurably partitioning each incumbent cell, with its unassigned remainder receiving \(\varnothing\).
Thus the largest seller revenue obtainable from the nonempty recipients while preserving their current utilities is
\[ F(p)= \max_z \sum_{(t,S)\in K}\sum_{T\ne\varnothing} \bigl(v_t(T)-v_t(S)+h_Sp_t\bigr)z_{t,S,T}. \]
Section 2 proves that admissible payments are core payments exactly when
\[ F(p)\leq P(p). \]
As a consistency check, taking \(Y=X^*\) gives objective value \(P(p)\), so always \(F(p)\geq P(p)\). Core membership therefore means equality.
For fixed \(p\), the deviation LP is feasible and compact. Its dual has nonnegative variables \(\alpha_{t,S}\) for cell capacities and \(q_g\) for good supplies:
\[ \min_{\alpha,q} \sum_{(t,S)\in K}x^*_{t,S}\alpha_{t,S} +\sum_gb_gq_g, \]
subject to
\[ \alpha_{t,S}+\sum_{g\in T}q_g \geq v_t(T)-v_t(S)+h_Sp_t \]
for every \((t,S)\in K\) and every nonempty \(T\subseteq G\).
The dual is feasible: set \(q=0\) and choose each \(\alpha_{t,S}\) at least the maximum of zero and its finitely many right-hand sides. Finite-dimensional LP strong duality therefore applies, with attained optimal values.
It follows that \(F(p)\leq P(p)\) holds exactly when some nonnegative \(\alpha,q\) satisfy these dual constraints and
\[ \sum_{(t,S)\in K}x^*_{t,S}\alpha_{t,S} +\sum_gb_gq_g \leq\sum_tw_tp_t. \]
Consequently, solve one rational LP with objective
\[ \min_{p,\alpha,q}\sum_tw_tp_t, \]
subject to the preceding dual constraints, the preceding revenue inequality, and the payment restrictions
\[ p_t\geq0, \]
\[ p_t\leq v_t(S) \quad\text{whenever }(t,S)\in K,\ S\ne\varnothing, \]
\[ p_t=0\quad\text{whenever }w_t=0, \qquad \alpha_{t,S}\geq0,\quad q_g\geq0. \]
Its projection onto \(p\) is exactly the type-uniform core price set. If it is infeasible, no such payments exist. Otherwise, its objective is bounded below by zero, and rational LP optimization returns minimum-revenue core payments.
This construction does not require applying the continuum equilibrium-existence theorem of [Azevedo–Weyl–White](https://eduardomazevedo.github.io/papers/Azevedo-et-al-Walrasian.pdf).
The LP sizes are:
| Stage | Variables | Constraints, including bounds | LP solves |
|---|---:|---:|---:|
| Welfare and lexicographic selection | \(N=\tau2^m\) | \(O(N+\tau+m)\) per solve | At most \(N+1\) |
| Minimum core payments | \(\tau+k+m\leq2(\tau+m)\) | \(O(k2^m+\tau+m)\) | One |
For an arbitrary supplied incumbent table, the same payment formulation works with \(k\leq N\), giving at most \(O(\tau4^m+\tau+m)\) constraints. The smaller bound above uses the prescribed lexicographic selection.
The sequential lexicographic solves have polynomial encoding length. Each fixed coordinate optimum is attained at a vertex of a face of the original feasible polytope, hence at an original vertex. Rational vertex coordinates have polynomial bit length in the original LP encoding by Cramer’s rule and determinant bounds. The welfare optimum likewise has polynomial bit length. Thus all intermediate equality constants, the final \(x^*\), and every coefficient of the payment LP have polynomial bit length.
Standard polynomial-time rational LP algorithms therefore give total bit running time
\[ \operatorname{poly}\!\left(m,\tau2^m,L\right), \]
which can also be written as
\[ 2^{O(m)}\operatorname{poly}(\tau,L). \]
Because the input explicitly lists \(\tau2^m\) table entries, \(L\geq\tau2^m\), up to the fixed encoding convention. Hence the algorithm is polynomial in \(L\). It returns exact rational mass tables and payments of polynomial output length.
Consider one type of mass \(1\), goods \(A,B\), supplies
\[ b_A=b_B=\frac14, \]
and values
\[ v(\varnothing)=0,\qquad v(\{A\})=1,\qquad v(\{B\})=2,\qquad v(\{A,B\})=0. \]
For any feasible allocation,
\[ V=x_{\{A\}}+2x_{\{B\}}\leq\frac14+2\cdot\frac14=\frac34. \]
Equality requires \(x_{\{A\}}=x_{\{B\}}=\frac14\). Feasibility then forces \(x_{\{A,B\}}=0\), so \(x_\varnothing=\frac12\). Thus every welfare-maximizing mass table has these masses.
A type-uniform payment must satisfy \(p\leq1\), because some winners receive \(\{A\}\). Seller revenue is therefore at most
\[ \frac12p\leq\frac12. \]
The losing bidders have mass \(\frac12\) and current utility zero. Assigning \(\{A\}\) to half of them and \(\{B\}\) to the other half is feasible. Charging their respective values preserves zero utility and gives seller revenue
\[ \frac14\cdot1+\frac14\cdot2=\frac34>\frac12. \]
Hence no type-uniform core payments exist in this instance. This confirms why the algorithm must include an infeasibility outcome.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves both questions in USER_TASK: it establishes polynomial-time solvability under the explicit-table encoding and proves equality of the ordinary, strengthened, and coalition-defined type-uniform core price sets. I found no mathematical errors or gaps requiring repair.
The welfare LP correctly represents the allocation problem.
The feasible region is nonempty and compact, so the welfare maximum exists even when values have either sign.
Successively optimizing and fixing the coordinates on the welfare-optimal face correctly implements the specified lexicographic rule. The stated bound of \(N+1\) LP solves is correct.
The exclusion of negative-valued winning cells is valid: replacing such a cell by the empty bundle preserves feasibility and strictly increases welfare. This assertion concerns positive-mass cells, exactly as required by the almost-everywhere payment restrictions.
The vertex argument is also correct. If the selected table were the midpoint of two distinct feasible tables, both would be welfare-optimal. At their first differing coordinate, one would exceed the selected table while matching all earlier coordinates, contradicting lexicographic maximality.
The support bound \(k\leq\tau+m\) follows from the stated dependence argument. A dependence among more than \(\tau+m\) consumption columns permits sufficiently small perturbations in both directions, preserving nonnegativity, type totals, and all good consumptions. This contradicts vertexhood. Including empty-bundle cells does not invalidate the argument.
The algebraic reformulation is correct:
\[ V(Y)-\int_Du\,d\lambda\leq P. \]
It uses the stipulated zero payments outside \(W\), and the payment restrictions ensure \(u\geq0\) almost everywhere.
Both implications are verified.
A violated constraint produces a block. The proposed coalition \(D\) receives a feasible assignment. Its transfers preserve each participant’s current utility exactly, and the violated inequality makes seller revenue strictly greater than \(P\). Signed transfers are expressly allowed. Measurability and integrability follow from the finite value tables and bounded incumbent payments.
A block produces a violated constraint. Weak improvement gives the stated pointwise upper bound on transfers. Integrating it bounds coalition revenue by
\[ V(Y)-\int_Du\,d\lambda-\int_{C\setminus D}u\,d\lambda. \]
Dropping the final, nonnegative utility integral is justified. Consequently, seller revenue exceeding \(P\) forces an ordinary-constraint violation.
The treatment of coalition members assigned empty bundles is essential and correct. No assumption that every coalition member receives goods is introduced.
The construction of \(Z\) is valid because the task explicitly requires joint feasibility of \(Y\) on \(D\) and the retained incumbent assignment on \(R\).
Since \(R\subseteq W\setminus D\), the recipient sets are disjoint. The displayed welfare decomposition and cancellation of incumbent values are exact. Applying the ordinary constraint to \(Z\) therefore gives precisely the strengthened constraint for \((Y,R)\).
Conversely, \(R=\varnothing\) recovers every ordinary constraint. Thus both implications hold for the full measurable families, including null sets and empty recipient sets.
The proof correctly uses joint feasibility of the entire retained set. It does not substitute individual nonconflict for joint feasibility. Its conclusion therefore applies to every welfare-maximizing \(X^*\), as requested.
The attribution of the discrete analogue to Theorem 1 is accurate; the continuum argument is independently established in the output. [Bünz–Seuken–Lubin, Theorem 1](https://people.bu.edu/blubin/papers/md/CCGAlgorithm2015AAAI.pdf).
The incumbent-cell formulation is exact.
Every alternative allocation determines feasible intersection masses \(z_{t,S,T}\). Conversely, every feasible collection of these masses can be realized by partitioning each positive-mass incumbent cell. Such cells inherit atomlessness from the type intervals.
The cell-capacity constraints prevent assigning more bidders than are available, and the good constraints impose exactly the original supply restrictions. The unassigned remainder receives the empty bundle.
The objective coefficient
\[ v_t(T)-v_t(S)+h_Sp_t \]
is the bidder’s deviating value minus current utility. For incumbent losers, \(S=\varnothing\), so the normalization \(v_t(\varnothing)=0\) and \(h_S=0\) give the correct coefficient.
Thus \(F(p)\) represents the maximum expression appearing in the ordinary constraints. Section 2 justifies the claimed characterization \(F(p)\leq P(p)\).
The consistency check \(F(p)\geq P(p)\) is correct: assigning every incumbent winner their original bundle yields objective value exactly \(P(p)\).
The displayed dual is correct. Both primal resource families are upper-bound constraints with nonnegative primal variables, so nonnegative dual variables and the stated covering inequalities have the correct signs.
The strong-duality application satisfies its hypotheses:
Consequently, the optimal dual value equals \(F(p)\), and an attained dual certificate of value at most \(P(p)\) exists exactly when \(F(p)\leq P(p)\).
The combined payment formulation remains linear: incumbent masses and winning masses are fixed coefficients, so no products of optimization variables occur.
The payment inequalities impose precisely the task’s restrictions, including the bound from every positive-mass winning cell and the zero payment for types without winning mass. Its projection onto \(p\) is therefore exactly the admissible type-uniform core set.
Infeasibility correctly certifies that no such payments exist. Otherwise, the objective is bounded below, and finite rational LP optimization supplies an attained minimum. Unbounded auxiliary dual variables do not invalidate this conclusion.
The stated dimensions and solve counts are correct:
The bit-length justification correctly addresses the potential growth caused by sequential lexicographic solves. Every successive optimization takes place on a face of the original polytope. Its optimum can be attained at an original vertex, whose rational coordinates have polynomial bit length by determinant bounds. The welfare optimum and all fixed coordinate constants consequently have polynomial bit length.
The payment LP likewise has polynomial-size rational coefficients. Standard polynomial-time rational LP algorithms therefore give
\[ \operatorname{poly}(m,\tau2^m,L) = 2^{O(m)}\operatorname{poly}(\tau,L). \]
Because the input explicitly contains all \(\tau2^m\) value entries, this is polynomial in \(L\). The output correctly makes no claim of polynomial dependence on \(m\) independently of the explicit tables.
The example’s calculations are correct. Welfare cannot exceed \(3/4\), and equality forces singleton winning masses \(1/4\) each and zero mass on the two-good bundle. Uniform individual rationality then bounds revenue by \(1/2\).
The losing mass is \(1/2\), sufficient for the stated feasible deviation. Charging singleton values preserves losers’ zero utilities and raises revenue to \(3/4\), strictly exceeding every admissible uniform-payment revenue.
The formulations also accommodate zero supplies, no winning mass, zero-valued winners, negative alternative values, and unused supplies. None creates an omitted hypothesis or failure of the argument.
No major or minor mathematical issues were found. No additional clarification or repair is needed to verify the claimed results.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.