| paper | d4-conf-wine-2014-0033 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The factor-\(3\) guarantee is an algorithmic approximation result in substance, but the supplied paper gives no numbered computational result to anchor the mirror. The proposed mass-based version also changes revenue monotonicity from individual bidder changes to positive mass shifts, leaving it an extension whose fit with the authors’ problem is uncertain.
fails bit a — no named computational result to mirror
In an atomless society, one advertiser’s bid change has zero mass and cannot change aggregate revenue; the proposed mass shift instead imposes a cohort-level monotonicity condition.
fatal: False
The proposed mirror covers CAII’s factor-\(3\) randomized mechanism guarantee; it leaves MCAII’s \(O(\log k)\) result and the paper’s broader discussion untouched.
The strongest positive candidate is CAII, the paper’s auction for \(k\) identical items. Its result is an algorithmic approximation guarantee, though not a complexity classification: the paper’s final CAII lemma is printed simply as Lemma, with no number in the supplied text, and claims \(\porm(\mathcal M)=3\). It is proved here. The claim is that for public demands \(d_i\in\{1,\ldots,k\}\) and private values \(v_i\), the randomized mechanism is truthful, revenue monotone, and achieves expected welfare at least one third of the optimum on every profile. It selects the highest-value bidder demanding more than \(\lfloor k/2\rfloor\) items with probability \(1/3\); otherwise it uses the price-per-item ordering of low-demand bidders and randomizes among the greedy winners. The preceding proofs establish truthfulness and revenue monotonicity.
There is no numbered theorem here asserting that a problem is NP-hard, in P, or in a comparable complexity class. So this is not a formally compliant numbered anchor as requested; I won’t invent a number. But it is a constructive mechanism result with a stated approximation guarantee, and it is the paper’s strongest basis for a continuous mirror.
Lead candidate: Continuous-Mass CAII Revenue-Monotone Mechanism Design. An instance has \(k\), a population scale \(N\), and a finite-support rational distribution \(\mu\) over bidder types \((d,v)\), with \(\sum_{d,v}\mu_{d,v}=1\). Type \((d,v)\) means public demand \(d\) and value \(v\) for receiving all \(d\) items. The cohort of that type has mass \(N\mu_{d,v}\); mass may be fractional, but each unit of mass receives either the whole bundle or nothing. A mechanism specifies allocation probabilities and expected payments for every reported profile of these cohorts. Its allocations must be feasible for the \(k\) items, its payments must make truthful bidding optimal for each bidder, and its total expected revenue must not decrease when mass is added or mass shifts to higher bids at fixed demand. Welfare is the total value of allocated mass; the benchmark is the maximum feasible welfare. The question is whether one can give a mechanism family with worst-case \(\porm\le3\) over these societies, and compute its allocation and payments from the support.
This is a plausible high-multiplicity regime when many advertisers fall into a modest number of standardized demand and bid classes: \(N\) is large while the support size \(\tau\) is much smaller. The type definition preserves the paper’s relevant attributes—demand and value—rather than merging bidders with different auction-relevant information. The mirror covers the CAII mechanism result, not the paper’s MCAII extension or the broader theory of revenue-monotone mechanisms.
I would expect this continuous problem to be tractable: the paper’s mechanism relies on sorting by value or price per item and locating a demand threshold. With mass cohorts, the threshold can be found from cumulative type masses, splitting the cutoff cohort as needed. That suggests an algorithm polynomial in \(k,\tau\), and the input bit length, with the factor-3 proof adapted to mass allocations. Further questions would include whether the ratio remains exactly 3, whether continuous mass improves the best possible ratio, and how to round a continuous solution back to an integer bidder profile.
The weakest point is the regime’s plausibility: in online advertising, exact repeated private values may be unusual, even when ad demands or formats repeat. Bid tiers or standardized campaign cohorts make the scenario credible, but less directly than the paper’s own story. There is also a formal limit: the paper gives a mechanism approximation result, not the complexity-landscape result that is ChoCo’s central kind of anchor.
The CAII factor-\(3\) guarantee is the paper’s strongest candidate, but it is not a complexity result. It establishes that a particular truthful, revenue-monotone mechanism achieves a welfare ratio; it does not classify the complexity of a computational problem or give an algorithm for an optimization problem over a supplied society. The paper’s main work is mechanism design under global incentive and monotonicity constraints. That is a real computational field, but it is not the complexity landscape ChoCo is set up to chart.
The proposed cohort model also has a problem preserving the result’s central conditions. In the paper, an advertiser can raise *her* bid, and the mechanism must remain truthful for that individual. In an atomless society represented only by \(\mu\), one advertiser’s report changes no mass. Individual incentive constraints therefore cannot be read from \(\mu\) alone. If raising a bid means shifting positive mass to a higher bid, that is a collective change by a cohort, not the unilateral deviation in the paper. It may be a sensible new axiom, but it is not the paper’s RM condition.
A stronger version could give each advertiser a tagged report against a continuous background distribution, and scale inventory with population so per-capita supply stays positive. That restores meaningful individual incentives, but RM under an individual’s addition or bid increase still has zero effect on the background measure. Making the change nonzero again requires a positive mass shift. And scaling supply changes the fixed-\(k\), scarce-slot auction the paper studies. If instead supply stays fixed, winners become a vanishing share of the population; retaining the finite effect of one advertiser requires tracking finite atoms or \(1/N\)-scale changes. That returns the model to a finite, high-multiplicity auction rather than a genuinely atomless one.
So the best case against this anchor is that its natural continuum versions either change the central monotonicity condition or preserve the finite-agent auction structure. The proposed sorting-by-mass adaptation may be mathematically clean, but it does not open the computational question ChoCo is meant to pursue. This negative case is not airtight: a mass-based RM axiom could itself be a worthwhile mechanism-design question. Its weakness is that ruling that out requires a narrower claim than “no worthwhile continuous mirror in any scenario.”
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.