| paper | d4-conf-aaai-2000-0052 |
| 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; an exact optimum \(x^\star\) can be computed in time polynomial in \(m,\tau,B,L\), and hence satisfies \(W(x^\star)\geq\mathrm{OPT}-3C\varepsilon\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite set of bidder types \(T\), rational masses \(\mu_t\), explicit package menus \(\mathcal B_t\subseteq 2^{[m]}\), package values \(v_{t,S}\), and per-capita supplies \(q_j\), compute an allocation \(x_{t,S}\geq 0\) maximizing \(\sum_{t\in T}\sum_{S\in\mathcal B_t}v_{t,S}x_{t,S}\), subject to \(\sum_{S\in\mathcal B_t}x_{t,S}\leq\mu_t\) for each type and \(\sum_{t,S:j\in S}x_{t,S}\leq q_j\) for each resource class. Each unit of assigned mass receives the whole package \(S\).
A society with type masses \(\mu_t\) and per-capita resource supplies \(q_j\); variables \(x_{t,S}\) assign mass of each type to whole packages, maximizing total welfare subject to type-mass and supply constraints.
The mirror covers the welfare-allocation target behind Theorem 1 as type-mass winner determination. It leaves the iterative bidding dynamics, individual price discrimination, Theorem 2's safe-bid condition, and the experimental comparisons aside.
The strongest anchor is Theorem 1, proved in this paper. It says that with \(|G|\) items, \(|I|\) agents, and minimum bid increment \(\epsilon\), iBundle terminates with an allocation whose value is within \(3\min\{|G|,|I|\}\epsilon\) of optimal when agents use myopic best-response bidding. This is a named approximation guarantee, though not a P-versus-NP result. The paper’s statement that winner determination is NP-hard is in the prose and cites Rothkopf et al.; I treat it as context, not as a named anchor.
My lead mirror is Per-capita Type-Mass Winner Determination. Imagine a large market for bundles of standardized resource classes, such as compute, storage, and bandwidth. There are \(m\) classes and a finite set \(T\) of complete bidder types: a type includes the same values for packages, bid options, and other parameters. The society is a rational distribution \(\mu\), with \(\sum_{t\in T}\mu_t=1\). Each class \(j\) has per-capita supply \(q_j\in[0,1]\). For each type \(t\), the input lists package options \(\mathcal B_t\subseteq 2^{[m]}\) and their values \(v_{t,S}\).
The decision variable \(x_{t,S}\geq0\) is the mass of type \(t\) receiving the whole package \(S\). The problem is to return a feasible allocation maximizing \(\sum_{t,S}v_{t,S}x_{t,S}\), subject to
\[ \sum_{S\in\mathcal B_t}x_{t,S}\leq\mu_t \quad\text{for each }t, \qquad \sum_{t,S:j\in S}x_{t,S}\leq q_j \quad\text{for each }j. \]
A finite version has \(N\) bidders, \(N\mu_t\) bidders of each type, and \(Nq_j\) copies of each resource class. Thus \(N\) can be very large while \(\tau=|T|\) stays moderate. In the continuum, \(x_{t,S}\) splits *people of a type* among packages; it does not give any person a fractional package. A prover could be asked to compute an optimal \(x\), or, mirroring Theorem 1’s precision guarantee, an allocation within \(3\epsilon\min\{1,\sum_jq_j\}\) of the per-capita optimum. That bound is Theorem 1’s additive error divided by \(N\).
This is a credible mirror of the paper’s winner-determination problem: it retains package bids, mutually exclusive choices, scarce resources, and welfare-maximizing allocation. The regime is plausible where many buyers share a small number of value and bid-menu profiles, such as recurring cohorts of firms buying standardized capacity bundles. Existing high-multiplicity work would support treating this regime seriously. The named theorem concerns the finite-agent auction’s approximation; the continuous question isolates the allocation problem its auction computes.
For the explicit package-list input above, the continuous problem is a linear program with \(\sum_t|\mathcal B_t|\) allocation variables, so I expect Class A in time polynomial in the input size. If package values are given succinctly instead, the relevant pricing question can be \(\max_S(v_t(S)-p(S))\), and the LP description alone does not promise a polynomial algorithm. That distinction is central: the paper’s prose hardness result does not by itself show that hardness survives when repeated identical bidders can be split by mass. Further questions are whether this tractability extends to particular succinct valuation languages, and whether a type-mass version of iBundle itself reaches the LP optimum under its price updates and best-response assumptions.
The weakest point is that Theorem 1 proves a guarantee for an auction among finitely many agents, including price discrimination when needed. It does not prove that a continuum auction has the same dynamics or guarantee. The mass allocation is still a sensible high-multiplicity version of the underlying problem, but the mirror covers the theorem’s welfare target, not every strategic feature of iBundle.
The strongest objection is that the proposed LP does not mirror Theorem 1’s result. That theorem is about iBundle as a protocol: agents submit myopic best-response bids over multiple rounds, the auctioneer updates provisional allocations and ask prices, and the final allocation has a welfare guarantee. The proposed type-mass LP instead takes package values as input and centrally computes an allocation. It drops the bidding process, price updates, and the conditions under which the theorem proves its guarantee. It is a plausible high-multiplicity version of winner determination, but it is a different computational question.
A closer mirror would make each type’s current bidding state part of the population description, then ask whether a mass version of iBundle retains a welfare guarantee. That question has real modeling work behind it: the paper’s general result uses price discrimination tied to individual bidding histories, and its safety condition is stated for an individual’s compatible bids. A continuum model would need to say how those histories and prices are represented, and how the termination conditions work for mass bids. The paper does not supply that model or a theorem that settles it. This makes Theorem 1 a weak anchor for the LP the proponent actually proposes.
The numerical bound itself is not the problem. If the finite market has \(N\) bidders and \(Nq_j\) copies of each resource class, then \(\min\{|G|,|I|\}/N\) can indeed become \(\min\{\sum_j q_j,1\}\). That scaling is consistent with the theorem. But it supports a welfare bound for a replicated finite auction; it does not turn the offline LP into a continuous version of the auction’s dynamics.
I cannot honestly extend this into a strong case that *no* worthwhile mirror exists. The static type-mass winner-determination problem is a sensible high-multiplicity question, and the paper’s prose identifies winner determination as NP-hard. For an explicit package menu, the proposed mass model is a well-posed LP. So I would reject the claimed link to Theorem 1, but the broader negative case remains weak: the winner-determination mirror may still be worth studying on its own.
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.