| paper | d4-conf-wine-2017-0030 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
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. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
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.
Buyer and seller reservation-value types carry rational masses. A posted price admits types above or below its threshold, and uniform rationing selects equal traded mass when eligible masses differ. Compare the resulting gain from trade with the maximum-weight feasible fractional matching.
A finite-support mass measure can have a jump across which buyer demand and seller supply switch order without ever being equal; allowing a fractional boundary type at \(p\) does not handle every such gap.
fatal: False
This mirrors the large-market double-auction performance result in Theorem 5.2; it leaves the bilateral-trade approximation results and the paper’s other bounds untouched.
The strongest mirror is Section 5’s large-market double auction result, not the paper’s bilateral-trade results.
Anchor: Theorem 5.2, proved in this paper. The authors consider \(n\) buyers with independent valuations drawn from a common distribution and \(m\) sellers whose independent valuations come from another common distribution. Their balanced fixed-price mechanism chooses \(p\) so that buyer demand and seller supply balance, \(nF(p)=mG(p)\), where \(F\) is the buyers’ valuation survival function and \(G\) the sellers’ CDF. Theorem 5.2 says that for every \(\varepsilon\in[0,1]\), with probability at least \(1-2e^{-\#T\varepsilon^2/2}\), the mechanism’s realized gain from trade is at least \(1-\varepsilon\) times the expected optimal gain from trade; \(\#T\) is the mechanism’s expected number of trades. The paper proves this using concentration bounds and properties of the optimal allocation.
The paper has named approximation and mechanism-performance results, but no numbered result classifying a problem as being in P, NP-hard, FPT, or similar. So this is an algorithmic performance anchor, not a hardness anchor.
The mirror: Balanced-Price Continuum GFT. An instance consists of two finite-support rational mass measures: \(\nu_B(v)\) over buyer values and \(\nu_S(w)\) over seller values. A type is a buyer or seller together with its per-unit value and unit-demand or unit-supply role. The measures give the mass of each type; all agents of a type are otherwise identical.
A feasible mass-trade plan is a matrix \(\pi_{vw}\ge 0\), with buyer and seller margins bounded by their available masses, and \(\pi_{vw}=0\) whenever \(v<w\). Its gain from trade is
\[
\mathrm{GFT}(\pi)=\sum_{v,w}(v-w)\pi_{vw}.
\]
The benchmark is the maximum over all feasible plans, \(\mathrm{OPT}_\infty\).
The question is: given \(\nu_B,\nu_S\), compute a clearing price \(p\) with
\[
\sum_{v\ge p}\nu_B(v)=\sum_{w\le p}\nu_S(w),
\]
and the resulting threshold trade plan \(\pi_p\); determine whether \(\mathrm{GFT}(\pi_p)=\mathrm{OPT}_\infty\), and return the exact efficiency ratio. If atoms prevent exact balance by admitting every type strictly above or below \(p\), the mechanism may admit a fraction of the type at \(p\). This is a fraction of a type’s mass: individual buyers and sellers still receive integral trade decisions. The output is a price, accepted mass by type, a feasible matching of that mass, and an optimality certificate or counterexample.
I expect this problem to be tractable, and the balanced-price plan to be optimal in this unit-demand, unit-supply setting. The masses of buyers above the clearing price and sellers below it are equal, and every such trade has nonnegative surplus. The instance can be processed by sorting the supports and scanning cumulative demand and supply; an optimal mass plan can also be constructed by matching the highest remaining buyer values to the lowest remaining seller values until no positive-surplus trade remains. This takes polynomial time in the support sizes and the input bit length. The result would be a Class A structural optimization story, though not a result showing that discrete hardness dissolves.
The regime is a thick market for a homogeneous good: many buyers and sellers with values from a fixed or moderate set of reservation-value bands. For example, many buyers and sellers in a repeated commodity exchange may share one of a small number of reservation values. As the market scales by \(K\), each positive-mass type has \(\Theta(K)\) agents while the number of types stays fixed. This is the high-multiplicity regime: the type records all relevant differences, while type-level trade masses can be fractional even though agents’ outcomes are integral.
The proposed mirror is specifically for Theorem 5.2. The paper’s bilateral-trade results concern one buyer and one seller, so they provide no corresponding thick-population anchor. The finite-market theorem motivates the continuum question: when the market grows, \(\#T\) grows and its failure probability decays exponentially. A limit argument for bounded, finite-support valuations would connect the random empirical type masses to deterministic population masses. The continuum question itself asks whether the balanced price is exactly efficient.
The soft spot is that the paper treats \(f\) and \(g\) as priors over randomly realized values, whereas the mirror treats type proportions as the society itself. In atomless distributions, exact valuation types need not repeat, so the small-support regime is most convincing for markets with shared, quantized reservation values. The theorem does not itself prove the deterministic mass statement; that bridge needs to be established. Still, finite-support priors are a natural instance regime for the paper’s double auction, and its explicit large-market result makes the population-limit interpretation plausible to the authors.
Theorem 5.2 is the one anchor, and it is a real mechanism-performance result. Its substance is about a *finite random market*: buyers and sellers are sampled independently, and the theorem bounds the chance that random imbalances leave too few agents able to trade. It does not pose a computational search or optimization problem. That distinction does not rule out a mirror, but it makes this a less direct ChoCo anchor than a complexity theorem.
There are two ways to carry the model across. If buyers and sellers remain random draws from \(f\) and \(g\), the distributions are priors over a finite market—the paper’s original setup. Increasing market size strengthens the concentration bound already in Theorem 5.2. If instead the distributions describe the actual masses of buyer and seller types, the sampling fluctuations disappear. With a price \(p\) balancing the accepted masses, the threshold plan trades equal mass of buyers with values at least \(p\) and sellers with values at most \(p\). It is efficient: matching a high buyer with a high seller and a low buyer with a low seller cannot beat matching the high buyer with the low seller, since
\[
(v_H-w_L)-\bigl((v_H-w_H)+(v_L-w_L)\bigr)=w_H-v_L\ge 0
\]
when \(v_L<p<w_H\). Thus the proposed equality test has the same answer on every instance, and sorting the supports computes the price and plan. The paper’s nontrivial concentration phenomenon has vanished in the mass limit.
That leaves a plausible but low-yield continuous question: characterize the mass limit and its finite-size convergence. The theorem itself already points toward that limit, while the deterministic computation is a one-dimensional clearing calculation. Replicating the bilateral-trade results into buyer and seller populations does not restore their original question: with actual masses, it becomes deterministic matching by value order; with random finite agents, it returns to the paper’s sampling model.
The finite-support market story is nevertheless a strong high-multiplicity regime: repeated reservation-value types are plausible, and the paper’s large-market setting directly motivates it. So I cannot honestly claim that no worthwhile mirror exists. My negative case is that this anchor’s computational content is thin: its interesting object is finite-sample randomness, which either remains the paper’s model or disappears in the continuous population. A reader who counts a simple, informative limit result as worthwhile can still reasonably green it.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.