| paper | d4-conf-ecai-2012-0213 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Corollary 1 is a named impossibility result, but it makes no claim about algorithms or the difficulty of computing a mechanism. The proposed mass-market question is plausible and precise, yet it cannot supply the missing computational anchor required for a ChoCo mirror.
fails bit a — no named computational result to mirror
The proposed question covers the competitive trading-size guarantee and its incentive, budget-balance, and individual-rationality constraints. It leaves the paper's one-sided truthful mechanisms and other mechanism results aside.
The strongest positive case is a high multiplicity mirror of the paper’s trading-size impossibility. The natural setting is a large group-buying market where many buyers share a small number of reservation values and sellers share a small number of cost schedules. Mass represents the fraction of buyers or sellers of each complete type. That fits the paper’s focus on competition between buyers and sellers, rather than merely making the traded good divisible.
My lead anchor is Corollary 1, proved here: there is no weakly or strongly budget-balanced, individually rational, truthful multi-unit double auction whose trading size is competitive—meaning it achieves at least a fixed positive fraction of the optimal trading size on every type profile. This is a substantive impossibility result about the paper’s mechanism problem. But it is not a computational-complexity result: the paper proves no named result about an algorithm being in \(P\), NP-hardness, or another complexity classification. So this can motivate a continuous mechanism-design question, but it does not meet ChoCo’s computational-anchor requirement.
A plausible regime is an online group-buying market with a very large buyer population and relatively few buyer value bands, alongside many suppliers with a small number of shared cost schedules. Buyer types specify willingness to pay for one unit; seller types specify costs for supplying quantities, including group discounts. Masses are rational fractions. To define the mirror, seller quantity and cost schedules would need a real-valued, per-capita interpretation as the market scales. That is a co-modification of the model, not continuity of the traded outcome alone.
Here is the precise candidate question: Continuum Competitive Group-Buying Auction Existence. An instance is a pair of finite-support distributions with rational masses, one over buyer types and one over seller types. Buyer type \(t\) has value \(b_t\) for one unit. Seller type \(s\) has a rational piecewise-linear cost schedule \(c_s(q)\) for supplying quantity \(q\), with nondecreasing total cost and nonincreasing average cost. A mechanism takes reported type distributions and gives each type a lottery over trade and payment outcomes. It must be feasible in aggregate, individually rational for truthful agents, truthful against unilateral misreports, and weakly budget balanced in expectation.
Let \(Q_{\mathrm{opt}}(\mu)\) be the greatest mass of trade possible at nonnegative aggregate surplus, and let \(Q_M(\mu)\) be a mechanism’s expected traded mass. The question is whether there is a single such mechanism and a constant \(c\) for which \(Q_M(\mu)\ge Q_{\mathrm{opt}}(\mu)/c\) for every instance. A solution is either a mechanism with that guarantee and proofs of its properties, or an impossibility proof. This mirrors Corollary 1’s demand for a constant-competitive trading size, with mass replacing counts.
I would expect the same economic tension among truthfulness, budget balance, individual rationality, and trade volume to obstruct such a mechanism. But this is not a prediction of tractability, transferred hardness, or continuum-specific computational hardness: the anchor concerns mechanism existence, not algorithmic complexity. The mirror covers the trading-size guarantee and the associated incentive constraints. It does not turn the paper’s results into a complexity landscape.
The soft spot is substantial: the paper’s impossibility theorem is not a computational result, and extending an individual seller’s quantity-discount schedule to a population-scaled cost curve is not canonical. In particular, group discounts may make concentrating supply in one seller essential, while a mass model naturally aggregates supply across sellers. The authors might recognize the proposed question as a continuous group-buying mechanism problem, but a ChoCo referee could reasonably reject it as outside the programme’s computational scope.
The best negative case is that Corollary 1 is not a computational result. It rules out a class of mechanisms: none can satisfy budget balance, individual rationality, truthfulness, and a constant competitive guarantee on trading size. It says nothing about an algorithm’s running time, computational complexity, or approximation. The other named results likewise concern incentive and mechanism properties. A continuous-population version of Corollary 1 could be a worthwhile mechanism-design question, but it would not fill ChoCo’s stated gap in computational complexity.
The proposed continuum question keeps that same mismatch. Its \(Q_{\mathrm{opt}}\) is a sensible mass analogue of the paper’s trading-size benchmark, and a market with many buyers in a few value bands is plausible. But replacing counts with masses does not turn a mechanism-existence theorem into a computational one. To get a computational mirror, one would need to introduce a new task—for example, specify encodings for the traders’ valuation schedules and ask how hard it is to compute an allocation or payment. That could be interesting, but it is not what Corollary 1 establishes, and its answer would not classify the result the paper actually proves.
There is a real modeling choice on the seller side: the paper’s discount schedule is a property of one seller supplying \(k\) units. Scaling the market raises questions about how seller capacity and those schedules scale, and whether trade can be spread across sellers. A careful mass model might resolve those questions, so they are not a decisive objection. Nor is high multiplicity itself implausible: repeated buyer values and seller schedules give a recognizable regime, and existing high-multiplicity auction work supports that regime.
So I would not claim that no continuous version of this market could be worthwhile. The stronger, narrower conclusion is that the paper offers no computational result for such a version to mirror. Its continuous analogue belongs to mechanism design unless someone adds a distinct computational problem. That makes the case against a ChoCo mirror strong on scope, but weak as a universal claim against continuous study of the market.
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.