Answer: The divisible outcome exists for every society, attains an exact \(1\)-approximation, and retains strong budget balance, individual rationality, and pointwise incentive compatibility. Every refinement with \(\operatorname{OPT}>0\) satisfies \(0\leq\operatorname{OPT}-\operatorname{GFT}(x^{(h)})\leq h\sum_g r_g\max_v v\), so its efficiency ratio converges to \(1\) for every fixed society.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe ascending-prices auction of Subsection 4.1 is strongly-budget-balanced, individually-rational and obvi- ously truthful, and its gain-from-trade approaches the opti- mum when the optimal market size (k) approaches ∞.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given categories \(G\), a recipe \(r_g\), and rational masses \(\mu_{g,v}\) of agents with category \(g\) and value \(v\), compute the divisible-mass ascending-price clock outcome. Trade quantities \(x_{g,v}\) and total trade mass \(q\) must satisfy \(0\le x_{g,v}\le\mu_{g,v}\) and \(\sum_v x_{g,v}=r_gq\); determine the outcome’s gain from trade \(\sum_{g,v}v x_{g,v}\) relative to the maximum over feasible mass trades, and establish its budget-balance, individual-rationality, and pointwise incentive properties as the largest individual mass tends to zero.
Let \(G\) contain \(m\) public categories, with one public recipe \(r_g\in\mathbb Z_{>0}\) and a category order fixed independently of values. Values \(v\in\mathbb Q\) may have either sign and are private; utilities are quasilinear, with signed payments to the auctioneer.
A society is given by its support: the list of the \(\tau\) types \((g,v)\) with positive mass, each mass \(\mu_{g,v}\) a binary rational. Here \(\tau\) is the support size, not the number of possible types. Normalize total mass to \(1\); let \(L\) be the total input bit length.
A feasible trade satisfies \(q\geq0\), \(0\leq x_{g,v}\leq\mu_{g,v}\), and \(\sum_v x_{g,v}=r_gq\). Write \(\operatorname{GFT}(x)=\sum_{g,v}v x_{g,v}\) and \(\operatorname{OPT}=\max_x\operatorname{GFT}(x)\), allowing no trade; consider approximation ratios only when \(\operatorname{OPT}>0\).
Define the mass clock through refinements: choose a common denominator \(D\) of the masses and, for each positive integer \(n\), split every type into packets of mass \(h=1/(Dn)\). Each packet has its type's value and acts independently; equal-valued packets have a public exit order independent of reports.
For each refinement, initialize \(p_g=-\infty\). With \(N_g\) packets in category \(g\), set \(c=\min_g\lfloor N_g/r_g\rfloor\); if \(c=0\), make no trade. Otherwise raise prices in oversized categories until their remaining packet counts have floor quotient \(c\).
Cycle through categories in the fixed order. Raise \(p_g\) until its remaining count becomes \(r_gc\), or until \(\sum_g r_gp_g=0\). Skip a category already at its target count; after a complete cycle decrement \(c\), stopping without trade if it becomes zero.
Packets exit irreversibly when their value is reached, processing equal-valued packets one at a time in the public order. If balance and an exit coincide, process that exit and then stop. Other packets at the same value may remain until their scheduled exit.
At balance, select uniformly \(r_gc\) remaining packets from each category, each trading packet paying \(hp_g\). Let \(x^{(h)}\) be expected trading masses and \(t^{(h)}_{g,v}=p_gx^{(h)}_{g,v}\) be expected signed payments; both are zero when there is no trade. The divisible outcome is their limit as \(n\to\infty\), if it exists.
Pointwise incentive compatibility means that an infinitesimal trader, whose deviation leaves aggregate masses unchanged, cannot improve expected utility per unit by changing its exit strategy; its category is fixed. State computation times in \(m,\tau,L\), the recipe's binary encoding length, and, for refinements, \(\log(1/h)\).
Does the divisible clock outcome exist, and what approximation guarantee does it attain relative to \(\operatorname{OPT}\)?
For every fixed society with \(\operatorname{OPT}>0\), does \(\operatorname{GFT}(x^{(h)})/\operatorname{OPT}\to1\) as \(h\to0\), or can a positive efficiency loss persist; does the limit retain strong budget balance, individual rationality, and pointwise incentive compatibility?
For finite agents with distinct values within categories, the ascending clock is strongly budget balanced, individually rational, and obviously truthful, with gain from trade approaching the optimum as the number of optimal procurement sets grows. [Verified full version](https://arxiv.org/html/1911.08094v2).
No result settling this precisely specified divisible refinement limit was located.
The specified divisible outcome exists for every society. It attains exactly \(\operatorname{OPT}\), retains strong budget balance and individual rationality, and is pointwise incentive compatible.
Moreover, write \(V_g=\max_v v\) and \(A=\sum_g r_gV_g\). Whenever \(\operatorname{OPT}>0\), every category is nonempty, \(A>0\), and every refinement satisfies
\(\displaystyle 0\leq \operatorname{OPT}-\operatorname{GFT}(x^{(h)})\leq hA.\)
Consequently,
\(\displaystyle \max\left\{0,1-\frac{hA}{\operatorname{OPT}}\right\}\leq \frac{\operatorname{GFT}(x^{(h)})}{\operatorname{OPT}}\leq 1.\)
Thus no positive efficiency loss persists for any fixed society with positive optimum.
The finite clock is analyzed in [Gonen and Segal-Halevi, Section 4.3](https://arxiv.org/html/1911.08094v2). The proof below directly handles the ties and refinement rule specified in the question.
Relabel categories according to their public order as \(1,\ldots,m\). Let \(M_g=\sum_v\mu_{g,v}\) and \(Q=\min_g M_g/r_g\). If a category is empty, then \(Q=0\), and every feasible allocation and every refinement make no trade. Henceforth assume all categories are nonempty.
For a fixed quantity \(q\in[0,Q]\), let \(z_{g,v}(q)\) allocate mass \(r_gq\) to the highest values in category \(g\), taking a fraction of the cutoff type if necessary. This is optimal at that quantity: exchanging selected lower-value mass for available higher-value mass weakly increases gains from trade.
Define
\(\displaystyle F(q)=\sum_{g,v}v\,z_{g,v}(q).\)
Each category’s contribution is continuous and piecewise linear, with nonincreasing marginal value. Therefore \(F\) is continuous, concave, and piecewise linear, and
\(\displaystyle \operatorname{OPT}=\max_{q\in[0,Q]}F(q).\)
Let
\(\displaystyle q^*=\max\{q\in[0,Q]:F(q)=\operatorname{OPT}\}.\)
The largest maximizer exists by continuity and compactness. We will prove that the clock converges to
\(\displaystyle x^*_{g,v}=z_{g,v}(q^*).\)
In particular, the clock selects the largest optimal quantity, including any terminal interval of zero marginal gains.
Fix a refinement with packet mass \(h\).
Suppose balance occurs in round \(c\), and let \(K_g\) be the number of remaining packets in category \(g\). Then
\(\displaystyle r_gc\leq K_g\leq r_g(c+1).\)
Indeed, initialization leaves each category with floor quotient \(c\), hence fewer than \(r_g(c+1)\) packets. After any completed round with target \(c+1\), every category has exactly \(r_g(c+1)\) packets. During the next round, counts decrease only toward \(r_gc\).
Prices only rise, and exits occur in increasing value order. Thus every exited packet has value at most its final category price, and every remaining packet has value at least that price. The stipulated treatment of equal values preserves these weak inequalities.
At balance all prices are finite and \(\sum_g r_gp_g=0\). For every feasible allocation \(y\),
\(\displaystyle \operatorname{GFT}(y)=\sum_{g,v}(v-p_g)y_{g,v}\leq\sum_{g,v}\mu_{g,v}(v-p_g)_+,\)
where \((a)_+=\max\{a,0\}\). The equality uses \(\sum_v y_{g,v}=r_gq\) and price balance.
Let
\(\displaystyle S_g=h\sum_{\text{remaining packets }i\text{ in }g}(v_i-p_g).\)
All positive-surplus packets remain, and any exited packet has nonpositive surplus. Consequently,
\(\displaystyle \sum_{g,v}\mu_{g,v}(v-p_g)_+=\sum_g S_g.\)
Each remaining packet is selected with probability \(\alpha_g=r_gc/K_g\). Expected payments sum to zero, so
\(\displaystyle \operatorname{GFT}(x^{(h)})=\sum_g\alpha_gS_g.\)
It follows that
\(\displaystyle \begin{aligned} \operatorname{OPT}-\operatorname{GFT}(x^{(h)}) &\leq\sum_g(1-\alpha_g)S_g\\ &\leq h\sum_g(K_g-r_gc)(V_g-p_g)\\ &\leq h\sum_g r_g(V_g-p_g) =hA. \end{aligned}\)
Here \(V_g-p_g\) is nonnegative because category \(g\) has remaining packets. Feasibility of the expected allocation also gives \(\operatorname{GFT}(x^{(h)})\leq\operatorname{OPT}\).
It remains to establish the same bound when the clock makes no trade.
If \(Q\leq h\), then \(F(q)\leq qA\) implies \(\operatorname{OPT}\leq hA\).
Suppose instead that \(Q>h\). Every category then has more than \(r_g\) packets. If round \(1\) completes without balance, its final price in category \(g\) is the value of the \((r_g+1)\)-st highest packet. The weighted sum of these prices is strictly negative; otherwise balance would have occurred.
That sum is precisely the right derivative \(F'_+(h)\): immediately beyond quantity \(h\), the next packet in category \(g\) supplies its marginal value with weight \(r_g\). Hence \(F'_+(h)<0\). Concavity implies that \(F\) decreases beyond \(h\), so
\(\displaystyle \operatorname{OPT}=\max_{0\leq q\leq h}F(q)\leq hA.\)
Finally, positive optimum implies \(A>0\), since \(F(q)\leq qA\). This completes the refinement bound.
Efficiency convergence alone does not establish convergence of payments. We now identify the eventual price vector.
Assume first that \(q^*>0\). At mass \(r_gq^*\), define:
These are well defined because each category has finite support. At a cumulative-mass breakpoint, \(b_g\) is the value on the higher side and \(a_g\) the value on the lower side. Inside a type’s mass interval, they coincide. Always \(a_g\leq b_g\).
Optimality gives
\(\displaystyle \sum_g r_gb_g\geq0.\)
If \(q^*<Q\), the weighted marginal value immediately to its right is strictly negative. A positive value would contradict optimality; zero would give a larger maximizer because \(F\) is piecewise linear. If \(q^*=Q\), some \(a_g=-\infty\). Thus, in either case,
\(\displaystyle \sum_g r_ga_g<0.\)
For \(j=0,\ldots,m\), define the extended-real sums
\(\displaystyle B_j=\sum_{g\leq j}r_gb_g+\sum_{g>j}r_ga_g.\)
They are nondecreasing, with \(B_0<0\) and \(B_m\geq0\). Let \(k\) be the first index with \(B_k\geq0\). Define
\(\displaystyle p_g^*= \begin{cases} b_g,&g<k,\\ -\dfrac{\sum_{j<k}r_jb_j+\sum_{j>k}r_ja_j}{r_k},&g=k,\\ a_g,&g>k. \end{cases}\)
Because \(B_k\geq0\), no \(a_g=-\infty\) remains after \(k\). Thus every displayed price is finite. Moreover, \(B_{k-1}<0\) and \(B_k\geq0\) imply
\(\displaystyle a_k<p_k^*\leq b_k,\qquad \sum_g r_gp_g^*=0.\)
This is the price vector reached by raising coordinates, in public order, from \(a_g\) toward \(b_g\) until balance.
For a refinement, let \(w_g(j)\) denote the value of the \(j\)-th highest packet in category \(g\), and set \(w_g(j)=-\infty\) when \(j>N_g\).
If a round with target \(c\) completes without balance, its endpoint price is
\(\displaystyle E_g(c)=w_g(r_gc+1).\)
When any packets must exit, this is the last exited packet’s value. In the initial round, a category already exactly at its target retains price \(-\infty\), which agrees with the convention above.
The sum \(\sum_g r_gE_g(c)\) is nondecreasing as \(c\) decreases. Starting each round with a negative price sum, balance occurs in that round exactly when its hypothetical endpoint sum is nonnegative.
Set
\(\displaystyle \widehat c_h=\left\lceil\frac{q^*}{h}\right\rceil-1.\)
For all sufficiently small \(h\), \(\widehat c_h\geq1\), and
\(\displaystyle E_g(\widehat c_h)=b_g,\qquad E_g(\widehat c_h+1)=a_g,\)
whenever the latter round exists.
Here is the key rounding check. If \(r_gq^*\) is a cumulative type mass, then its packet count
\(\displaystyle J_g=\frac{r_gq^*}{h}\)
is an integer. The definition of \(\widehat c_h\) gives
\(\displaystyle r_g\widehat c_h+1\leq J_g<r_g(\widehat c_h+1)+1.\)
Thus the two queried ranks lie on opposite sides of the breakpoint. If \(r_gq^*\) lies inside a type, both ranks lie inside that type for sufficiently small \(h\). Finite support supplies a positive distance to every other relevant breakpoint, justifying these statements simultaneously across categories.
There is one initialization case to check: \(q^*=Q\) and \(Q/h\) is nonintegral. Then \(\widehat c_h\) is the initial target. Capacity-attaining categories start at \(-\infty=a_g\). Every other category is oversized for sufficiently small \(h\); initialization leaves \(r_g(\widehat c_h+1)-1\) packets, and its price is \(w_g(r_g(\widehat c_h+1))=a_g\). Hence this round also starts at the vector \(a\).
Therefore the round preceding \(\widehat c_h\) has negative endpoint sum, while round \(\widehat c_h\) has nonnegative endpoint sum. It follows that, for all sufficiently small \(h\),
\(\displaystyle c_h=\widehat c_h,\qquad p^{(h)}=p^*.\)
The price vector is therefore eventually constant, rather than merely convergent. This also shows independence from the chosen common denominator and from the exit order within a type.
Write \(q_h=c_hh\). The preceding formula implies
\(\displaystyle q^*-h\leq q_h<q^*.\)
In category \(g\), the remaining packets include the highest \(r_gc_h\) packets, with at most \(r_g\) additional packets. Comparing uniform selection with selecting exactly those highest packets gives
\(\displaystyle \sum_v\left|x^{(h)}_{g,v}-z_{g,v}(q_h)\right|\leq2r_gh.\)
Indeed, both allocations have the same total mass; their distance is at most twice the mass that can be selected from the additional packets.
The top-value allocations are nested as quantity increases. Hence
\(\displaystyle \sum_v\left|z_{g,v}(q_h)-z_{g,v}(q^*)\right|=r_g(q^*-q_h)\leq r_gh.\)
Consequently,
\(\displaystyle \sum_{g,v}|x^{(h)}_{g,v}-x^*_{g,v}|\leq3h\sum_g r_g.\)
Since prices are eventually \(p^*\),
\(\displaystyle t^{(h)}_{g,v}\longrightarrow t^*_{g,v}=p_g^*x^*_{g,v}.\)
If \(q^*=0\), the initial marginal value \(F'_+(0)\) is strictly negative: a positive value contradicts optimality at zero, while zero would give a positive interval of maximizers. For sufficiently small \(h\), the endpoint sum of round \(1\) equals this negative marginal value. The clock therefore makes no trade. Allocations and transfers are eventually zero.
Together with the empty-category case, this proves existence for every society. By construction,
\(\displaystyle \operatorname{GFT}(x^*)=F(q^*)=\operatorname{OPT}.\)
For \(q^*>0\), feasibility and price balance imply
\(\displaystyle \sum_{g,v}t^*_{g,v}=q^*\sum_g r_gp_g^*=0.\)
Thus the limiting outcome is strongly budget balanced. Each finite trading realization also has this identity, since it selects exactly \(r_gc_h\) packets per category.
Individual rationality follows because every selected packet has value at least its category price. Passing to the limit gives
\(\displaystyle (v-p_g^*)x^*_{g,v}\geq0.\)
For pointwise incentives, consider an infinitesimal trader whose deviation leaves the aggregate clock unchanged, as stipulated in the question. Its final category price is therefore fixed.
When \(q^*>0\):
Any alternative exit strategy produces a trading probability \(\beta\in[0,1]\), giving utility per unit \(\beta(v-p_g^*)\). This cannot exceed \(\max\{0,v-p_g^*\}\), which truthful behavior attains. When \(q^*=0\), the aggregate outcome makes no trade, so an aggregate-invariant deviation also yields zero utility.
This proves pointwise incentive compatibility under the specified notion.
Let \(B_r=\sum_g\lceil\log_2(r_g+1)\rceil\) denote the recipe encoding length. All computations below use the support representation.
For the divisible outcome, sort values within categories and form normalized cumulative-mass breakpoints. Sweeping these breakpoints computes \(F\) and its largest maximizer \(q^*\); the formulas above then compute allocations and prices. This takes
\(\displaystyle O\bigl(\tau\log(\tau+1)+m\bigr)\)
exact rational arithmetic operations, with polynomial bit complexity in \(m,\tau,L,B_r\).
For an arbitrary refinement, compute the integer type counts \(\mu_{g,v}/h\). The endpoint sums \(\sum_g r_gE_g(c)\) are monotone, so binary search finds the stopping round, or establishes no trade. A rank lookup uses cumulative type counts, and the stopping round can then be reconstructed in public order, including the single exit at a coincident balance event.
The expected masses and payments can therefore be computed using
\(\displaystyle O\bigl(\tau\log(\tau+1)+m\log(\tau+1)\log(1/h+1)+m\bigr)\)
arithmetic operations. Operand lengths, and hence total bit complexity, are polynomial in \(m,\tau,L,B_r,\log(1/h)\). In particular, these bounds have no dependence on the number of possible unsupported types or a linear dependence on recipe magnitudes.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is established. The argument proves existence of the allocation and payment limits, exact optimality of the limiting allocation, and the three stated economic properties. The finite-refinement error bound and polynomial computation claims also withstand verification. I found no major or minor issues requiring correction.
For fixed quantity \(q\), the highest-value allocation \(z(q)\) is optimal: an exchange of equal amounts within a category preserves feasibility and weakly increases gains from trade when it replaces a lower value with a higher value.
The resulting function \(F\) is continuous, concave, and piecewise linear. Its domain \([0,Q]\) is compact, so its largest maximizer \(q^*\) exists. Defining the target allocation as \(z(q^*)\) is therefore valid.
Empty categories are handled correctly: their feasibility constraint forces \(q=0\), and every refinement has initial capacity zero.
The remaining-count bounds \(r_gc\leq K_g\leq r_g(c+1)\) are correct. Initialization gives the strict upper bound; subsequent rounds begin with the previous round’s exact target counts. The lower bound survives the stipulated exit-before-stop convention because the processed exit cannot take the count below the current target.
At balance, all prices are finite. Increasing-value exits imply that exited packets have value at most their final category price, while remaining packets have value at least that price. These statements remain valid with ties.
The price-based upper bound on the optimum is valid for signed values and payments. The price term cancels for every feasible allocation because category quantities are proportional to the recipe and the weighted price sum is zero.
The identity between total positive surplus and remaining-packet surplus is also correct: every packet with strictly positive surplus remains, and remaining packets with zero surplus contribute nothing. Uniform selection then gives the stated expected-surplus expression.
Each inequality in the error bound is justified. In particular, \(K_g-r_gc\leq r_g\), and \(V_g-p_g\geq0\) because each category has remaining packets. The final cancellation gives precisely \(hA\).
For no-trade refinements:
The deduction \(\operatorname{OPT}>0\Rightarrow A>0\) is valid. Thus the stated relative approximation bound is meaningful throughout its claimed domain.
For \(q^*>0\), the one-sided marginal values \(a_g,b_g\) are well defined.
Optimality implies that the left marginal sum is nonnegative. The right marginal sum is strictly negative when \(q^*<Q\): a positive sum contradicts optimality, and a zero sum contradicts selection of the largest maximizer. At \(q^*=Q\), the extended-real convention correctly supplies a negative-infinite right marginal sum.
The sums \(B_j\) are nondecreasing. Their first nonnegative index therefore exists. At that index, all prices occurring in the displayed balancing formula are finite. The inequalities \(a_k<p_k^*\leq b_k\) follow from the adjacent weighted sums, including when \(a_k=-\infty\).
The construction correctly describes the first balance encountered while raising coordinates in the public order.
The completed-round endpoint formula \(E_g(c)=w_g(r_gc+1)\) is correct, including initial categories that retain price \(-\infty\).
The central rounding argument is valid. When \(r_gq^*\) is a cumulative type mass, its packet count \(J_g\) is an integer under every specified refinement. With \(\widehat c_h=\lceil q^*/h\rceil-1\), the two queried ranks lie on the claimed sides of this breakpoint.
If the cutoff lies inside a type interval, both queried ranks eventually remain inside that interval. Finite support permits one sufficiently small refinement threshold to work simultaneously for every category.
The exceptional initialization case is handled correctly. Capacity-attaining categories retain \(-\infty\), while other categories eventually undergo initialization exits and attain the stated \(a_g\) prices.
Monotonicity of endpoint sums then identifies the stopping round. Public coordinate order identifies the balancing prices. Tied exits affect counts within that round but do not invalidate the price vector. Consequently, eventual equality \(p^{(h)}=p^*\) is established.
The quantity estimate \(q^*-h\leq q_h<q^*\) follows directly from the stopping-round formula.
The allocation comparison is valid: the remaining packets contain the highest target number of packets and at most \(r_g\) additional packets. Uniform selection can therefore differ from the highest-value allocation by at most \(2r_gh\) in total absolute mass. Equal-valued packets cause no problem because the comparison concerns type masses.
Nested highest-value allocations give the second distance estimate. Together these prove allocation convergence. Eventual price equality then proves payment convergence.
The case \(q^*=0\) is correctly distinguished. Its initial marginal sum must be strictly negative, and sufficiently fine refinements consequently make no trade. This also establishes convergence in zero-optimum societies whose largest maximizer is zero.
Thus existence is proved for every society, including zero-optimum and empty-category cases.
Strong budget balance holds in every trading realization because each category trades exactly its recipe multiple of the common quantity. It therefore holds for expected payments and their limit.
Individual rationality follows from the remaining-packet value inequalities and passes to the limit.
The pointwise incentive argument uses exactly the task’s aggregate-invariant deviation assumption. Under that assumption, the final price and aggregate settlement remain fixed. Truthful behavior attains full limiting trading probability when the trader has strictly positive surplus, zero utility when it has negative surplus, and zero utility under any allocation when surplus is zero. No alternative trading probability can improve these utilities.
The claim is therefore proved under the specified pointwise notion.
The divisible computation uses sorting, cumulative masses, and a sweep of normalized breakpoints. The claimed arithmetic-operation count is consistent with these operations.
For refinements, monotone endpoint sums permit binary search over the round index. Rank queries use cumulative type counts, and reconstruction of the stopping round can process tied blocks without enumerating packets individually. The stated operation bound is consistent with this support-based implementation.
The rational quantities and integer counts involved have polynomial encoding lengths in the stated parameters. No step requires expansion proportional to recipe magnitudes or packet counts.
The cited finite-agent result is contextual; the proof does not depend on an unverified application of that theorem. All requested conclusions are addressed, and no clarification is needed.
⟨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.