Answer: Polynomial-time solvable, including the exact rational threshold and its endpoint status.
Proposition 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe method described by this section is op- timal for the bidder-optimal core-selecting combinatorial auction.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational distribution μ over bidder types, per-capita item supplies, and a type \(t\) with a losing bid on bundle \(S\), designate mass \(q>0\) of type \(t\) as a cohort. What is the exact threshold \(p^\star\) such that changing that cohort’s bid on \(S\) to \(p\) leaves the welfare-maximizing allocation and fixed-tie-broken bidder-optimal core outcome unchanged for \(b_t(S) ≤ p ≤ p^\star\), while a bid above \(p^\star\) changes the selected outcome?
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Masses sum to \(1\). There are \(m\geq1\) item kinds with positive binary-rational per-capita supplies \(s_j\).
Each type has an explicit list of admissible nonempty bundles \(B\subseteq[m]\) and nonnegative binary-rational bids \(b_r(B)\); bids are XOR. The empty bundle is always admissible with bid zero. Utilities are quasilinear; the core uses reported bids.
Given a listed bundle \(S\) of type \(t\) and binary-rational \(0<q\leq\mu_t\), label a cohort \(c\) of mass \(q\) separately from the remaining type-\(t\) mass, retaining identical bids initially and omitting zero-mass classes.
An allocation specifies masses \(x_{rB}\geq0\), with \(\sum_Bx_{rB}=\mu_r\) and \(\sum_{r,B:j\in B}x_{rB}\leq s_j\). Each member receives one whole bundle; splitting a type's mass across bundles is permitted.
An outcome also specifies total payments \(h_{rB}\), with \(0\leq h_{rB}\leq x_{rB}b_r(B)\) and \(h_{r\varnothing}=0\). Members of a positive-mass class \((r,B)\) each pay \(h_{rB}/x_{rB}\). Use the transferable-utility core with the seller: coalitions may contain arbitrary submasses of these classes, and the seller contributes its entire supply; bidder-only coalitions have no items.
Select an allocation maximizing \(\sum_{r,B}x_{rB}b_r(B)\), breaking ties by lexicographically minimizing \(x\). For that allocation, select core payments minimizing \(\sum_{r,B}h_{rB}\), breaking ties by lexicographically minimizing \(h\). Coordinate orders are fixed by the input labels and bundle lists and do not depend on bid amounts. Promise that initially \(x_{cS}=0\); the cohort may win other bundles.
Let \(O(p)\) be this selected allocation-payment pair when only \(b_c(S)\) is replaced by the real number \(p\geq b_t(S)\). Define \(p^\star=\sup\{p\geq b_t(S):O(p)=O(b_t(S))\}\), and include whether \(O(p^\star)=O(b_t(S))\) in the threshold problem.
Is computing this exact threshold, including its endpoint status, possible in polynomial time, or is it NP-hard? State running times in \(m\), \(\tau\), the total number \(N\) of listed bids, and the total input bit length \(L\).
Discrete: an optimal mixed-integer method for bidder-optimal envy quotes is established, without a polynomial-time guarantee ([Othman–Sandholm](https://www.cs.cmu.edu/~sandholm/www/envy%20quotes%20for%20CAs.aaai10.pdf)). No result settling this precise mass-cohort threshold problem was identified in the literature search.
The exact threshold and its endpoint status are computable in polynomial time. The algorithm uses \(O(N+\tau)\) rational linear programs, each with \(O(m+N+\tau)\) variables and constraints and polynomial encoding length. Its total bit running time is
\[
(m+\tau+N+L)^{O(1)}.
\]
The key is that arbitrary submasses may form coalitions. This makes the blocking-coalition calculation a linear program and gives a compact characterization of minimum-revenue core payments.
After labeling the cohort, let \(R\leq\tau+1\) be the number of positive-mass classes. Write \(\mathcal A_r\) for class \(r\)'s admissible bundles, including the empty bundle, and let
\[
K=\sum_r|\mathcal A_r|\leq 2N+\tau+1.
\]
The increase comes from duplicating type \(t\)'s list when its remaining mass is positive.
For item prices \(\lambda\in\mathbb R_{\geq0}^m\), write \(\lambda(B)=\sum_{j\in B}\lambda_j\). For a fixed bid vector \(b\), the welfare LP maximizes \(\sum_{r,B}x_{rB}b_r(B)\), subject to the allocation constraints in the question. Its dual is
\[
\min_{\lambda,w}\left\{s\cdot\lambda+\sum_r\mu_rw_r:
\lambda\geq0,\quad w_r+\lambda(B)\geq b_r(B)\ \text{for every }r,B\right\}.
\]
The empty-bundle constraints imply \(w_r\geq0\).
The primal is feasible by allocating everyone the empty bundle. It is bounded because \(0\leq x_{rB}\leq\mu_r\). Thus strong LP duality applies. Let \(W(b)\) be its optimum and define the optimal dual polytope
\[
D(b)=\left\{(\lambda,w):
\lambda\geq0,\ w\geq0,\ w_r+\lambda(B)\geq b_r(B),\
s\cdot\lambda+\sum_r\mu_rw_r=W(b)\right\}.
\]
This polytope is nonempty and compact: positivity of every supply and retained mass gives \(\lambda_j\leq W(b)/s_j\) and \(w_r\leq W(b)/\mu_r\).
For any welfare-optimal \(x\) and any \((\lambda,w)\in D(b)\), the duality gap is
\[
0=\sum_j\lambda_j\left(s_j-\sum_{r,B:j\in B}x_{rB}\right)
+\sum_{r,B}x_{rB}\bigl(w_r+\lambda(B)-b_r(B)\bigr).
\]
Every term is nonnegative. Consequently,
\[
x_{rB}>0\ \Longrightarrow\ w_r+\lambda(B)=b_r(B),
\qquad
s\cdot\lambda=\sum_{r,B}x_{rB}\lambda(B).
\]
Lemma. Fix a welfare-optimal allocation \(x\) and payments satisfying the stipulated bounds. The outcome is in the core if and only if some \((\lambda,w)\in D(b)\) satisfies
\[
h_{rB}\geq x_{rB}\lambda(B)\qquad\text{for every }r,B.
\]
Proof. Index the positive-mass allocated classes by \(i\). Write their masses as \(x_i\), their types as \(r(i)\), and their current bundles as \(B_i\). Their per-member utilities and the seller’s utility are
\[
u_i=b_{r(i)}(B_i)-h_i/x_i\geq0,
\qquad H=\sum_i h_i.
\]
Bidder-only coalitions cannot block: they have no items, their worth is zero, and their current utilities are nonnegative.
For coalitions containing the seller, consider
\[
\Phi(u)=\max_z\sum_i\sum_{C\in\mathcal A_{r(i)}}z_{iC}\bigl(b_{r(i)}(C)-u_i\bigr),
\]
subject to
\[
z_{iC}\geq0,\qquad \sum_Cz_{iC}\leq x_i,\qquad
\sum_i\sum_{C:j\in C}z_{iC}\leq s_j.
\]
This is exactly the maximum coalition worth minus the included bidders’ current utility. Indeed, a feasible \(z\) includes mass \(y_i=\sum_Cz_{iC}\) from class \(i\) and assigns those members whole bundles. Conversely, an optimal allocation for any seller-containing coalition produces such a \(z\). Arbitrary submasses and further splitting by assigned bundle are permitted by the hypotheses.
Hence the core condition is \(\Phi(u)\leq H\). Assigning every class its current bundle is feasible and yields objective \(H\), so the condition is equivalent to \(\Phi(u)=H\).
The dual of this blocking LP is
\[
\min_{\lambda,\alpha}\left\{s\cdot\lambda+\sum_i x_i\alpha_i:
\lambda,\alpha\geq0,\
\alpha_i+\lambda(C)\geq b_{r(i)}(C)-u_i\right\}.
\]
The primal is feasible and bounded, so strong duality applies.
Suppose the outcome is in the core. Choose an optimal blocking dual, whose objective is \(H\). Its current-bundle constraints and allocation feasibility give
\[
H\leq\sum_i x_i\bigl(\alpha_i+\lambda(B_i)\bigr)
\leq s\cdot\lambda+\sum_i x_i\alpha_i=H.
\]
Thus equality holds throughout. Since every \(x_i>0\),
\[
\alpha_i+\lambda(B_i)=h_i/x_i.
\]
In particular, \(h_i\geq x_i\lambda(B_i)\).
Set \(w_i=u_i+\alpha_i\). The dual constraints and the preceding equality imply
\[
w_i\geq b_{r(i)}(C)-\lambda(C)\quad\text{for every }C,
\qquad
w_i=b_{r(i)}(B_i)-\lambda(B_i).
\]
Therefore \(w_i=\max_C\{b_{r(i)}(C)-\lambda(C)\}\), which depends only on the type. Denote it by \(w_r\). It is nonnegative because the empty bundle is admissible. Moreover,
\[
s\cdot\lambda+\sum_r\mu_rw_r
=H+\sum_i x_i u_i
=\sum_i x_i b_{r(i)}(B_i)
=W(b).
\]
Thus \((\lambda,w)\in D(b)\).
Conversely, suppose \((\lambda,w)\in D(b)\) and \(h_i\geq x_i\lambda(B_i)\). Define \(\alpha_i=h_i/x_i-\lambda(B_i)\geq0\). The welfare complementary equalities give \(u_i+\alpha_i=w_{r(i)}\). Hence the welfare dual constraints imply
\[
\alpha_i+\lambda(C)\geq b_{r(i)}(C)-u_i.
\]
This is a feasible blocking dual, and its objective equals
\[
s\cdot\lambda+\sum_i x_i\alpha_i
=s\cdot\lambda+H-\sum_i x_i\lambda(B_i)=H.
\]
Thus \(\Phi(u)\leq H\), proving core membership. ∎
Define the payment vector induced by a welfare dual as
\[
T_x(\lambda)_{rB}=x_{rB}\lambda(B).
\]
For every \((\lambda,w)\in D(b)\), this vector satisfies the payment bounds: on positive allocation coordinates, \(\lambda(B)\leq b_r(B)\), and its empty-bundle payment is zero. The lemma shows that it is in the core.
Conversely, every core payment vector \(h\) has a supporting welfare dual with \(T_x(\lambda)\leq h\) coordinatewise. Replacing \(h\) by \(T_x(\lambda)\) preserves core membership and weakly lowers every payment. Therefore, if \(h\) minimizes total revenue, equality must hold in every coordinate.
It follows that the selected payments are computed by:
These are linear objectives. Thus the full payment selection uses at most \(K+1\) LPs.
Let \(p_0=b_t(S)\), and let \((x^0,h^0)=O(p_0)\). Write \(W_0=W(b^0)\) and \(D_0=D(b^0)\), where \(b^0\) denotes the initial bids after cohort labeling. By the promise, \(x^0_{cS}=0\).
Define
\[
F_0=\left\{(\lambda,w)\in D_0:
x^0_{rB}\lambda(B)=h^0_{rB}\ \text{for every }r,B\right\}.
\]
Section 3 shows that \(F_0\) is nonempty. It is compact because it is a closed subset of \(D_0\).
Compute
\[
P=\max_{(\lambda,w)\in F_0}\bigl(w_c+\lambda(S)\bigr).
\]
This is one rational LP. Its maximum is attained and finite, and its initial cohort constraint ensures \(P\geq p_0\).
Claim. The requested threshold is \(p^\star=P\).
Choose a maximizer \((\lambda^\dagger,w^\dagger)\in F_0\). For every \(p\in[p_0,P]\), it satisfies the changed cohort constraint \(w_c+\lambda(S)\geq p\). All other dual constraints are unchanged, and its dual objective is \(W_0\). Meanwhile, \(x^0\) retains primal objective \(W_0\), because \(x^0_{cS}=0\). Therefore \(x^0\) remains welfare-optimal throughout this interval.
If \(p<P\), the changed constraint is strictly slack at this dual solution. The nonnegative duality-gap formula then forces every optimal allocation at \(p\) to have \(x_{cS}=0\). Such an allocation has the same welfare under the initial bids, so it was initially optimal. Since \(x^0\) was the lexicographically smallest initial optimum, it remains the selected allocation.
On this interval, the optimal welfare dual set is exactly
\[
D(p)=D_0\cap\{(\lambda,w):w_c+\lambda(S)\geq p\}.
\]
It contains \((\lambda^\dagger,w^\dagger)\), which reproduces \(h^0\). The original payment vector minimizes total payment and then lexicographic order over the price-payment vectors obtained from \(D_0\). It therefore remains selected over the subset obtained from \(D(p)\).
Thus \(O(p)=O(p_0)\) for every \(p_0\leq p<P\).
Now suppose \(p>P\) and nevertheless \(O(p)=O(p_0)\). Then \(x^0\) is selected and \(W(b^p)=W_0\). By Section 3, its selected minimum-revenue payments \(h^0\) must equal \(T_{x^0}(\lambda)\) for some optimal welfare dual at \(p\). That dual belongs to \(F_0\) and satisfies \(w_c+\lambda(S)\geq p>P\), contradicting the definition of \(P\).
Hence no bid above \(P\) preserves the outcome. Together with the preceding interval result and the fact that \(p_0\) itself preserves the outcome, this proves \(p^\star=P\).
At \(p=P\), the original allocation remains welfare-optimal and the original payments remain feasible. Additional optimal allocations can, however, appear.
Compute the lexicographically selected welfare allocation \(x^P\) at the rational bid \(P\). Then
\[
O(p^\star)=O(p_0)\quad\Longleftrightarrow\quad x^P=x^0.
\]
The forward implication is immediate. For the reverse implication, if the selected allocation remains \(x^0\), the payment argument in Section 4 still applies at \(P\): the smaller dual set contains a dual reproducing \(h^0\), so the same payments remain selected.
Both endpoint statuses can occur. For example, take one type of mass one, label the entire type as the cohort, and give each of two items supply one. List \(T=\{1\}\) before \(S=\{2\}\), with initial bids \(b(T)=1\) and \(b(S)=0\). Initially everyone receives \(T\), and minimum core revenue is zero. The threshold is \(1\). At that bid, lexicographically minimizing the \(T\)-coordinate assigns everyone \(S\), so the endpoint is excluded. Reversing the order of the two listed bundles includes the endpoint.
The complete algorithm performs:
Thus it uses at most \(3K+4=O(N+\tau)\) LP calls. Each has \(O(m+N+\tau)\) variables and constraints.
Exact rational LP optimization runs in polynomial bit time, and rational vertices have polynomial encoding length; see [Goemans’s linear programming notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf). These facts apply here because all coefficients are rational and the relevant polytopes are nonempty and bounded.
More specifically, successive lexicographic minimizations restrict an original polytope to faces. Their optimum values are attained at vertices of that original polytope, so repeated tie-breaking does not cause uncontrolled growth of rational bit lengths. The initial allocation, welfare, and payments consequently have polynomial encoding length. The threshold LP then has polynomial encoding length, yielding a rational \(P\) of polynomial encoding length; the same argument applies to endpoint selection.
The total running time is therefore \((m+\tau+N+L)^{O(1)}\), and polynomial in the explicit input length \(L\). No enumeration of possible types or of unlisted bundles is required.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned threshold problem correctly. The core characterization, threshold formula, endpoint test, and polynomial bit complexity follow from the written argument. I found no major or minor mathematical issues requiring repair.
The established running time is \((m+\tau+N+L)^{O(1)}\), using \(O(N+\tau)\) rational LP calls. This is a polynomial bit-time guarantee, not a strongly polynomial guarantee.
The welfare LP matches the task: allocation variables represent masses receiving whole admissible bundles, type-mass constraints are equalities, and item-supply constraints are inequalities.
The displayed dual is correct. Its class variables are initially unrestricted because they correspond to equality constraints; the empty-bundle inequalities then imply \(w_r\geq0\).
The hypotheses for strong duality are verified:
The optimal dual set is nonempty. Its compactness argument is also correct: all terms in its fixed objective are nonnegative, and every retained mass and every supply is strictly positive. Consequently, the stated coordinate bounds hold, including when \(W(b)=0\).
The duality-gap identity has the correct signs and coefficients. Since all its terms are nonnegative, it establishes complementary slackness for every pair consisting of a welfare-optimal allocation and an optimal dual solution. Both consequences used later follow.
Assessment: Correct.
Indexing positive-mass allocated classes is appropriate because members within each such class have the same current per-member utility.
The constraints \(\sum_Cz_{iC}\leq x_i\) represent arbitrary coalition submasses. The variables permit those submasses to be reassigned across admissible whole bundles, exactly as authorized by the task. The item constraints correctly give a seller-containing coalition the seller’s entire supply.
The objective subtracts the current utilities of precisely the included bidders. Thus \(\Phi(u)\leq H\) is the correct transferable-utility core condition for seller-containing coalitions. Bidder-only coalitions cannot block because their worth is zero and current bidder utilities are nonnegative.
Assigning every allocated class its current bundle is feasible and gives objective \(H\). Therefore the equivalence between core membership and \(\Phi(u)=H\) is justified.
The blocking dual is correctly formulated. The blocking primal is feasible and bounded, so an optimal dual exists with objective \(H\) when the outcome is in the core.
The displayed chain of inequalities is valid. Equality throughout forces each positive-mass current-bundle constraint to be tight and gives \(h_i\geq x_i\lambda(B_i)\).
The conclusion
\[
w_i=\max_C\{b_{r(i)}(C)-\lambda(C)\}
\]
follows from the combination of the inequalities for all admissible bundles and equality for the currently allocated bundle. Consequently, all allocated subclasses belonging to the same input class have the same \(w_r\). The separately labeled cohort is correctly treated as its own class when its bid changes.
The objective calculation establishing membership in \(D(b)\) is correct.
The proposed \(\alpha_i\) are nonnegative. Welfare complementary slackness gives the asserted identity \(u_i+\alpha_i=w_{r(i)}\), which verifies every blocking-dual constraint.
The blocking-dual objective equals \(H\), using the previously established supply complementary-slackness identity. Weak duality then proves the required core inequality.
Zero allocation coordinates cause no division problem: the proof only divides by positive \(x_i\), while the stipulated payment bounds force payments on zero coordinates to vanish.
Assessment: The lemma is proved in both directions.
For an optimal welfare dual, complementary slackness and \(w_r\geq0\) verify the upper payment bounds for \(T_x(\lambda)\). Nonnegative prices verify the lower bounds, and the empty bundle has zero price. The core lemma establishes feasibility.
Conversely, the lemma supplies a coordinatewise dominated price-payment vector for every core payment vector. If any coordinate were strictly smaller, its total revenue would be strictly smaller. Thus every minimum-revenue core payment vector is represented by an optimal welfare dual.
This establishes the claimed reduction of both revenue minimization and payment lexicographic selection to linear objectives over \(D(b)\). Possible nonuniqueness of the representing dual does not affect the selected payment vector.
Assessment: Correct.
The set \(F_0\) is nonempty by the payment characterization and compact as a closed subset of \(D_0\). Its objective therefore has a finite attained maximum \(P\). Initial dual feasibility establishes \(P\geq p_0\).
The maximizing dual remains feasible for every real \(p\in[p_0,P]\), with objective \(W_0\). Because \(x^0_{cS}=0\), the original allocation also retains objective \(W_0\). Weak duality therefore establishes welfare optimality throughout this interval.
For \(p<P\), the changed constraint is strictly slack at this particular optimal dual. Complementary slackness consequently forces every welfare-optimal allocation at \(p\) to have zero cohort-\(S\) mass.
Every such allocation was initially optimal. Since \(x^0\) remains available and was initially lexicographically smallest, it remains selected. This verifies the allocation tie-breaking argument with its required quantifier over all current optima.
The equality describing \(D(p)\) is valid on the interval because welfare remains \(W_0\) and only one dual inequality changes. Its subset relationship to \(D_0\), together with the retained dual reproducing \(h^0\), proves that both payment selection stages preserve \(h^0\).
If the original outcome were selected at a bid \(p>P\), its unchanged allocation would imply welfare \(W_0\). The minimum-revenue characterization would then supply an optimal dual reproducing \(h^0\).
Because the changed inequality is stronger than the initial inequality, this dual belongs to \(F_0\). Its changed constraint contradicts the definition of \(P\).
Thus the proof establishes preservation below \(P\) and exclusion above \(P\). The supremum conclusion also covers \(P=p_0\), since the initial bid itself always preserves its initial outcome.
Assessment: The exact threshold \(p^\star=P\) is proved.
At \(P\), welfare optimality of \(x^0\) survives, but strict slackness need not. The prover correctly allows new optimal allocations to appear.
If endpoint allocation selection still returns \(x^0\), the restricted dual set contains a dual reproducing \(h^0\), and the same payment-selection argument applies. Hence the stated equivalence between outcome preservation and allocation equality is valid.
The examples are also correct. With bids \(1\) on \(T\) and \(0\) on \(S\), the initial allocation is uniquely all \(T\), with zero minimum revenue. At bid \(1\) on \(S\), welfare maximization assigns total mass one across the two singleton bundles. Minimizing the \(T\)-coordinate selects all \(S\); reversing their order selects all \(T\). The empty-bundle coordinate is zero at these optima and does not invalidate either example.
Assessment: Both the endpoint algorithm and examples are correct.
The cohort duplication bound \(K\leq2N+\tau+1\) is valid, including the omission of a zero-mass remainder.
The LP count is correct: three selection stages use at most \(K+1\) calls each, and threshold maximization uses one, totaling \(3K+4\). Each implemented LP has \(O(m+N+\tau)\) variables and constraints.
The argument addresses intermediate bit lengths, rather than merely counting LP calls. Successive lexicographic restrictions are faces of the corresponding fixed original polytope. Their linear optimum values can be attained at vertices of that polytope, so repeated restrictions do not introduce uncontrolled encoding growth. The resulting initial values give the threshold LP polynomial encoding length; its rational optimum then gives the endpoint LP polynomial encoding length.
The cited rational-LP facts apply: the implemented feasible regions are nonempty bounded rational polytopes. The cited [Goemans notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf) support polynomial vertex encoding bounds and polynomial-time rational linear programming.
Exact endpoint comparison is therefore justified. No enumeration of unlisted bundles or possible unsupported types is needed.
Assessment: The claimed polynomial bit-time bound is established.
No additional lemma, correction, or clarification is needed to verify the claimed result.
⟨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.