Answer: Polynomial-time solvable in \(m,\tau,K,L\), with at most \(\tau(m+1)\) positive assignment masses.
Proposition 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIf x is an optimal primal solution to the allo- cation LP and p is an optimal dual solution, then ⟨x, p⟩is a competitive equilibrium. The set of CE prices will typically not be unique. In our model, because each agent’s valuation is M-concave, the set of competitive equilibrium prices is in fact a lattice under the usual meet and join operations for real vectors.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an explicit impression set \(M\), a finite supported rational distribution \(\mu\) over complete bid-tree types \(t\), and rational per-capita supplies \(q_j\), find prices \(p_j\geq 0\) and an assignment of each type’s mass \(\mu_t\) over its feasible integral bundles \(B\). Every bundle receiving positive mass must maximize that type’s bid-tree value minus \(\sum_{j\in M}p_jB_j\); total assigned impressions must not exceed \(q_j\), and any impression with slack supply must have price zero.
Let \(M\) be an explicitly listed nonempty impression set, with \(m=|M|\), and let supplies be \(q_j\in\mathbb Q_{\geq0}\).
A society is given by its support: a list of \(\tau\) complete bid-tree types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a rooted tree of nonempty subsets of \(M\): the root is \(M\), children partition their parent, and leaves are singletons. Each node \(T\) has an incremental bid \(b_{tT}\in\mathbb Q\) and capacity \(c_{tT}\in\mathbb Z_{\geq0}\cup\{+\infty\}\); singleton capacities are finite. Capacities apply to each individual bundle, independently of the society's supplies.
Writing \(B(T)=\sum_{j\in T}B_j\), the feasible bundles are \(F_t=\{B\in\mathbb Z_{\geq0}^{M}:B(T)\leq c_{tT}\text{ for every node }T\}\), with value \(v_t(B)=\sum_T b_{tT}B(T)\).
An equilibrium consists of prices \(p\in\mathbb Q_{\geq0}^{M}\) and finitely supported rational assignment masses \(a_{tB}\geq0\), satisfying \(\sum_{B\in F_t}a_{tB}=\mu_t\). Positive assignment mass requires \(B\in\arg\max_{C\in F_t}\{v_t(C)-p\cdot C\}\); all utility ties are permitted.
For each impression, \(d_j=\sum_t\sum_{B\in F_t}a_{tB}B_j\leq q_j\), and \(d_j<q_j\) requires \(p_j=0\). Let \(K\) be the total number of tree nodes and \(L\) the total binary input length.
Is computing such an equilibrium polynomial-time in \(m,\tau,K,L\), or is it NP-hard?
For finitely many individual bidders, optimal allocation-LP solutions paired with optimal supply-constraint dual prices form a competitive equilibrium; integral supplies admit an integral optimal allocation, and the LP is polynomial-time solvable ([Lahaie, Parkes, and Pennock, 2008](https://econcs.seas.harvard.edu/sites/g/files/omnuum6346/files/econcs/files/lahaie_aaai08.pdf)).
No result settling this exact support-encoded problem with mass split over integral bundles was identified in the literature search.
An equilibrium can be computed in polynomial time in \(m,\tau,K,L\). The algorithm outputs rational prices and at most \(\tau(m+1)\) positive assignment masses, all with polynomial bit length.
The proof uses a compact linear program and an explicit decomposition of each type’s fractional allocation into feasible integral bundles.
Let \(\mathcal N_t\) denote the nodes of type \(t\)’s tree, and let \(\mathcal N_t^{\mathrm{fin}}\) contain its finite-capacity nodes. Define
\(w_{tj}=\sum_{T\in\mathcal N_t:\,j\in T}b_{tT}\).
Changing the order of summation gives, for every bundle \(B\),
\(v_t(B)=\sum_{T\in\mathcal N_t}b_{tT}\sum_{j\in T}B_j=\sum_{j\in M}w_{tj}B_j.\)
Thus the stated valuations are linear in bundle quantities, even when incremental bids are negative.
For a real vector \(x\), write \(x(T)=\sum_{j\in T}x_j\), and define
\(P_t=\{x\in\mathbb R_{\geq0}^{M}:x(T)\leq c_{tT}\text{ for every }T\in\mathcal N_t^{\mathrm{fin}}\}.\)
The zero vector belongs to \(P_t\). Finite singleton capacities make \(P_t\) bounded. Moreover,
\(F_t=P_t\cap\mathbb Z^{M}.\)
We next prove constructively that \(P_t=\operatorname{conv}(F_t)\), with an efficient rational decomposition.
Lemma. Every rational \(x\in P_t\) can be expressed as a rational convex combination of at most \(m+1\) bundles in \(F_t\). This combination can be computed in polynomial time in the encoding lengths of \(x\) and the tree.
Proof. Order the singleton leaves by a depth-first traversal of the tree, and write the resulting impression order as \(j_1,\ldots,j_m\). The descendant leaves of every node are consecutive in this order. Because children partition their parent, these descendant leaves are exactly the impressions belonging to that node.
Set
\(S_0=0,\qquad S_i=\sum_{h=1}^{i}x_{j_h}\quad(1\leq i\leq m).\)
For \(\theta\in[0,1)\), define an integral bundle by
\(B_{j_i}(\theta)=\lfloor S_i+\theta\rfloor-\lfloor S_{i-1}+\theta\rfloor.\)
Since the prefix sums are nondecreasing, all these coordinates are nonnegative.
Consider any finite-capacity node \(T\), whose impressions occupy positions \(a,\ldots,b\). Telescoping gives
\(B(\theta)(T)=\lfloor S_b+\theta\rfloor-\lfloor S_{a-1}+\theta\rfloor.\)
Feasibility of \(x\) implies \(S_b-S_{a-1}\leq c_{tT}\). Since \(c_{tT}\) is an integer,
\(\lfloor S_b+\theta\rfloor\leq\lfloor S_{a-1}+\theta+c_{tT}\rfloor=\lfloor S_{a-1}+\theta\rfloor+c_{tT}.\)
Consequently, \(B(\theta)(T)\leq c_{tT}\). This holds for every finite-capacity node, so \(B(\theta)\in F_t\).
For any nonnegative real \(s=n+r\), where \(n\) is integral and \(0\leq r<1\), the function \(\lfloor s+\theta\rfloor\) equals \(n\) for an interval of length \(1-r\) and \(n+1\) for an interval of length \(r\), apart from irrelevant endpoints. Therefore,
\(\int_0^1\lfloor s+\theta\rfloor\,d\theta=s.\)
Applying this identity to successive prefix sums yields
\(\int_0^1 B_{j_i}(\theta)\,d\theta=S_i-S_{i-1}=x_{j_i}.\)
It remains to turn this average into a small explicit combination. Each function \(\lfloor S_i+\theta\rfloor\) has at most one breakpoint inside \((0,1)\), located at
\(\beta_i=\lceil S_i\rceil-S_i\)
when this number is nonzero. Sort the distinct interior breakpoints together with the endpoints:
\(0=\gamma_0<\gamma_1<\cdots<\gamma_r=1.\)
There are at most \(m\) interior breakpoints, hence \(r\leq m+1\). For each interval choose
\(\theta_\ell=(\gamma_{\ell-1}+\gamma_\ell)/2,\qquad \alpha_\ell=\gamma_\ell-\gamma_{\ell-1},\qquad B^\ell=B(\theta_\ell).\)
The bundle is constant on each open interval, so the integral identity proves
\(x=\sum_{\ell=1}^{r}\alpha_\ell B^\ell,\qquad \sum_{\ell=1}^{r}\alpha_\ell=1,\qquad \alpha_\ell>0.\)
For rational \(x\), all prefix sums, breakpoints, weights, and representatives are rational. Their bit lengths remain polynomial: forming a sum of \(m\) encoded rationals increases bit length by at most a polynomial amount, and taking floors, sorting rationals, and forming differences and midpoints are polynomial-time operations. Computing the bundles uses at most \(m+1\) representatives and \(m\) coordinates per representative. This proves the lemma.
The same construction works for real \(x\), with real weights. Since \(P_t\) is convex and contains \(F_t\), it also proves
\(P_t=\operatorname{conv}(F_t).\)
Introduce aggregate quantity variables \(y_{tj}\), representing the total mass-weighted quantity assigned to type \(t\). Write \(y_t(T)=\sum_{j\in T}y_{tj}\).
Consider the linear program
\(\max\ \sum_{t=1}^{\tau}\sum_{j\in M}w_{tj}y_{tj}\)
subject to
\(y_{tj}\geq0\quad\text{for all }t,j,\)
\(y_t(T)\leq\mu_t c_{tT}\quad\text{for all }t,\ T\in\mathcal N_t^{\mathrm{fin}},\)
\(\sum_{t=1}^{\tau}y_{tj}\leq q_j\quad\text{for all }j\in M.\)
This program has \(\tau m\) variables and at most \(K+m\) constraints apart from nonnegativity.
To verify that it represents precisely the allowed assignment model, first take any feasible assignment and set
\(y_{tj}=\sum_{B\in F_t}a_{tB}B_j.\)
Every bundle obeys its individual capacity constraints, and the type’s assignment masses sum to \(\mu_t\). Consequently,
\(y_t(T)\leq\sum_B a_{tB}c_{tT}=\mu_t c_{tT}.\)
The supply inequalities also hold, and linearity of valuations makes the objective equal to assignment welfare.
Conversely, for any feasible \(y\), positivity of \(\mu_t\) permits the definition
\(x_t=y_t/\mu_t\in P_t.\)
Apply the lemma to obtain
\(x_t=\sum_{\ell}\alpha_{t\ell}B^{t\ell}.\)
Assign mass \(\mu_t\alpha_{t\ell}\) to bundle \(B^{t\ell}\), combining masses if a bundle occurs more than once. These masses sum to \(\mu_t\) and reproduce \(y_t\) exactly.
Thus the compact program is an exact formulation of the welfare problem with mass split over integral bundles.
Its feasible region is nonempty because \(y=0\) is feasible. It is bounded because
\(0\leq y_{tj}\leq\mu_t c_{t\{j\}}.\)
Hence its optimum is finite and attained.
Associate nonnegative dual variables \(p_j\) with supply constraints, and nonnegative variables \(\lambda_{tT}\) with finite-capacity constraints. The dual program is
\(\min\ \sum_{j\in M}q_jp_j+\sum_{t=1}^{\tau}\sum_{T\in\mathcal N_t^{\mathrm{fin}}}\mu_t c_{tT}\lambda_{tT}\)
subject to
\(p_j+\sum_{T\in\mathcal N_t^{\mathrm{fin}}:\,j\in T}\lambda_{tT}\geq w_{tj}\quad\text{for every }t,j,\)
\(p_j\geq0,\qquad\lambda_{tT}\geq0.\)
It is feasible: set all \(\lambda_{tT}=0\) and choose
\(p_j=\max\{0,w_{1j},\ldots,w_{\tau j}\}.\)
Choose optimal primal and dual solutions \(y\) and \((p,\lambda)\). Strong duality applies because the primal is feasible with a finite optimum.
Define the nonnegative dual slacks
\(r_{tj}=p_j+\sum_{T\in\mathcal N_t^{\mathrm{fin}}:\,j\in T}\lambda_{tT}-w_{tj}.\)
Expanding the difference between dual and primal objectives gives
\(0=\sum_jp_j\bigl(q_j-\sum_t y_{tj}\bigr)+\sum_t\sum_{T\in\mathcal N_t^{\mathrm{fin}}}\lambda_{tT}\bigl(\mu_t c_{tT}-y_t(T)\bigr)+\sum_t\sum_jr_{tj}y_{tj}.\)
Every summand is nonnegative. Therefore every summand vanishes.
In particular,
\(p_j\bigl(q_j-\sum_t y_{tj}\bigr)=0.\)
This is the required condition that unused supply has zero price.
For each type define
\(U_t=\sum_{T\in\mathcal N_t^{\mathrm{fin}}}c_{tT}\lambda_{tT}.\)
For any feasible integral bundle \(C\in F_t\), the definition of \(r_{tj}\) gives
\(v_t(C)-p\cdot C=\sum_{T\in\mathcal N_t^{\mathrm{fin}}}\lambda_{tT}C(T)-\sum_jr_{tj}C_j\leq U_t.\)
The inequality follows from \(C(T)\leq c_{tT}\), \(C_j\geq0\), and nonnegativity of \(\lambda\) and \(r\).
For \(x_t=y_t/\mu_t\), vanishing of the type’s capacity and coordinate slack terms, divided by the positive number \(\mu_t\), gives
\(\sum_T\lambda_{tT}\bigl(c_{tT}-x_t(T)\bigr)+\sum_jr_{tj}x_{tj}=0.\)
Thus
\(w_t\cdot x_t-p\cdot x_t=U_t.\)
Now decompose \(x_t=\sum_\ell\alpha_{t\ell}B^{t\ell}\) as in the lemma. Linearity implies
\(\sum_\ell\alpha_{t\ell}\bigl(v_t(B^{t\ell})-p\cdot B^{t\ell}\bigr)=U_t.\)
Every expression being averaged is at most \(U_t\), and every weight is positive. If any expression were strictly smaller, the average would be strictly smaller. Hence every supported bundle satisfies
\(v_t(B^{t\ell})-p\cdot B^{t\ell}=U_t.\)
Since all feasible bundles have utility at most \(U_t\), every bundle receiving positive assignment mass is utility-maximizing. Ties cause no difficulty.
Finally, the decomposition reproduces \(y\), so actual demand is \(d_j=\sum_t y_{tj}\). Primal feasibility and the supply slack equations give exactly the equilibrium’s supply and price conditions.
The only general algorithmic theorem needed is the standard theorem for rational linear programming: an explicitly encoded rational linear program with a feasible finite optimum admits exact rational optimal primal and dual solutions computable in time polynomial in its encoding length; such solutions can be chosen with polynomial bit length. Polynomial-time LP algorithms and the determinant bounds underlying the output-size guarantee are described in [MIT’s LP algorithm notes](https://courses.csail.mit.edu/6.854/18/Scribe/s14-lpAlgorithms/s14-lpAlgorithms.html) and [LP bit-complexity notes](https://courses.csail.mit.edu/6.854/21/Notes/n11-lp.html).
Its hypotheses were checked above. The compact primal and dual have polynomially many variables and constraints. Their coefficients are rational: the new coefficients are sums of input bids and products \(\mu_t c_{tT}\), all of polynomial bit length. Their complete encodings therefore have size polynomial in \(m,\tau,K,L\).
After solving them, division by each positive \(\mu_t\) preserves polynomial bit length. The decomposition lemma then produces at most \(m+1\) bundles per type in polynomial time. Multiplying its rational weights by \(\mu_t\) also preserves polynomial bit length.
The resulting explicit equilibrium consequently has at most \(\tau(m+1)\) positive assignment masses and is computable in polynomial time. No expansion into a number of individuals determined by the mass denominators is required.
⟨structured verdict parsed — rendered above⟩
The polynomial-time conclusion is sound in substance. The decomposition and duality arguments establish the required equilibrium, including utility maximization for every supported integral bundle. There is one minor quantifier gap: the claimed correspondence with rational assignments must restrict the converse direction to rational LP points.
The definition
\(w_{tj}=\sum_{T:\,j\in T}b_{tT}\)
correctly collects every incremental bid contributing to impression \(j\). Reordering the finite sums gives
\(v_t(B)=w_t\cdot B\).
No assumption that bids are nonnegative is needed.
The definition of \(P_t\) correctly omits infinite-capacity constraints. Its coordinates are nonnegative and bounded by finite singleton capacities. Consequently, \(P_t\) is nonempty, closed, and bounded, and
\(F_t=P_t\cap\mathbb Z^M\)
is correct.
Finding: These steps are justified.
Every step of the decomposition checks out.
\(B_{j_i}(\theta)\geq0\).
Each coordinate is integral.
\(S_b\leq S_{a-1}+c_{tT}\),
monotonicity of the floor function and integrality of \(c_{tT}\) give
\(B(\theta)(T)\leq c_{tT}\).
This also works for zero capacities and tight constraints.
The extension to real \(x\) establishes the claimed convex-hull identity. It does not assert efficient computation with arbitrary real inputs.
Finding: The decomposition lemma, the bound of \(m+1\) bundles, and \(P_t=\operatorname{conv}(F_t)\) are established.
The forward direction is correct: a permitted assignment produces aggregate quantities satisfying the scaled individual-capacity inequalities and the supply inequalities. Linearity makes the objective exactly assignment welfare.
For rational feasible \(y\), the converse is also correct. Positivity of \(\mu_t\) permits division, the decomposition lemma supplies rational weights, and multiplication by \(\mu_t\) produces rational assignment masses. These reproduce the quantities and welfare exactly.
Where: “Conversely, for any feasible \(y\)” and the ensuing claim that the program represents “precisely the allowed assignment model.”
An LP’s feasible points are real unless restricted otherwise. If \(y\) is irrational, the real decomposition need not yield rational assignment masses. Therefore the converse, stated for every feasible LP point, is too broad.
A concrete failure occurs with one impression, one type of mass \(1\), capacity \(1\), supply \(1\), and bid \(0\). The LP permits
\(y=\sqrt{2}/2\).
The only integral bundles are \(0\) and \(1\); rational assignment masses can produce only a rational aggregate quantity.
Minimum clarification: Restrict the converse correspondence to rational feasible \(y\). The later exact rational LP theorem supplies the rational optimal \(y\) needed by the algorithm.
This is minor because that theorem is already explicitly invoked, and the final equilibrium construction uses rational optimal solutions.
The remaining LP claims are correct. It has \(\tau m\) variables and at most \(K+m\) inequalities besides nonnegativity. The zero vector is feasible. Finite singleton capacities bound every variable, so the optimum is finite and attained.
The displayed dual has the correct objective, inequality directions, and nonnegative variables. The proposed feasible dual point works even with negative bids.
The invocation of strong duality is valid: the finite-dimensional primal is feasible and has a finite attained optimum; dual feasibility is also exhibited.
The objective-gap expansion is algebraically correct. Every term is nonnegative by primal feasibility, dual feasibility, and nonnegativity of the variables. Thus equality of optimal objective values forces every term to vanish.
In particular,
\(p_j(q_j-\sum_t y_{tj})=0\)
gives exactly the required zero-price condition for unused supply.
For each type:
This establishes individual demand optimality, rather than merely optimal aggregate welfare. Combining duplicate bundles preserves the conclusion.
Finding: The duality argument establishes all equilibrium conditions. Negative bids, utility ties, zero supplies, zero capacities, and redundant constraints do not invalidate it.
The rational LP theorem is stated with the needed guarantees: exact rational optimal primal and dual solutions, polynomial running time in the encoded LP size, and polynomial output bit length. Its hypotheses hold here. The cited notes support polynomial-time LP algorithms and the determinant bounds underlying polynomial-size optimal solutions. [MIT LP algorithm notes](https://courses.csail.mit.edu/6.854/18/Scribe/s14-lpAlgorithms/s14-lpAlgorithms.html), [MIT LP bit-complexity notes](https://courses.csail.mit.edu/6.854/21/Notes/n11-lp.html).
The encoding-size argument is correct:
The final support bound is therefore \(\tau(m+1)\), and the construction requires no expansion by mass denominators.
The output resolves the intended support-encoded equilibrium problem in polynomial time, subject only to the minor rationality qualification in Section 3. No false central step, missing substantive lemma, or unverified theorem application blocks the conclusion.
⟨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.