Answer: The sharp infimum is \(0\), and it is not attained when \(\mathrm{OPT}>0\). Writing \(d=D(p)\), \(s=S(p)\), \(a=D_>(p)\), and \(c=\sum_{w<p}\nu_S(w)\), exactly the instances satisfying \(d=s\), or \(d>s\) and \(a=0\), or \(s>d\) and \(c=0\), have \(R=1\). For \(m=1\), the crossing price, gain, optimum, and ratio are exactly computable in \(O(\tau\log(\tau+1)L^2)\) bit operations.
Theorem 5.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor all ǫ ∈[0, 1], with probability at least 1 −2/e#Tǫ2/2, the balanced fixed price double auction achieves a gain from trade that is at least (1 −ǫ) times the expected optimal gain from trade. Note that #T, the expected number of trades of the balanced fixed price double auction, needs to exceed 2 ln(2)/ǫ2 by any constant for the above theorem to yield a constant approximation guarantee. The value #T can be regarded as a property of the instance (n, m, f, g) on which the mechanism is run, and is equal to the value where the functions nF and mG cross each other.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite-support rational buyer and seller mass measures, find a generalized crossing price for \(D(p)=\sum_{v\ge p}\nu_B(v)\) and \(S(p)=\sum_{w\le p}\nu_S(w)\). At a jump, trade the smaller eligible mass and uniformly ration the excess side, allowing fractional mass within types. Compute this mechanism’s exact gain from trade and its ratio to the optimum fractional matching value \(\max_{\pi}\sum_{v,w}(v-w)\pi_{vw}\), subject to the type-mass capacities and \(\pi_{vw}=0\) when \(v<w\); determine when the ratio is one.
There is one homogeneous good (\(m=1\)); buyers have unit demand and sellers unit supply. Buyer and seller types have nonnegative rational valuations \(v,w\) and positive rational masses \(\nu_B(v),\nu_S(w)\). Both sides are nonempty; their total masses may differ and need not sum to one.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here types include their buyer/seller role; \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Define \(D(p)=\sum_{v\ge p}\nu_B(v)\), \(S(p)=\sum_{w\le p}\nu_S(w)\), and \(D_>(p)=\sum_{v>p}\nu_B(v)\). Choose the generalized crossing price \(p=\min\{x\ge0:D_>(x)\le S(x)\}\).
At this price all weakly eligible types participate. Trade mass \(t=\min\{D(p),S(p)\}\); if \(t>0\), each eligible buyer type trades fraction \(t/D(p)\) of its mass and each eligible seller type fraction \(t/S(p)\). Pair these traded masses arbitrarily, with payment \(p\) per unit; if \(t=0\), no trade occurs. Let \(G\) be the resulting total gain from trade.
The benchmark is \(\mathrm{OPT}=\max_{\pi\ge0}\sum_{v,w}(v-w)\pi_{vw}\), subject to \(\sum_w\pi_{vw}\le\nu_B(v)\), \(\sum_v\pi_{vw}\le\nu_S(w)\), and \(\pi_{vw}=0\) for \(v<w\). Write \(R=G/\mathrm{OPT}\) when \(\mathrm{OPT}>0\), and set \(R=1\) otherwise.
What is the sharp worst-case approximation ratio \(\inf_{\mathrm{OPT}>0}R\) of this mechanism, and exactly which instances have \(R=1\)? Can its crossing price, gain \(G\), and ratio \(R\) be computed exactly in polynomial time in \(m,\tau,L\)?
For finite markets with independent identically distributed valuations on each side, the published balanced-price guarantee states that gain is at least \((1-\varepsilon)\) times expected optimal gain with probability at least \(1-2\exp(-T\varepsilon^2/2)\), where \(\varepsilon\in[0,1]\) and \(T\) is the common expected eligible count. [Source](https://www.cs.ox.ac.uk/people/paul.goldberg/papers/WINE2017-procs-paper.pdf).
No result settling this exact deterministic mass mechanism with uniform rationing at atoms was located.
The sharp worst-case approximation ratio is \(0\). Every individual instance with \(\mathrm{OPT}>0\) has \(R>0\), so the infimum is not attained.
There is also an exact characterization of all instances with \(R=1\), including those covered by the convention for \(\mathrm{OPT}=0\). The crossing price, gain, optimum, and ratio can all be computed exactly in polynomial time.
Define the strictly eligible masses and the masses at the crossing price by
\(a=\sum_{v>p}\nu_B(v),\qquad b=\sum_{v=p}\nu_B(v),\qquad c=\sum_{w<p}\nu_S(w),\qquad e=\sum_{w=p}\nu_S(w).\)
Write \(d=D(p)=a+b\) and \(s=S(p)=c+e\), so \(t=\min\{d,s\}\).
First, the minimum defining \(p\) exists. Indeed, \(D_>(x)=0\) whenever \(x\) is at least the largest buyer valuation. Moreover, \(D_>(x)-S(x)\) is a nonincreasing step function whose changes occur only at supported valuations. Consequently, its first nonpositive point belongs to the finite set consisting of \(0\) and all supported valuations.
By the defining crossing condition,
\(a\le s.\)
We also have
\(c\le d.\)
For \(p=0\), this follows from \(c=0\), since valuations are nonnegative. For \(p>0\), choose \(y<p\) sufficiently close to \(p\) that there is no supported valuation in \([y,p)\). Then \(D_>(y)=D(p)=d\) and \(S(y)=c\). Minimality of \(p\) gives \(D_>(y)>S(y)\), hence \(d>c\).
Since also \(a\le d\) and \(c\le s\), these inequalities imply
\(\max\{a,c\}\le t\le\min\{a+b,c+e\}.\)
Thus trade mass \(t\) can accommodate every strictly eligible buyer and every strictly eligible seller, using agents at the price to balance the two sides.
Define the two nonnegative surplus quantities
\(X=\sum_{v>p}(v-p)\nu_B(v),\qquad Y=\sum_{w<p}(p-w)\nu_S(w).\)
Claim. For every instance, \(\mathrm{OPT}=X+Y\).
Upper bound. For a real number \(z\), write \(z_+=\max\{z,0\}\). For every buyer and seller valuation,
\(v-w\le(v-p)_++(p-w)_+.\)
Therefore any feasible allocation \(\pi\) satisfies
\(\sum_{v,w}(v-w)\pi_{vw}\le\sum_v(v-p)_+\sum_w\pi_{vw}+\sum_w(p-w)_+\sum_v\pi_{vw}\le X+Y.\)
The final inequality uses the capacity constraints and the nonnegativity of the coefficients.
Attainment. Suppose first that \(t>0\). Select buyer masses \(x_v\) by taking every buyer with \(v>p\), together with mass \(t-a\) of buyers at \(p\). This is possible because \(0\le t-a\le b\). Similarly, select every seller with \(w<p\), together with mass \(t-c\) of sellers at \(p\), obtaining seller masses \(y_w\).
Both selected sides have total mass \(t\). Define
\(\pi_{vw}=x_vy_w/t.\)
Its row sums are \(x_v\), its column sums are \(y_w\), and every pair with positive mass satisfies \(v\ge p\ge w\). Hence it is feasible. Its gain equals
\(\sum_{v,w}(v-w)\pi_{vw}=\sum_v(v-p)x_v+\sum_w(p-w)y_w=X+Y.\)
If \(t=0\), the crossing inequalities imply \(a=c=0\), so \(X=Y=0\). The upper bound and the feasible zero allocation then give \(\mathrm{OPT}=0\). This proves the claim.
When \(t>0\), uniform rationing selects buyer mass \((t/d)\nu_B(v)\) for each \(v\ge p\), and seller mass \((t/s)\nu_S(w)\) for each \(w\le p\). Because both selected sides have mass \(t\), any pairing has gain
\(G=\dfrac{t}{d}X+\dfrac{t}{s}Y.\)
Thus pairing does not affect total gain. When \(\mathrm{OPT}>0\),
\(R=\dfrac{(t/d)X+(t/s)Y}{X+Y}.\)
In particular,
\(\mathrm{OPT}-G=\left(1-\dfrac{t}{d}\right)X+\left(1-\dfrac{t}{s}\right)Y.\)
Both summands are nonnegative. If \(d=s\), both vanish. If \(d>s\), only the buyer coefficient is positive, so equality holds exactly when \(X=0\). If \(s>d\), equality holds exactly when \(Y=0\).
Because every supported mass is positive, \(X=0\) is equivalent to \(a=0\), and \(Y=0\) is equivalent to \(c=0\). Consequently, the following characterization holds for every instance:
\(R=1\quad\Longleftrightarrow\quad (d=s)\ \text{or}\ (d>s\ \text{and}\ a=0)\ \text{or}\ (s>d\ \text{and}\ c=0).\)
Equivalently:
To check the zero-optimum convention explicitly: \(\mathrm{OPT}=0\) implies \(X=Y=0\), hence \(a=c=0\), so one of these three conditions holds. If \(t=0\), the same conclusion follows from the crossing inequalities. Thus the characterization includes all degenerate cases.
The gain formula gives \(G\ge0\), so \(R\ge0\). Moreover, if \(\mathrm{OPT}>0\), then \(X+Y>0\). A positive \(X\) implies \(a>0\), and a positive \(Y\) implies \(c>0\). Since \(t\ge\max\{a,c\}\), it follows that \(t>0\); both rationing fractions are positive. Hence \(G>0\) and \(R>0\).
Nevertheless, ratios approach zero even with strictly positive valuations and equal total masses. For each positive integer \(N\), consider:
| Role | Valuation | Mass |
|---|---:|---:|
| Buyer | \(2\) | \(N\) |
| Buyer | \(N+2\) | \(1\) |
| Seller | \(1\) | \(1\) |
| Seller | \(N+3\) | \(N\) |
For \(0\le x<1\), we have \(D_>(x)=N+1>S(x)=0\). For \(1\le x<2\), we have \(D_>(x)=N+1>S(x)=1\). At \(x=2\), both quantities equal \(1\). Therefore \(p=2\).
At this price,
\(d=N+1,\qquad s=t=1,\qquad X=N,\qquad Y=1.\)
The proved formulas give
\(\mathrm{OPT}=N+1,\qquad G=\dfrac{N}{N+1}+1,\qquad R=\dfrac{2N+1}{(N+1)^2}.\)
Since \(R\le 2/(N+1)\), these ratios tend to zero. Thus
\(\inf_{\mathrm{OPT}>0}R=0.\)
Each side has total mass \(N+1\). Scaling all masses by \(1/(N+1)\) gives total mass \(1\) on each side and preserves the crossing price and ratio. The example therefore also establishes the zero infimum under separate normalization of the two sides.
For the promised case \(m=1\), use the following algorithm:
This uses \(O(\tau\log(\tau+1))\) comparisons and arithmetic operations.
For an explicit bit bound, let \(Q\) be the product of all input denominators, including valuation and mass denominators. Its bit length is \(O(L)\). Represent each input rational as an integer divided by \(Q\). All scaled integers, mass sums, and surplus numerators have \(O(L)\) bits: summation adds at most \(O(\log\tau)\) bits, and \(\tau\le L\). Surpluses have common denominator \(Q^2\), and the gain and ratio formulas require only a constant number of further arithmetic operations on \(O(L)\)-bit integers.
Using schoolbook integer arithmetic, a valid exact running-time bound is
\(O\!\left(\tau\log(\tau+1)L^2\right)\)
bit operations for \(m=1\). Thus computation is polynomial in \(m,\tau,L\) on the stated domain; this makes no claim for multiple goods.
Definition 3 and Theorem 4 of the [cited paper](https://www.cs.ox.ac.uk/people/paul.goldberg/papers/WINE2017-procs-paper.pdf) concern a price balancing expected eligible counts in an independent sampling model, with a probability guarantee relative to expected optimal gain.
The generalized crossing here permits unequal weakly eligible masses at atoms. The proved gain formula identifies exactly how that imbalance reduces deterministic gain; the four-type family demonstrates that the reduction can be arbitrarily severe.
⟨structured verdict parsed — rendered above⟩
The output resolves all parts of USER_TASK. The deterministic argument is correct, covers the degenerate cases, and establishes the claimed polynomial running time. I found no major or minor mathematical issues.
The existence argument is valid. The support is finite, and \(D_>(x)=0\) once \(x\) reaches the largest buyer valuation. Thus the crossing condition eventually holds.
The assertion that the first crossing occurs at \(0\) or a supported valuation is also correct. Both functions are constant between supported valuations; at a supported valuation, the strict buyer tail excludes buyers at that value and the weak seller tail includes sellers at that value. Consequently, the post-jump values are already attained at the jump, so the first nonpositive point is included.
The inequality \(a\le s\) is exactly the defining crossing condition.
The proof of \(c\le d\) correctly handles both cases:
Combining these inequalities with \(a\le d\) and \(c\le s\) correctly yields
\[
\max\{a,c\}\le t.
\]
The displayed upper bound on \(t\) is equality by its definition. These inequalities justify the later selection of all strictly eligible masses.
The upper-bound argument is correct. The pointwise inequality
\[
v-w\le (v-p)_+ +(p-w)_+
\]
holds for every pair of valuations. Multiplication by nonnegative allocation masses and summation preserve it. The capacity constraints apply because the coefficients are nonnegative, giving the claimed bound \(\mathrm{OPT}\le X+Y\).
The attainment argument establishes every necessary condition:
For \(t=0\), the inequalities imply \(a=c=0\), and hence \(X=Y=0\). Together with the upper bound and feasible zero allocation, this proves \(\mathrm{OPT}=0\).
Thus \(\mathrm{OPT}=X+Y\) is established for every allowed instance.
For \(t>0\), both \(d\) and \(s\) are positive, so the rationing fractions are defined. The gain calculation correctly depends only on the traded marginal masses: both sides trade total mass \(t\), causing the price terms to cancel. Arbitrary pairing therefore does not change total gain.
The formulas for \(G\), \(R\), and \(\mathrm{OPT}-G\) follow correctly.
The equality analysis is exhaustive:
Because the support is finite and every supported mass is positive, each strictly eligible type makes a strictly positive contribution to its respective surplus. Thus \(X=0\) is equivalent to \(a=0\), and \(Y=0\) is equivalent to \(c=0\).
The zero-optimum convention is explicitly and correctly incorporated. When \(\mathrm{OPT}=0\), both surpluses vanish, so \(a=c=0\), and one of the three stated conditions necessarily holds. The proof does not use an undefined rationing fraction when \(t=0\).
The claimed characterization of every instance with \(R=1\) is therefore correct.
The positivity argument is valid. If \(\mathrm{OPT}>0\), at least one surplus is positive, so at least one of \(a,c\) is positive. The crossing inequalities then imply \(t>0\). Both rationing fractions are positive, and consequently \(G>0\).
The four-type family satisfies all input requirements for every positive integer \(N\), including positivity of masses and nonnegativity of valuations.
The crossing calculation is correct: the condition fails throughout \(0\le x<2\) and holds at \(x=2\). At that price, the stated values of \(d,s,t,X,Y\) are correct.
Rechecking the arithmetic confirms
\[
\mathrm{OPT}=N+1,\qquad
G=\frac{N}{N+1}+1,\qquad
R=\frac{2N+1}{(N+1)^2}.
\]
The bound \(R\le 2/(N+1)\) holds for every positive integer \(N\), proving convergence to zero.
Therefore the infimum is zero and is not attained on instances with positive optimum. The equal-total-mass assertion and invariance under common positive scaling are also correct.
The algorithm computes the specified crossing price. Grouping equal valuations permits simultaneous treatment of buyer exclusions and seller inclusions at each candidate, preserving the required strict and weak inequalities.
The remaining quantities are finite rational sums followed by a constant number of rational operations. The branches for \(t=0\) and \(\mathrm{OPT}=0\) correctly avoid division by zero.
The explicit bit bound is justified:
Schoolbook arithmetic therefore supports the stated bound \(O(\tau\log(\tau+1)L^2)\). Its restriction to \(m=1\) matches the promised domain; no multiple-good result is needed.
The description of Definition 3 and Theorem 4 agrees with the [cited paper](https://www.cs.ox.ac.uk/people/paul.goldberg/papers/WINE2017-procs-paper.pdf): the price balances expected eligible counts, and the probability guarantee compares realized gain with expected optimal gain.
The prover uses this citation only for context. None of the deterministic conclusions depends on applying that theorem, so there is no missing verification of theorem hypotheses in the main argument.
No repair or additional clarification is required. The output establishes the sharp ratio, the complete equality characterization, and exact polynomial-time computation.
⟨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.