| paper | d4-conf-aaai-2018-1091 |
| 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: \(\text{Polynomial-time solvable with exact optimal GFT}\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given finitely many buyer and seller types with rational masses \(\mu_t\), capacity at most \(M\), and explicit rational DMR valuation tables over integral quantities \(q\in\{0,\ldots,M\}\), compute a price \(p\) and allocation masses \(x_{t,q}\). Require \(\sum_q x_{t,q}=\mu_t\), equal total quantities bought and sold, and that every assigned quantity maximizes its type’s gain at \(p\); among such allocations, maximize total GFT.
A nonatomic single-good market with finite support of complete buyer and seller types. Each type’s mass is split among agents receiving whole quantities \(q\in\{0,\ldots,M\}\); the objective is to maximize total GFT subject to balanced trade and a supporting price \(p\).
The continuous input has no population size \(N\), so the question cannot capture Theorem 3’s finite-market error rate; atomlessness removes the sampling and rationing effects that theorem analyzes.
fatal: False
Covers the limiting total-GFT question behind Theorem 3 for Lottery-MUDA and Vickrey-MUDA. It does not cover finite-market sampling rates, Vickrey-MUDA’s agents-GFT, or the truthfulness and budget-balance guarantees.
The strongest anchor is Theorem 3, proved in this paper in §5. It says that the expected *total* gain from trade of both Lottery-MUDA and Vickrey-MUDA is at least a \(1-O(M\sqrt{\ln k/k})\) fraction of maximum total GFT. Here \(k\) is the number of units traded in an optimal allocation, and \(M\) is the maximum number of units any one buyer or seller can trade. The expectation is over the mechanism’s randomization. In particular, with \(M\) fixed and \(k\) growing, the guarantee approaches the optimum. This is an approximation result for a computed mechanism, not a theorem classifying a problem as NP-hard or in P; the paper gives no such named complexity classification.
The mirror I would put to a prover is Continuous MUDA Market Clearing. An instance is a finite support \(T\) of buyer and seller types with rational masses \(\mu_t>0\), summing to \(1\). A type completely specifies its side, inventory or capacity (at most \(M\)), and its explicit rational valuation table over integral quantities, with decreasing marginal returns. A solution gives a price \(p\) and allocation masses \(x_{t,q}\): the mass of type \(t\) assigned an *integral* trade quantity \(q\). The masses assigned to each type must sum to \(\mu_t\), and total units bought must equal total units sold. Among such balanced allocations, the solution must maximize total GFT; at the price, each assigned quantity must maximize that type’s gain, allowing a split of mass among tied quantities. Thus a fractional \(x_{t,q}\) means that a fraction of otherwise identical agents receives bundle \(q\), not that an individual receives a fractional unit.
This is a natural limit of the paper’s market-halving construction. The mechanism randomly divides traders into two markets and posts each market the other market’s equilibrium price. In an atomless population, each type’s mass can be split exactly in half, so both halves have the same type distribution and the same equilibrium price. They clear at that price; there is no long side left to ration. For DMR valuations, the continuous allocation can be computed by sorting the buyers’ marginal values and sellers’ marginal costs, then matching the positive-surplus mass, splitting mass at ties as needed. With valuation tables explicit in the input, this is polynomial in \(\tau\), \(M\), and the input bit length \(L\).
The regime is a large single-good market with \(N\) traders, a fixed menu of \(\tau\) complete valuation types, and bounded per-trader capacity \(M\). Each supported type occurs many times—say, \(\Theta(N)\) times—and the market has \(k=\Theta(N)\) units of optimal trade. One plausible setting is a recurring wholesale market where standardized tariffs, technologies, and capacity classes produce repeated DMR schedules for many small buyers and sellers. Mass is the fraction of traders of each type; the allocation can divide that mass among agents receiving different *whole* quantities. These assumptions matter: if nearly every trader has a unique schedule, then \(\tau\) grows with \(N\); if \(k\) stays small, Theorem 3 gives no convergence. The authors’ own focus on large markets and bounded concentration makes this a recognizable extension of their question.
I expect this mirror to be Class A, tractable. It asks whether the finite randomized mechanism’s total-GFT guarantee reaches exact market clearing in the high-multiplicity limit, and how to compute that limiting allocation. Theorem 3’s rate predicts the answer as \(k\) grows with fixed \(M\). This mirror covers that efficiency result, especially the Lottery-MUDA case, where strong budget balance makes agents’ GFT equal total GFT. It does not claim that Vickrey-MUDA’s agents’ GFT approaches the optimum: the paper’s guarantee is for total GFT, and its fees can leave agents with much less.
The weakest point is that this limit removes much of the strategic difficulty: a single agent of zero mass cannot move the price, so truthfulness becomes price-taking behavior, and exact market clearing is simpler than finite MUDA’s long-side problem. Also, exact repeated valuation schedules are a restrictive type regime. I still think the mirror is worth asking because it tracks the population-size and market-concentration limit that Theorem 3 itself studies. Theorem 1’s bilateral setting is not part of this mirror: one buyer and one seller provide no high-multiplicity regime.
Theorem 3 is the strongest anchor, but the proposed Continuous MUDA Market Clearing mirror drops the feature that makes that theorem interesting. The theorem analyzes finite random partitions: the two submarkets get different samples, their prices can differ, and material balance can force rationing. In an atomless society, each type splits exactly across the two halves. Both halves have the same type distribution and equilibrium price, so the sampling and rationing effects disappear. A distribution \(\mu\) alone also contains no population size \(N\), which is needed to ask for a finite-market approximation rate. Put \(N\) back in, and the question is about the high-multiplicity discrete market whose finite-size guarantee Theorem 3 already studies.
The remaining continuous computation is straightforward for the proposed input. Expand each explicit DMR valuation table into its marginal values, give each value the mass of its type, sort buyers’ marginal values and sellers’ marginal costs, and match the positive-surplus mass. Split mass at the boundary if needed. This computes an optimal balanced allocation and an equilibrium price in time polynomial in \(\tau\), \(M\), and the input bit length. The paper itself already points to the Walrasian mechanism: DMR gives an equilibrium, and the first welfare theorem gives maximal GFT. The continuous formulation supplies a clean mass-based description, but no substantial computational question remains to classify.
Keeping MUDA’s truthful-mechanism requirement does not restore one. A single agent has zero mass and cannot move the equilibrium price; the individual incentive constraint reduces to choosing the best quantity at a fixed price. Treating an entire positive-mass cohort as a strategic player would preserve market power, but that changes individual DSIC into a coalition or bloc-proofness question.
This is a strong case against this mirror’s value for ChoCo, but it is not an airtight argument that no worthwhile mirror exists. Someone could study sharper finite-population error bounds, though that work would retain \(N\) and build on the paper’s existing approximation analysis rather than pose a new computational problem over a continuous society.
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.