| paper | d4-conf-aaai-2010-0157 |
| 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: Polynomial-time solvable, including the exact rational threshold and its endpoint status. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 4
statement extracted from the paper’s text layer
Given a rational distribution μ over bidder types, per-capita item supplies, and a type \(t\) with a losing bid on bundle \(S\), designate mass \(q>0\) of type \(t\) as a cohort. What is the exact threshold \(p^\star\) such that changing that cohort’s bid on \(S\) to \(p\) leaves the welfare-maximizing allocation and fixed-tie-broken bidder-optimal core outcome unchanged for \(b_t(S) ≤ p ≤ p^\star\), while a bid above \(p^\star\) changes the selected outcome?
Types encode complete bidder templates, including true package values, bids, and other auction attributes; μ gives their population masses. Let \(x_{t,A}\) be the mass of type \(t\) receiving integral bundle \(A\), with per-capita supply constraints. Define blocking coalitions and bidder-optimal core payments over masses, then vary the bid of a designated mass \(q\) and compute the threshold at which the selected outcome changes.
The quote in Proposition 4 is pivotal for one bidder, while the proposed \(q\)-mass quote requires a block deviation; this departs from the paper’s deliberate focus on individual envy reduction.
fatal: False
The mirror covers Proposition 4’s optimal quote computation for bidder-optimal core selection. It leaves the other quote methods, convergence results, and strategic safeguards unmirrored.
My lead is Mass Core-Support Envy Quote, an extension of the paper’s optimal envy-quote computation.
The anchor is Proposition 4, proved in this paper: for a bidder-optimal core-selecting combinatorial auction, the described MIP method produces an optimal envy quote. For a losing bundle \(S\), it encodes the current winners’ payments and the losing bids that could form blocking coalitions, with constraints preventing a coalition from using multiple bids from one agent. It minimizes the price of \(S\). The resulting quote is optimal: a bid just above it changes the allocation or payments. This is a named computational result the paper actually computes with, though it does not classify the problem as polynomial-time or NP-hard. The paper’s NP-hard claim for first-price quote computation is unnumbered, attributed to Sandholm (2002), and concerns a different mechanism, so it is not my anchor.
A plausible regime is a large auction for repeated batches of digital advertising inventory. Many small advertisers may share a relatively small number of complete bidder templates: the same values for every package, eligibility and budget rules, and current bid vector. Here \(N\), the number of advertisers, is much larger than the number \(\tau\) of templates. Inventory scales with the batch, so per-capita supply remains meaningful.
For the mirror, a type \(t\) has true package values \(v_t(S)\), current package bids \(b_t(S)\), and any other attributes used by the auction. The society is a rational distribution \(\mu\) over the \(\tau\) types. Let \(\kappa_j\) be the per-capita supply of item \(j\). An allocation is a mass assignment \(x_{t,S}\): each unit of mass receives an integral bundle \(S\), while a type’s mass can be divided among bundles. Feasibility requires
\[ \sum_S x_{t,S}=\mu_t,\qquad \sum_{t,S:\,j\in S}x_{t,S}\leq\kappa_j. \]
Define the mechanism to choose a welfare-maximizing allocation under reported bids, then a bidder-optimal core payment outcome, with a fixed tie-breaking rule. A blocking coalition in this market is a positive-mass set of agents that can reallocate the available stock and weakly improve every member’s utility, strictly improving some positive mass while increasing total payments.
The instance also designates a positive mass \(q\leq\mu_t\) of one type as the cohort whose losing bid for bundle \(S\) is being tested. Mass Core-Support Envy Quote asks for the exact threshold
\[ p^\star=\sup\{p\geq b_t(S):\text{the selected bidder-optimal core outcome is unchanged when that }q\text{-mass cohort bids }p\text{ on }S\}. \]
The solution is the rational value \(p^\star\); above it, the selected outcome changes. The cohort action is part of the question: a zero-mass individual in a nonatomic society cannot change the market outcome.
I expect this mirror to be Class A, provisionally. Dividing bidder classes into masses and scaling stock puts allocation and coalition choices into a configuration-style linear optimization problem; the quote is then a parametric optimization question. The key unresolved step is a polynomial pricing or separation method, with running time stated in \(\tau\), \(k\), the bit length \(L\), and the explicit package-bid input size. Proposition 4 does not establish this tractability claim. The mirror also raises questions about exact rational bit complexity, finite high-multiplicity instances that realize the mass solution, and how the threshold behaves as \(q\) tends to zero.
The scope is deliberately narrow: Proposition 4’s optimal quote computation for bidder-optimal core selection. I am not using the paper’s convergence propositions as computational-complexity anchors, or claiming a mirror for the paper’s other mechanisms.
My weakest point is the change from a single bidder’s pivotal quote to a positive-mass cohort’s quote. Scaling supplies and letting a type’s members split across integral bundles makes a coherent population market, but it changes how a bid affects the outcome. I think the result remains recognizable to these authors because the core-support threshold and bidder-optimal selector are preserved; whether they would accept the cohort threshold as their problem’s continuous form is the main fidelity test.
Proposition 4 is a real computational anchor: it proves that the paper’s MIP method returns an optimal envy quote for bidder-optimal core selection. So the negative case cannot dismiss the paper as having no named computational result. The harder question is whether that quote survives continuization as the same kind of object.
Its meaning depends on a single bidder being pivotal. The quote is the threshold at which one losing bid changes the selected allocation or payments. In a nonatomic society, changing one person’s bid changes no mass, so it cannot change the aggregate outcome. The exact pivotal-bid property that Proposition 4 computes disappears.
The strongest repair is the proposed positive-mass cohort. That is a coherent market model, but it changes the action: \(q\) mass must move its bid together. The resulting threshold is for a block deviation, not the individual response the paper’s envy quotes were designed to support. The paper emphasizes individual envy reduction partly because group action invites collusion. Defining a family \(p^\star(q)\) would make the block question precise, but it would not restore Proposition 4’s individual quote; as \(q\) tends to zero, the cohort loses its effect on the outcome.
A finite high-multiplicity sequence with one bidder changing a bid preserves the original question, but its exact answer remains tied to finite-agent granularity. Taking the population limit erases that bidder’s effect on the aggregate outcome. A limiting shadow price could still be useful, but it would tell a price-taking bidder what a bundle costs, not the threshold at which their bid changes the selected outcome. That is a different computational question.
This is a substantial objection to the proposed mirror, but not a proof that no worthwhile mirror exists. A market where a sizable, homogeneous advertiser segment responds in lockstep to a public quote could make the cohort question plausible, and Proposition 4 is a natural result to extend. The negative case is strongest on fidelity: preserving the paper’s individual pivotal quote makes it vanish in the continuum; preserving an effect on the outcome turns it into a collective-deviation problem the paper was trying to avoid.
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.