| paper | d4-conf-sigecom-2011-0028 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time exactly solvable: an admissible mechanism attains \(R(M)=\mathrm{OPT}\), so \(c=1\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given a finite support of private value vectors and public budgets with rational population masses \(\mu_t\), a finite service set \(J\), and per-capita total supply \(q\), does a \(\mathrm{poly}(|J|,\tau,L)\)-time algorithm output an anonymous direct-revelation mechanism with indivisible service lotteries and feasible mass rationing that is DSIC, ex-post IR, budget-feasible, and earns a fixed constant fraction of optimal expected revenue per capita? Require supply feasibility at every report-mass profile and evaluate revenue under the truthful type distribution \(\mu\).
A nonatomic population with finite support over value-vector and public-budget types, distributed according to \(\mu\). The mechanism assigns each individual at most one service or nothing, while aggregate allocated mass is at most \(q\); each individual remains strategic, but a unilateral report does not change aggregate rationing. The objective is expected revenue per capita under truthful reports.
The continuum's atomless incentives and aggregate rationing differ from the finite-agent setting, so Theorem 10 does not establish the proposed approximation or its computation.
fatal: False
The mirror anchors on Theorem 10's public-budget, multi-parameter unit-demand revenue approximation for matroid or simpler feasibility. It leaves the paper's single-agent characterization, other revenue results, private-budget results, and welfare results aside.
The strongest positive case is a high-volume, unit-demand marketplace: for example, a very large market of automated campaign accounts choosing among a fixed set of advertising products. A useful regime has \(n\) accounts but only \(\tau\) distinct combinations of valuation for those products and public spending budget, with \(n\gg\tau\). Each type \(t\) has a value vector \(v^t\) and public budget \(B_t\); \(\mu_t\) is its fraction of the market. Requiring agents in a type to share their relevant values and budget is the point of the high-multiplicity model, not a distortion. Inventory scales with the market: every agent can receive at most one product, and total supply is a fixed fraction \(q\) of the population.
My lead mirror is Continuous Budget-Constrained Unit-Demand Revenue Approximation. Its input is a finite set of services \(J\), rational type masses \((\mu_t)_{t\in T}\) summing to one, rational value vectors and public budgets for each type, and a rational per-capita supply \(q\). To stay within the paper’s setting, value distributions within each public-budget cohort can be restricted to the paper’s product priors, with the induced finite support listed explicitly. The mechanism does not know an individual’s value vector; agents report it, while their budget is public.
The question is: given this instance, can an algorithm running in \(\mathrm{poly}(|J|,\tau,L)\) output a direct-revelation mechanism that is dominant-strategy truthful, ex-post individually rational and budget feasible, assigns at most one service to each agent, and respects the supply limit at every report profile? The target is a fixed constant fraction of \(\mathrm{OPT}_\infty\), the maximum expected revenue per capita of any mechanism with those properties. A solution is the mechanism—such as a set of truthful menus and a feasible rationing rule—not an LP encoding. Each individual still receives either an indivisible service or nothing; fractions arise because the mechanism can serve a fraction of a type’s mass. The supply constraint is the uniform-matroid case, normalized by population size.
The anchor is Theorem 10, proved in this paper. It states that for multi-parameter, unit-demand agents with public budgets and a matroid or simpler feasibility constraint, there is a polynomial-time computable mechanism for the budget-truncated instance \(\hat I\) which is budget feasible and DSIC for the original instance \(I\), and earns a constant fraction of the optimal budget-feasible revenue for \(I\). The proof here builds on the cited multi-parameter reduction [6] and the cited greedy matroid-intersection result [13]. The paper has no comparable numbered hardness result, so an algorithmic anchor is the right choice.
This mirror keeps the central problem recognizable: the seller chooses how to allocate scarce services and charge agents with budget-limited, multi-dimensional values, while seeking revenue under incentive and feasibility constraints. It changes the population representation from a list of named agents to masses of complete agent types. The continuous question is therefore whether the approximation can be computed from the type support and its masses, with supply scaled per capita. Randomized lotteries remain possible tools in the mechanism; making lotteries continuous is not the goal.
I expect this mirror to be Class A, at least for uniform or other well-structured capacity constraints. A natural route is to aggregate identical agents and reason over their served mass, rather than processing every account separately. That suggests a type-compressed algorithm, potentially using posted prices or a finite optimization over types. Follow-up questions include whether the constant approximation extends to normalized general matroids, whether exact revenue optimization is tractable, and how the answer changes with private budgets. The scope here is only Theorem 10’s public-budget, multi-parameter revenue result; I would not stretch it to the paper’s welfare theorems.
The weak point is that Theorem 10 does not itself prove the continuum result. Its construction is for finite named agents and may use their ordering; a continuous mechanism needs a truthful, feasible rationing rule that works with masses. Also, repeated exact valuation vectors are a demanding scenario assumption. The case survives because it proposes a specific regime where those repetitions and per-capita inventory are sensible, and asks a computational question that retains the paper’s objective, budgets, unit-demand preferences and truthfulness requirements. It is a mirror to investigate, not a claim that the paper already solved it.
Theorem 10 is a real anchor: it gives a polynomial-time mechanism for a computational problem, and the proposed marketplace has a credible high-volume regime. I cannot dismiss it on the grounds that the paper lacks an algorithmic result or that repeated agents are implausible.
The best objection is that the proposed input blurs two different meanings of “type.” In Theorem 10, agents have independent private value draws from product priors; the mechanism is designed for a finite set of named agents and a feasibility constraint on those agents and services. If \(\mu_t\) instead gives the exact realized mass of each valuation vector, it does not specify that Bayesian model. If it describes a prior over hidden values, the mirror needs to define how independent draws, aggregate reports, rationing, and ex-post feasibility work for a continuum. Theorem 10 does not supply that definition: its construction works through representatives and finite feasibility constraints.
There is a coherent repair: take a finite-support prior over valuation and budget types, a nonatomic population, per-capita supply \(q\), and an explicit class of anonymous truthful mechanisms with feasible mass allocations. But that repair changes the strategic environment. An individual report has zero effect on aggregate demand or rationing, unlike a report in the finite auction. It is therefore a new continuum market-design problem, not a direct high-multiplicity reading of Theorem 10. That shift gives a reason to question whether this is the best use of ChoCo’s effort, but it does not show that the repaired question is uninteresting.
Existing continuum work reinforces the distinction without resolving the computational question. Richter studies welfare and revenue mechanisms for a continuum of budget-constrained agents, but with a divisible good and without the paper’s unit-demand setting; that work supplies analytic results, not a computational classification of the proposed mirror. [Richter, “Mechanism design with budget constraints and a population of agents”](https://www.sciencedirect.com/science/article/abs/pii/S0899825619300193). Under the programme’s criteria, it is relevant background, not a collision.
So the negative case is weak where it matters most: the proponent’s formulation needs sharpening, but its repaired version remains a sensible continuous-population question. I cannot honestly argue that no worthwhile mirror survives.
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.