| paper | d4-conf-wine-2015-0023 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
For a finite set of item categories \(\Omega\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita supplies \(q_j\), and a price increment \(\varepsilon\), let each complete bidder type \(t\) have a monotone, \(\alpha\)-near-submodular valuation \(v_t(S)\) over integral bundles \(S\subseteq\Omega\). In a specified mass-SMRA with uniform category prices, type-state masses choose truthful conditional bids, category capacity is \(q_j\), and standing-high-bid mass is updated with a fixed measurable tie rule. Is every terminal outcome’s welfare at least \(\beta\,\mathrm{OPT}(\mu,q)\), where \(\mathrm{OPT}\) maximizes welfare over feasible allocations of integral bundles subject to the type masses and category supplies; in particular, does the bound \(\beta=1/(1+\alpha)\) hold, with \(\alpha\)-individual rationality almost everywhere?
A population distribution over complete valuation types, with mass \(\mu_t\) per type and per-capita supply \(q_j\) of each item category. State variables track the mass of each type holding each integral provisional bundle; truthful conditional bids and standing-high-bid updates determine the allocation, whose total welfare is compared with the maximum feasible allocation under the same supplies.
The paper has one standing high bidder per indivisible item, so the proposed capacity-mass update and its tie rule need a precise definition and may not be the unique high-multiplicity limit.
fatal: False
The mirror covers the welfare guarantee in Theorem 1 and can cover Theorem 3 under secure bidding; it leaves Theorem 2’s local-improvement guarantee, the bad example, and the activity-rule discussion unanalysed.
There is a defensible continuous mirror for the paper’s SMRA welfare guarantees, though it is weaker evidence for ChoCo’s central complexity programme: the paper gives no named theorem about polynomial time, NP-hardness, or parameterized complexity. Its numbered results concern the welfare and rationality of auction outcomes. I would use those as performance-analysis anchors, not present them as complexity results.
My lead is Theorem 1, stated in the introduction and proved in this paper through Theorems 5 and 6. It says that if bidders have \(\alpha\)-near-submodular valuations and use conditional truthful bidding, the SMRA’s allocation has welfare at least \(\frac{1}{1+\alpha}\) times optimal, and the auction is \(\alpha\)-individually rational. The latter means that in every round, each bidder’s value for their provisional bundle, multiplied by \(\alpha\), is at least its price.
A concrete mirror is Mass-SMRA Truthful Welfare Certification. An instance has a finite set \(\Omega\) of item categories; a rational distribution \(\mu\) over \(\tau\) bidder types; an explicit valuation table \(v_t(S)\) for each type \(t\) and bundle \(S\subseteq\Omega\); a rational per-capita supply \(q_j\) for each category \(j\); and a price increment \(\varepsilon\). A type completely specifies the bidder’s valuation and bidding rule. At the continuum level, a variable \(x_{t,S}\) records the mass of type \(t\) receiving the integral bundle \(S\), with \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:j\in S}x_{t,S}\le q_j\). The objective is welfare, \(\sum_{t,S}x_{t,S}v_t(S)\), and the benchmark \(\mathrm{OPT}(\mu,q)\) is its maximum over feasible allocations.
The auction state records, by type and provisional bundle, how much mass holds each bundle. Each such mass chooses its conditional bid \(T\subseteq\Omega\setminus S\); truthful conditional bidding maximizes \(v_t(S\cup T)-v_t(S)-\sum_{j\in T}(p_j+\varepsilon)\). The item-by-item standing-high-bid updates are lifted to supply masses \(q_j\), with ties split measurably. Given a rational threshold \(\beta\), the question is whether every terminal mass-auction outcome has welfare at least \(\beta\mathrm{OPT}(\mu,q)\) and is \(\alpha\)-individually rational at every round. A solution is a proof of that guarantee or a violating mass trajectory. I expect the \(\frac{1}{1+\alpha}\) guarantee to survive: the paper’s welfare and price inequalities appear to extend by integrating over type-state mass. That makes this a Class A candidate, though the paper itself supplies no polynomial-time algorithm for optimizing over all possible mass trajectories.
The regime I would defend is a large, replicated market: for example, many regional markets selling the same categories of network or access rights, with bidders sharing a modest number of complete valuation profiles. There could be \(N\) bidders and item supplies that scale with \(N\), while the number of types \(\tau\) stays in the tens or hundreds. The bid variable is then mass making a particular conditional bid; allocations remain integral for each agent even though a type’s mass can be split among bundles.
A second, distinct anchor is Theorem 3, proved in Section 5.2. It says that if valuations are \(\alpha\)-near-submodular, all set values are multiples of \(\varepsilon\), and each bidder makes a profit-maximizing conditional secure bid in every round, then the SMRA’s welfare is at least \(\frac{1}{1+\alpha}\) times optimal. A secure bid requires every subset of the bidder’s provisional set plus bid to have value at least its price. Secure bidding therefore supplies full individual rationality as well. Its mirror, Mass-SMRA Secure Welfare Certification, uses the same instance and asks whether every terminal outcome under profit-maximizing secure bids meets a threshold \(\beta\mathrm{OPT}(\mu,q)\); a counterexample is a violating mass trajectory. I also expect the stated guarantee to survive as a Class A result, by extending the paper’s type-wise inequalities over mass. Further questions include the complexity of finding a profit-maximizing secure bid and whether the guarantee persists under realistic activity rules. The paper itself notes that such rules may make secure bidding risky.
Theorem 1 is my lead because its bidding rule and welfare question are the most direct mirror of the paper’s main result. Theorem 3 adds a useful second case: the same welfare bound under a different bidding discipline, with individual rationality restored.
The weakest point is the market regime. A fixed-stock auction of a few spectrum licenses among a small number of firms is not a useful continuum-agent limit: as the number of bidders grows, the winners have vanishing mass. My mirror therefore needs supply to scale with the population, as it might across many repeated regional markets. That co-modification is allowed by the programme, but it narrows the claim. More broadly, these theorems establish outcome guarantees, not computational complexity. They support a continuous population mirror of the paper’s welfare analysis; they do not, by themselves, establish a ChoCo-style complexity landscape.
The strongest case against both anchors is that neither is a computational result. Theorem 1, proved through Theorems 5 and 6, bounds the SMRA’s welfare and individual rationality under truthful bidding. Theorem 3 gives a welfare bound under secure bidding. Neither states a runtime, classifies a computational problem, or gives an algorithm for one. As proposed, the “certifications” ask whether those guarantees extend to a mass auction, with a proof or a violating trajectory as the answer. That could be worthwhile auction analysis, but it does not fill ChoCo’s stated gap in complexity questions about a continuous population.
The best version of Theorem 1’s mirror would use repeated bidders of a few complete types, scale supplies with population, and track mass across provisional bundles. That is a plausible high-multiplicity regime; I would count it as evidence that the regime makes sense, not as an objection. Aggregate welfare can remain meaningful, and the theorem’s inequalities may extend over mass. But establishing that extension is still a performance theorem. To turn it into a computational question, one would need to add a task such as finding the worst terminal mass trajectory or computing an auction outcome. That is a researchable question about a newly specified mass auction, not a complexity claim made by this paper.
Theorem 3 has the same gap. Asking whether the welfare guarantee survives mass aggregation is again performance analysis. Asking how to find a profit-maximizing secure bid is a stronger computational angle, but it shifts the anchor: the paper assumes such bids and proves a welfare consequence; it does not claim an algorithm for finding them. A continuous study could investigate that problem, but its computational contribution would have to be established independently. Individual rationality does not settle the issue either: its pointwise form loses force for zero-mass identities, though an almost-everywhere version over type and auction state could be sensible.
So the negative case is strong against these two results as *ChoCo complexity mirrors*, but weak against the broader claim that a continuous auction-performance study could be valuable. A replicated-market model may support one. The paper simply gives no computational result to continue; making one of its welfare guarantees continuous would add an adjacent result, not chart the complexity landscape the programme is meant to study.
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.