| paper | d4-conf-atal-2014-0100 |
| 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 lottery optimization is exactly polynomial-time solvable. Proportional-supply MVM is DSIC and feasible, but its eventual welfare guarantee fails: an instance with both values strictly greater than \(1\) has limiting gap \(1/16\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite value-type set \(T\), values \(v_t\in[1,U]\), rational masses \(\mu_t\) summing to one, and per-capita type-A supply \(\rho\in(0,1)\), compute a type-based lottery \((q_t,p_t)_{t\in T}\) maximizing \(\sum_t\mu_t v_t q_t\), subject to \(\sum_t\mu_t q_t\le\rho\), \(q_t+p_t\le1\), and DSIC constraints \(v_tq_t+p_t\ge v_tq_s+p_s\) for all \(t,s\). Determine whether an MVM-style rule can attain the efficient welfare within additive \(\varepsilon\) as finite populations grow with proportions converging to \(\mu\).
A growing population with finitely many valuation types and rational masses, a residual claimant for type-B goods, and type-A supply proportional to population size; each type has allocation probabilities \(q_t,p_t\), aggregate feasibility is measured against \(\mu\), and welfare is \(\sum_t\mu_t v_t q_t\).
MVM selects among the top \(\lceil U\rceil\) named bidders for one item, and those ranks have no direct mass-level counterpart; scaling supply to \(\rho N\) also requires a new rule and a precise individual-deviation incentive model.
fatal: False
Covers Theorem 5’s DSIC, feasibility, and asymptotic welfare guarantee in the residual-claimant setting; it leaves Theorem 2’s MIHR impossibility and the other mechanism comparisons aside.
I find no qualifying computational anchor in this paper. Its numbered results do not assert that an underlying problem is in P, NP-hard, or belongs to another computational complexity class. The closest result is Theorem 5, proved in this paper: for any value distribution supported on \([1,U]\) with finite \(U>1\), the Multi-lottery Vickrey Mechanism is DSIC and feasible, and for every \(\varepsilon>0\), sufficiently many agents and a residual claimant make its expected welfare come within \(\varepsilon\) of optimal allocation. That is an asymptotic welfare guarantee, not a complexity result. Theorem 2 is also a near miss: it says that for i.i.d. values with monotone increasing hazard rate, no DSIC feasible mechanism beats arbitrary allocation in expected welfare. The other named results characterize incentive compatibility or establish welfare properties of particular mechanisms. Proposition 2 is attributed to Hartline and Roughgarden (2008), and it too is a welfare inequality.
The most promising population regime is a large computing service with many users sharing a small set of value types for a scarce high-performance resource, alongside plentiful ordinary service. Type \(t\) could be a user class with value \(v_t\); its mass \(\mu_t\) is the fraction of users in that class. An analogue would choose, for each reported type, probabilities \(q_t\) of receiving the scarce resource and \(p_t\) of receiving the plentiful good, subject to incentive and allocation constraints, and maximize scarce-resource welfare when plentiful goods have a residual claimant. Per-capita scarce-resource supply would need to scale with population size. This is a plausible continuum limit of the setting in Section 3, but it asks about welfare and incentive-compatible mechanism design. Theorem 5’s mechanism also depends on the ranks of the top \(\lceil U\rceil\) individual bidders, a feature a mass description may not preserve.
So I cannot state a continuous computational problem per anchor without inventing a computational claim the paper does not make. This leaves the positive case weak under the requested standard: the paper offers a credible large-population hook, but no named computational result for that hook.
The strongest case against is that this paper has no named computational result to mirror. Proposition 1 and Theorem 1 characterize incentive compatibility and feasibility; Theorems 2–4 give welfare bounds or compare mechanisms; Theorem 5 proves an asymptotic welfare guarantee. None specifies a computational problem or establishes its complexity. The paper has no encoded input, required algorithmic output, or running-time or hardness claim. Under ChoCo’s source gate, that is decisive: a computational question inspired by the paper would be a new project, not a mirror of one of its results.
Theorem 2 is not a hidden population-continuization result. Its distribution \(F\) is a prior over the private values of \(n\) finite agents. Treating that prior as the society’s type-mass distribution would conflate uncertainty about agents with an aggregate population. A direct population limit also strains the theorem’s object: with one type-A good, its per-capita supply vanishes, and the top bidder’s contribution is not represented as positive mass. Theorem 5 makes this especially clear: its mechanism allocates among the top \(\lceil U\rceil\) individual bidders, a set whose mass vanishes as \(n\) grows. Scaling type-A supply with population size could preserve a meaningful allocation problem, as the programme allows, but that produces a multi-unit mechanism-design extension rather than a mirror of these single-item welfare theorems.
The proponent’s computing-service scenario is plausible, and a finite set of value classes could support a well-defined mass-based mechanism-design problem. But asking an algorithm to optimize such a mechanism would add the computational question that the paper itself does not ask. Theorem 5’s limit is a welfare result, not an algorithmic guarantee; the paper’s discussion of optimal mechanism design is motivation for future work, not a complexity anchor. The negative case is therefore strong against treating this as a ChoCo mirror candidate, though weaker against the broader claim that a useful computational project could be built from the same setting.
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.