| paper | d4-journals-geb-2022-0004 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.1
statement extracted from the paper’s text layer
For fixed \(k\), take a rational mass of identical copies of the paper's two-bidder instance \(\mathcal I_k\), with \(m=2^k-1\) local items per copy, and synchronize copies at the same bid profile and update step. Under local best-response dynamics that do not overbid on the grand bundle, must aggregate welfare be at most \(O(\log\log m/\log m)\) times aggregate optimum in infinitely many rounds?
Each unit of mass is a local auction room with two bidder roles, the valuations and tie-breaking of \(\mathcal I_k\), and integral local allocations. A room state records both bidders' bids and the update position; mass moves only along permitted local best-response transitions. Aggregate welfare and optimum are the mass-weighted sums of the corresponding room quantities.
The bound transfers only for synchronized independent rooms, so it does not address shared-item competition or yield a support-sensitive algorithmic gain; the proponent confines the proposed mirror to repeated local markets.
fatal: False
The mirror covers Theorem 4.1 and, as a companion, Theorem 3.1. It leaves the average-welfare, randomized-activation, adversarial-activation, equilibrium, and other results without a proposed mirror.
There is a narrow positive case. The paper’s numbered results concern algorithmic welfare guarantees for best-response dynamics, rather than NP-hardness or the complexity of computing equilibria. A continuous mirror can therefore ask whether those guarantees survive when the population consists of many copies of local auctions.
I would model a society as a rational mass distribution \(\mu\) over auction-room templates. Each template specifies \(n\) bidder roles, their valuations, \(m\) local indivisible items, tie-breaking, and the update schedule. A room has one bidder of each role; many rooms repeat the same finite set of roles and templates. The state is a joint distribution over rooms’ bid profiles and next-to-move positions. A legal action moves room mass along transitions where a bidder makes a permitted best response. Aggregate welfare and optimum are the mass-weighted sums of the rooms’ welfare and optima. The joint state matters: role marginals alone do not say which bidders compete against each other. Clearing rational masses gives finitely many rooms, while every allocation inside each room remains integral. In a repeated procurement setting across many districts, for example, \(q\) rooms give \(N=qn\) agents but only \(\tau n\) role types, with local supply scaling along with population size.
My lead is the approximation lower bound in Theorem 4.1, proved in this paper. It says that for every positive integer \(k\), there is an instance \(\mathcal I_k\) with \(n=2\) bidders, \(m=2^k-1\) items, and subadditive valuations such that, in *every* best-response dynamic whose bidders do not overbid on the grand bundle, infinitely many time steps have
\[
SW(b^t)\leq \frac{1}{\Omega(\log m/\log\log m)}\,OPT(v).
\]
The instance is the paper’s vector-space construction: one bidder has a set-cover valuation, and the other values subspaces of \(\mathbb F_2^k\).
The corresponding continuous question is Mass-Room No-Overbid Welfare Barrier. Given \(q\) copies of \(\mathcal I_k\), with mass \(1/q\) on each room and the two bidder roles repeated across rooms, does every admissible synchronized local best-response dynamic have infinitely many rounds with aggregate welfare at most \(O(\log\log m/\log m)\) times aggregate optimum? A solution is a proof of that bound for all such dynamics, or a legal mass trajectory showing that it fails. The theorem’s bad trajectory applies room by room; synchronizing identical copies gives the same aggregate ratio. I expect this welfare barrier to transfer. This is a lower bound on attainable welfare guarantees, not an NP-hardness result.
A useful companion is Theorem 3.1, also proved here and the paper’s strongest positive anchor. It states that in a \(\beta\)-safe round-robin dynamic with \(\alpha\)-aggressive updates, every time \(t\geq n\) satisfies
\[
SW(b^t)\geq \frac{\alpha}{(1+\alpha+\beta)\beta}\,OPT(v).
\]
The paper obtains \((\alpha,\beta)=(1,1)\) for fractionally subadditive valuations, giving a \(1/3\) guarantee, and \((1/\ln m,1)\) for subadditive valuations, giving an \(\Omega(1/\log m)\) guarantee.
Its mirror, Mass-Room Round-Robin Welfare, takes rational masses over room templates satisfying those update conditions. It asks whether, after every room has completed one local round, aggregate welfare is at least the same fraction of aggregate optimum. A solution is a proof of that uniform bound or a counterexample mass trajectory. The expected result is the same guarantee: applying Theorem 3.1 in each room and summing preserves it. This is the tractable side of the proposed mirror, though the theorem assumes the best-response updates can be carried out; it does not itself give an algorithm for computing equilibria.
The scope is these two dynamic welfare results. The paper’s discussion of equilibrium computation and allocation hardness does not provide additional numbered results to anchor here. The main weakness is the market structure: mass represents repeated local auctions, with their grouping preserved, rather than many bidders competing for one shared inventory. The two-bidder lower-bound instance becomes a high-multiplicity population across rooms, but not a large single auction. Authors working on repeated or geographically separated auctions could recognize this as their dynamic problem in a population regime; a referee requiring one common market may judge it an adjacent extension instead of a direct mirror.
I would not argue that the paper lacks named results: Theorems 3.1 and 4.1 give genuine guarantees about the welfare produced by best-response dynamics. The harder objection is that the proposed mirrors make the *auction rooms* continuous, while the programme’s central object is a population of agents. That difference determines whether these results yield a support-sensitive computational question.
For Theorem 4.1, the proposed copies of \(\mathcal I_k\) are independent two-bidder auctions with separate items. If their dynamics are synchronized, the aggregate lower bound follows by applying the theorem in each room and adding the welfare and optima. That establishes a valid fact about repeated local auctions, but adds no mass-transfer or algorithmic problem: the result is inherited room by room. If rooms are asynchronous, the state needed to track the argument includes each room’s bids and activation phase. The support is then a distribution over whole auction states, not a compressed distribution over bidder types.
The stronger version would put many copies of the two bidder roles into one shared auction, with supply scaled alongside the population. That changes the construction in a consequential way. The proof finds a cheap subspace using one bidder’s grand-bundle bid bound; in a shared market, the price of each item is the maximum across all opposing bidders. Different copies can set those maxima on different items, so the original averaging argument does not establish a cheap subspace at the prices a bidder faces. A new shared-market lower bound might be interesting, but it would need a new construction and would be a result about a modified game, not a continuous lift of Theorem 4.1.
Theorem 3.1 has the same divide. Across synchronized, independent rooms, summing the per-room guarantees gives the aggregate guarantee directly. In one market with many bidders, however, the theorem’s round-robin premise requires visiting every individual bidder. A finite continuum step cannot update one agent at a time while changing positive population mass; updating a positive mass together changes the price environment during the move, which the theorem does not model. A continuous-time or batch-update dynamic could be defined, but it would be a new dynamic whose welfare guarantee needs its own analysis. Nor does Theorem 3.1 itself provide a support-size algorithm for that model.
So the strongest negative case is about fit and payoff: the room mirrors are straightforward averages, while the shared-market versions lose the paper’s interaction and timing assumptions. Neither anchor, as proposed, exposes the kind of computational landscape the programme is built to chart. This case is not airtight. Repeated auctions across many districts are a plausible high-multiplicity regime, and researchers in that setting might value aggregate welfare guarantees. The negative argument is strongest as a reason to treat these mirrors as lower priority or outside ChoCo’s central population-complexity gap—not as proof that no worthwhile mirror exists.
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.