Answer: \(1\)
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIn combinatorial auctions with gross substi- tutes condition, the Cavallo redistribution scheme’s worst- case redistribution fraction is exactly n−m−1 n .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix a finite set \(J\) of item categories and a finite set \(\Theta\) of gross-substitutes valuations over integral bundles \(B\subseteq J\), with per-capita supplies \(q_j\). For populations of size \(N\), give category \(j\) an integer supply approximating \(Nq_j\), and let the empirical type distribution converge to \(\mu\in\Delta(\Theta)\). Among sequences of anonymous finite-population VCG redistribution mechanisms that are strategy-proof, individually rational, and non-deficit at every \(N\), find a limiting per-type rebate rule \(\beta_\theta(\mu)\) maximizing \(\inf_{\mu:\,p(\mu)>0}\frac{\sum_{\theta\in\Theta}\mu_\theta\beta_\theta(\mu)}{p(\mu)}\), where \(p(\mu)\) is limiting VCG revenue per capita and allocations assign integral bundles to each unit of mass subject to the category supplies.
Fix \(m=|J|>1\), a finite report domain \(\Theta\) of gross-substitutes valuations given by binary-rational bundle tables, and binary-rational supplies \(q_j>0\) with \(\sum_j q_j<1\). Valuations are nonnegative, satisfy \(v_\theta(\varnothing)=0\), and obey free disposal; utilities are quasilinear.
A society is given by its support: the list of its \(\tau\) types with positive binary-rational masses \(\mu_\theta\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. State any running times in \(m,\tau,|\Theta|\), total input bit length \(L\), and any accuracy parameter.
A mass allocation consists of \(x_{\theta B}\geq0\) with \(\sum_B x_{\theta B}=\mu_\theta\) and \(\sum_{\theta,B:j\in B}x_{\theta B}\leq q_j\); each recipient receives an integral bundle \(B\subseteq J\). Allocations maximize total valuation.
At population size \(N\), category \(j\) has \(\lfloor Nq_j\rfloor\) copies, and each agent can receive at most one copy of each category. Use Clarke-pivot VCG; resolve ties uniformly over efficient bundle assignments, so allocation is anonymous in distribution. Write \(R_N(n)\) for total VCG revenue at type-count vector \(n\).
An admissible sequence uses, at every \(N\), a nonnegative rebate function \(r_N\) of the multiset of other agents’ reports only. On every profile \(n\) with \(\sum_\theta n_\theta=N\), require \(\sum_{\theta:n_\theta>0}n_\theta r_N(n-e_\theta)\leq R_N(n)\); the resulting mechanisms must be strategy-proof, individually rational, and non-deficit.
For each rational society, let \(D\) clear the denominators of \(\mu\) and \(q\), and take limits through \(N=kD\): \(p(\mu)=\lim_{k\to\infty}R_{kD}(kD\mu)/(kD)\) and \(\beta_\theta(\mu)=\lim_{k\to\infty}r_{kD}(kD\mu-e_\theta)\) for supported types. Admissible sequences must have these rebate limits at every rational society; assume at least one society has \(p(\mu)>0\).
What is the sharp worst-case limiting redistribution guarantee \(\sup_{(r_N)}\inf_{\mu\in\Delta(\Theta)\cap\mathbb{Q}^{|\Theta|}:p(\mu)>0}\frac{\sum_\theta\mu_\theta\beta_\theta(\mu)}{p(\mu)}\) achievable by admissible sequences?
For discrete gross-substitutes auctions with \(n>m+1\), Cavallo’s rebate \(R(I\setminus\{i\})/n\) has worst-case redistribution fraction exactly \((n-m-1)/n\), under the tie-free assumption. [Guo, 2011](https://ojs.aaai.org/index.php/AAAI/article/download/7883/7742).
For discrete homogeneous-unit auctions with nonincreasing marginal values, a worst-case optimal redistribution mechanism is known. [Guo–Conitzer](https://www.cs.cmu.edu/~conitzer/redistributionGEB08.pdf). No result settling the exact replicated-mass formulation above was located.
The guarantee is attained by Cavallo’s rebate, provided that the counterfactual auction retains the inventory of the original population.
In fact, a stronger statement holds: for every rational society, sufficiently large exact replications redistribute all VCG revenue. The threshold may depend on the society.
For an integer inventory \(c=(c_j)_{j\in J}\) and a type-count vector \(h\), let \(W_c(h)\) denote optimal integral welfare. Define its fractional relaxation by
\( F(t,c)=\max\left\{\sum_{\theta,B}v_\theta(B)y_{\theta B}: y_{\theta B}\geq0,\ \sum_B y_{\theta B}=t_\theta,\ \sum_{\theta,B:j\in B}y_{\theta B}\leq c_j \right\}. \)
Linear-programming duality gives
\[ F(t,c)= \min\left\{ \sum_\theta t_\theta u_\theta+\sum_j c_j\pi_j: u_\theta\geq0,\ \pi_j\geq0,\ u_\theta+\sum_{j\in B}\pi_j\geq v_\theta(B) \right\}. \tag{1} \]
We use three standard gross-substitutes facts:
\(
v(A)+v(B)\leq v(A\setminus\{a\})+v(B\cup\{a\}),
\)
or there exists \(b\in B\setminus A\) such that
\(
v(A)+v(B)\leq
v((A\setminus\{a\})\cup\{b\})+
v((B\setminus\{b\})\cup\{a\}).
\)
\(
U(\pi)=\max_{B\subseteq J}\left(v(B)-\sum_{j\in B}\pi_j\right)
\)
is submodular in prices:
\(
U(\pi)+U(\sigma)\geq U(\pi\vee\sigma)+U(\pi\wedge\sigma).
\)
These are the one-sided specializations of Theorems 9 and 6 of [Hatfield et al., *Full Substitutability*](https://web.stanford.edu/~ost/papers/fs2.pdf).
Here is why these facts apply to the category capacities and consumption restriction in the question.
Replace category \(j\) by \(c_j\) labeled copies. For a set \(A\) of copies, let \(\rho(A)\) be its set of represented categories, and extend a buyer’s valuation to
\( \widetilde v(A)=v(\rho(A)). \)
This extension satisfies the exchange condition. Indeed, fix \(a\in A\setminus B\), of category \(j\).
Thus the copy valuations are gross substitutes.
A feasible compressed fractional allocation lifts to the labeled configuration LP: distribute each type’s bundle masses equally among its agents, and choose the copy of each requested category uniformly. Every labeled copy of category \(j\) then has load at most \(c_j/c_j=1\). Categories with zero capacity have zero allocation.
Conversely, project any labeled fractional allocation through \(\rho\). Category usage weakly decreases and welfare is preserved. Hence the two fractional optimum values coincide. An integral optimum in the labeled market projects to a feasible original allocation after redundant copies are discarded. Therefore, for all integer \(h,c\),
\[ W_c(h)=F(h,c). \tag{2} \]
Fix inventory \(c\), and write \(W(S)\) for welfare with participating agent set \(S\). By (1)–(2),
\[ W(S)=\min_{\pi\geq0} \left(c\cdot\pi+\sum_{i\in S}U_i(\pi)\right). \tag{3} \]
Let \(\pi,\sigma\) minimize this expression for \(S,T\), respectively. Such minimizers exist: prices can be capped at the maximum bundle value without increasing the objective.
For agents in \(S\cap T\), use price submodularity. For agents belonging to just one set, use the fact that indirect utility decreases when prices increase. Finally,
\( c\cdot\pi+c\cdot\sigma =c\cdot(\pi\vee\sigma)+c\cdot(\pi\wedge\sigma). \)
Consequently,
\[ W(S)+W(T) \geq \left[c\cdot(\pi\vee\sigma)+\sum_{i\in S\cup T}U_i(\pi\vee\sigma)\right] + \left[c\cdot(\pi\wedge\sigma)+\sum_{i\in S\cap T}U_i(\pi\wedge\sigma)\right] \geq W(S\cup T)+W(S\cap T). \tag{4} \]
This proof requires no uniqueness of allocations.
Let \(\mathcal R_c(h)\) denote VCG revenue with inventory \(c\), for any number of participating agents. Summing Clarke-pivot payments over any efficient assignment gives
\[ \mathcal R_c(h) = W_c(h)-\sum_{\theta:h_\theta>0} h_\theta\bigl(W_c(h)-W_c(h-e_\theta)\bigr). \tag{5} \]
Thus total revenue is independent of which efficient assignment is selected. In particular, uniform tie-breaking leaves total revenue unchanged.
Revenue is monotone under adding agents. Indeed, for an agent \(a\in S\), (5) gives
\[ \mathcal R_c(S)-\mathcal R_c(S\setminus\{a\}) = \sum_{i\in S\setminus\{a\}} \left[ W(S\setminus\{i\})+W(S\setminus\{a\}) -W(S)-W(S\setminus\{a,i\}) \right] \geq0, \tag{6} \]
where each summand is nonnegative by (4).
At population size \(N\), set
\[ c_N=(\lfloor Nq_j\rfloor)_{j\in J}, \qquad r_N(s)=\frac{\mathcal R_{c_N}(s)}{N}, \qquad \sum_\theta s_\theta=N-1. \tag{7} \]
The counterfactual revenue in (7) uses inventory \(c_N\), not inventory \(c_{N-1}\).
This defines an admissible finite mechanism:
\( \sum_\theta n_\theta r_N(n-e_\theta) \leq \sum_\theta n_\theta\frac{\mathcal R_{c_N}(n)}N =R_N(n). \)
It remains to prove the rebate limits and their performance.
Fix a rational society \(\mu\), with support \(T\) of size \(\tau\). Throughout this section, take \(N=kD\), so
\( n=N\mu,\qquad c_N=Nq. \)
Restrict the dual variables to types in \(T\), and choose
\( V=\max\left\{1,\max_{\theta\in T}v_\theta(J)\right\}. \)
The dual in (1) can be restricted to the compact polytope
\[ P=\left\{ (u,\pi): 0\leq u_\theta\leq V,\ 0\leq\pi_j\leq V,\ u_\theta+\sum_{j\in B}\pi_j\geq v_\theta(B) \right\}. \tag{8} \]
To justify this restriction, first replace \(u_\theta\) by \(U_\theta(\pi)\). Then cap every price exceeding \(V\) at \(V\). Any bundle containing a capped category still has nonpositive net value, while the empty bundle has net value zero; hence the cap does not change indirect utilities. The objective weakly decreases, and indirect utilities lie in \([0,V]\).
Let \(E\) be the finite vertex set of \(P\), and define
\( w=\min_{(u,\pi)\in P}(\mu\cdot u+q\cdot\pi), \qquad E_0=\{(u,\pi)\in E:\mu\cdot u+q\cdot\pi=w\}. \)
For a nonnegative deletion vector \(d\) supported on \(T\), put
\[ H(d)=\max_{(u,\pi)\in E_0}d\cdot u, \qquad a_\theta=H(e_\theta). \tag{9} \]
Claim. For all sufficiently large \(N=kD\), simultaneously for every integer \(d\geq0\) with \(\sum_\theta d_\theta\leq2\),
\[ W_{Nq}(N\mu-d)=Nw-H(d). \tag{10} \]
Proof. Choose \(N\) large enough that every supported count is at least two. If there are vertices outside \(E_0\), their objective gaps have a positive minimum
\( \delta=\min_{(u,\pi)\in E\setminus E_0} \bigl(\mu\cdot u+q\cdot\pi-w\bigr)>0. \)
At such a vertex, the perturbed objective is at least
\( N(w+\delta)-d\cdot u\geq Nw+N\delta-2V. \)
For \(N\delta>2V\), this exceeds \(Nw\). Every active vertex has perturbed objective at most \(Nw\), because \(d,u\geq0\). Thus only active vertices can minimize the perturbed objective, whose minimum is \(Nw-H(d)\).
If all vertices are active, this conclusion holds directly. Equation (2) converts the fractional optimum into integral welfare. This proves (10). \(\square\)
For supported types \(\alpha,\theta\), choose two distinct agents of those types; if the types coincide, choose two agents of that type. Applying (4) to their single-agent deletions gives
\( W_{Nq}(n-e_\alpha)+W_{Nq}(n-e_\theta) \geq W_{Nq}(n)+W_{Nq}(n-e_\alpha-e_\theta). \)
Substituting (10) yields
\[ H(e_\alpha+e_\theta)\geq a_\alpha+a_\theta. \tag{11} \]
The reverse inequality follows directly from (9):
\( H(e_\alpha+e_\theta) =\max_{E_0}(u_\alpha+u_\theta) \leq\max_{E_0}u_\alpha+\max_{E_0}u_\theta =a_\alpha+a_\theta. \)
Therefore,
\[ H(e_\alpha+e_\theta)=a_\alpha+a_\theta. \tag{12} \]
In particular, for sufficiently large exact replications,
\( W_{Nq}(n)-W_{Nq}(n-e_\theta)=a_\theta, \)
and
\[ W_{Nq}(n-e_\alpha)-W_{Nq}(n-e_\alpha-e_\theta)=a_\theta. \tag{13} \]
Thus deleting one agent leaves every remaining agent’s marginal welfare contribution unchanged.
Define
\( P_\mu=w-\sum_{\theta\in T}\mu_\theta a_\theta. \)
Equations (5), (10), and (13) imply
\[ R_N(N\mu) =Nw-\sum_{\theta\in T}N\mu_\theta a_\theta =NP_\mu. \tag{14} \]
For every supported type \(\alpha\), the same calculation after deletion gives
\[ \mathcal R_{Nq}(N\mu-e_\alpha) = Nw-a_\alpha- \sum_{\theta\in T} \left(N\mu_\theta-\mathbf1_{\theta=\alpha}\right)a_\theta =NP_\mu. \tag{15} \]
These identities hold for every sufficiently large \(N=kD\). They prove both existence of the required revenue limit and
\( p(\mu)=P_\mu. \)
By (7) and (15),
\( r_N(N\mu-e_\alpha)=P_\mu \)
eventually. Hence the rebate limits exist at every rational society, including zero-revenue societies, and satisfy
\[ \beta_\alpha(\mu)=p(\mu) \quad\text{for every supported }\alpha. \tag{16} \]
For every society with \(p(\mu)>0\), the resulting limiting redistribution fraction is therefore
\[ \frac{\sum_{\theta\in T}\mu_\theta\beta_\theta(\mu)}{p(\mu)} = \frac{p(\mu)\sum_{\theta\in T}\mu_\theta}{p(\mu)} =1. \tag{17} \]
For any admissible sequence, finite-profile non-deficit at \(N\mu\), divided by \(N\), gives
\( \sum_{\theta\in T}\mu_\theta r_N(N\mu-e_\theta) \leq \frac{R_N(N\mu)}N. \)
Taking the prescribed limits is valid because the support is finite and all required limits exist. Consequently,
\( \sum_{\theta\in T}\mu_\theta\beta_\theta(\mu)\leq p(\mu). \)
Every positive-revenue society therefore has limiting fraction at most \(1\). The assumed existence of such a society makes the infimum’s domain nonempty. Combining this bound with (17) proves
\( \boxed{ \sup_{(r_N)} \inf_{\substack{\mu\in\Delta(\Theta)\cap\mathbb Q^{|\Theta|}\\p(\mu)>0}} \frac{\sum_\theta\mu_\theta\beta_\theta(\mu)}{p(\mu)} =1. } \)
The formula for \(p(\mu)\) is computationally explicit. First solve the bounded dual (8) for \(w\). Then, for each supported type \(\theta\), maximize \(u_\theta\) on its optimal face
\( \mu\cdot u+q\cdot\pi=w. \)
This computes \(a_\theta\), and hence \(p(\mu)\) and all supported rebate limits. There are \(\tau+1\) rational LPs, each with \(\tau+m\) variables and \(O(\tau2^m+\tau+m)\) constraints. Exact computation takes
\( (\tau+1)\operatorname{poly}(m,\tau2^m,|\Theta|,L) \)
bit operations. No accuracy parameter is needed.
Similarly, evaluating a finite rebate on an others-profile with support size \(t\) requires at most \(t+1\) compressed welfare LPs, using (5). Its value-computation time is
\( (t+1)\operatorname{poly}(m,t2^m,|\Theta|,L), \)
where here \(L\) includes the binary population size and counts. These are bounds for welfare, revenue, and rebate values.
Exact replication matters. For example, take two categories with \(q_1=q_2=1/4\), and additive types valuing category one at \(2\) and \(1\), respectively, and category two at zero. Let their masses be \(1/4\) and \(3/4\). At every exact replication, VCG revenue is \(N/4\). If instead the high-type count is increased by one, revenue becomes \(N/2\), although the empirical societies converge to the same \(\mu\).
Thus the proof establishes the requested exact-replication guarantee while fully allowing capacity boundaries and ties.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed sharp limiting guarantee of \(1\). I found no major or minor mathematical errors. Its polynomial-time claims apply to computing welfare, revenue, rebates, and the limiting quantities from the explicit bundle tables; it does not claim a polynomial-time procedure for sampling the uniform allocation lottery.
The dual in (1) is correct for nonnegative type masses and capacities. Although equality constraints ordinarily give unrestricted dual variables \(u_\theta\), the constraint for the empty bundle implies \(u_\theta\geq0\), since \(v_\theta(\varnothing)=0\).
The exchange condition and price-submodularity inequality are correctly stated. The cited Theorems 9 and 6 establish the relevant equivalences, and their one-sided specialization applies to the buyers here. Their treatment permits indifferences. [Hatfield et al., *Full Substitutability*](https://web.stanford.edu/~ost/papers/fs2.pdf).
The cited equilibrium-existence and configuration-LP results support the stated integrality fact for a finite labeled market with gross-substitutes buyers. The rational-to-integer scaling observation is valid: a common positive scaling preserves demands after corresponding price scaling and preserves optimal allocations. [Paes Leme–Wong, *Computing Walrasian equilibria*](https://link.springer.com/article/10.1007/s10107-018-1334-9).
The three exchange cases exhaust the possibilities for the category of \(a\). In the second case, the chosen same-category copy in \(B\) necessarily lies outside \(A\), because \(a\) is the only copy of that category in \(A\) and \(a\notin B\). In the third case, the exchanged category belongs to \(\rho(B)\setminus\rho(A)\), so its chosen copy also lies outside \(A\). The use of free disposal when redundant copies remain has the correct inequality direction.
The fractional lifting respects each agent’s total allocation mass and each labeled copy’s unit capacity. Projection preserves valuation and weakly decreases category usage. Discarding redundant copies from an integral labeled assignment enforces the original per-agent consumption restriction without changing welfare.
Thus (2) follows for nonnegative integer count vectors and inventories. Zero-capacity categories are explicitly handled; the empty-agent case has welfare zero.
Equation (3) follows from the dual and integrality result. Price capping justifies the existence of minimizers, including when some capacities are zero.
The comparison in (4) is valid term by term:
Each resulting bracket is at least the corresponding minimum defining welfare. Both inequality directions in (4) are therefore correct.
Summing Clarke-pivot payments gives (5). The identity uses only optimal welfare values and consequently remains valid under ties; individual payments may depend on the assignment, but their total does not.
Subtracting the revenue identity for the market without \(a\) gives precisely (6). Applying (4) to the two single-agent deletion sets makes every summand nonnegative. Fixed-inventory revenue monotonicity is established.
The construction uses the original population’s inventory \(c_N\) in every counterfactual. This is essential for the monotonicity argument and is stated explicitly.
Each admissibility condition is justified:
This reasoning covers small populations and zero inventories as well as the replication regime.
The restriction to the bounded polytope \(P\) is valid. After setting \(u_\theta=U_\theta(\pi)\), capping prices at \(V\) leaves indirect utilities unchanged: any bundle containing a capped category has nonpositive net value, and the empty bundle gives zero.
The vertex argument proves (10). At every inactive vertex, the perturbed objective is at least
\[
Nw+N\delta-2V.
\]
For \(N\delta>2V\), this exceeds \(Nw\), whereas every active vertex has perturbed objective at most \(Nw\). Minimization over active vertices then gives exactly \(Nw-H(d)\).
There are finitely many deletion vectors under consideration. The count condition ensures all these deletions are feasible, including two agents of the same supported type. The case with no inactive vertices is separately covered.
Applying welfare submodularity to the two deletion sets gives the displayed inequality. Substitution of (10) yields
\[
H(e_\alpha+e_\theta)\geq a_\alpha+a_\theta,
\]
with the correct sign.
The reverse inequality follows directly from the maximum defining \(H\). Thus (12) and (13) follow. The argument explicitly covers coincident types by choosing distinct agents.
No simultaneous maximizer for all \(u_\theta\) is assumed or needed.
Equation (14) follows by substituting the stabilized single-agent losses into (5).
For the deleted market, (13) gives each remaining agent’s marginal contribution. In (15), the welfare loss \(a_\alpha\) cancels exactly against the reduction in the number of agents contributing \(a_\alpha\). Counterfactual revenue therefore equals full-profile revenue for sufficiently large exact replications.
Consequently, the revenue and supported rebate limits exist at every rational society, including zero-revenue societies. Equations (16)–(17) correctly establish limiting redistribution fraction \(1\) whenever \(p(\mu)>0\).
The threshold may depend on the society. This matches the task’s pointwise limits; no uniform threshold is required.
Dividing finite-profile non-deficit by \(N\) gives the stated inequality. Passing to the limit is legitimate because the support is finite and the prescribed rebate limits exist.
The resulting upper bound applies to every admissible sequence and every positive-revenue rational society. The task’s existence assumption ensures that the infimum is over a nonempty set. Together with the construction, this proves the claimed supremum.
The optimal-face maximizations compute the same \(a_\theta\) defined using active vertices. The stated variable and constraint counts are correct. Exact rational LP computation yields polynomial bit complexity in the explicit-table input model; the factor \(2^m\) is already represented in those tables. The finite-rebate calculation likewise requires one welfare evaluation for the profile and one for each supported deletion type.
The boundary example also checks out. With \(N/4\) high agents and \(N/4\) copies, each allocated high agent pays \(1\), giving revenue \(N/4\). With one additional high agent, each allocated high agent pays \(2\), giving revenue \(N/2\). This establishes the claimed discontinuity without contradicting the prescribed exact-replication limit.
No repair or additional clarification is required to verify the target 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.