| paper | d4-conf-ijcai-2009-0173 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable, in \((m+\tau+L)^{O(1)}\) bit operations, hence \(L^{O(1)}\) for the explicitly listed input. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.1
statement extracted from the paper’s text layer
Given a finite goods set \(G\), bidder types \(T\) with rational masses \(\mu_t\) summing to \(1\), integral packages \(I_t\), payments \(p_t\), and rational per-capita inventory \(b_g\), choose accepted masses \(x_t\in[0,\mu_t]\) to maximize \(\sum_{t\in T}p_tx_t\), subject to \(\sum_{t\in T}I_t(g)x_t\le b_g\) for every \(g\in G\).
A nonatomic population of buyers whose types specify complete package-and-payment bids; choose each type's accepted mass, subject to per-capita goods capacities, to maximize revenue. Each accepted unit of mass receives its original integral package.
The mirror covers only Theorem 5.1's atomic-bid branch with \(\mathrm{in\text{-}deg}(A)=0\), where no transformation produces goods. It leaves the other branch, feasibility results, and instances with production or richer bidding languages aside.
The strongest honest mirror is the demand-side, atomic-bid slice of winner determination. It keeps the auctioneer’s question— which bids to accept to maximize revenue—while making the bidder population continuous.
My anchor is Theorem 5.1. It states that WINNER-DETERMINATION is NP-hard under atomic bids both when \(\mathrm{in\text{-}deg}(A)=0\) and when \(\mathrm{out\text{-}deg}(A)=0\). In the paper’s definitions, the first restriction means no transformation produces goods; the second means no transformation requires goods. The paper says this result follows by adapting classical combinatorial-auction hardness results, citing Lehmann, Müller, and Sandholm (2006). I rely on the first branch: bids consume goods from the auctioneer’s inventory, and accepted bids pay the auctioneer.
Here is the continuous problem. An instance has a finite set \(G\) of goods, a finite set \(T\) of bidder types, rational masses \(\mu_t\geq 0\) with \(\sum_{t\in T}\mu_t=1\), and rational per-capita inventory \(b_g\) for each good. A type \(t\) specifies a complete atomic bid: a package \(I_t\in\mathbb{N}^{|G|}\) the bidder receives and a payment \(p_t\) to the auctioneer. Choose an accepted mass \(x_t\in[0,\mu_t]\) for each type to maximize
\[
\sum_{t\in T}p_t x_t
\]
subject to
\[
\sum_{t\in T} I_t(g)x_t\leq b_g\qquad\text{for every }g\in G.
\]
Unused inventory is allowed, as under free disposal. Each accepted bidder still receives their whole integral package; \(x_t\) is the mass of identical bidders whose bid is accepted. With total population \(N\), the corresponding discrete counts and inventory are \(N\mu_t\) and \(Nb_g\), when those are integral.
This is a plausible regime for a large wholesale or procurement market with many buyers drawn from a modest menu of recurring package-and-price profiles. The type records everything relevant to the auction: the desired bundle and the offered payment. The number of agents \(N\) can be very large while the number of distinct types \(\tau=|T|\) and the goods universe remain modest. Inventory scales with the market. This makes population mass the continuous object; fractional aggregate consumption is the type-level average of integral packages.
The authors should recognize this as their winner-determination problem in the no-production, atomic-bid case, with the discrete accept-or-reject choice replaced by an accepted fraction of each bidder type. It does not extend the mirror to every MMUCA feature: it covers only the \(\mathrm{in\text{-}deg}(A)=0\) branch of Theorem 5.1, with no transformations that produce goods and no richer OR/XOR bidding language.
I expect this mirror to be tractable (Class A). It is a linear program with \(\tau\) variables, one capacity constraint per good, and one upper bound per type, so it is solvable in time polynomial in the input bit length, \(|G|\), and \(\tau\). The discrete NP-hardness concerns selecting whole bids; in the continuous population, accepting any mass of a type is allowed. That makes the LP a meaningful high-multiplicity relaxation and a natural source of bounds or approximations for discrete instances.
The weak point is that the LP need not give the exact winner determination for a finite auction: it can accept a fractional number of bidders of a type. If the authors or a referee require every named bidder to remain all-or-nothing in the aggregate, this is too relaxed to count as their problem. I think the mirror survives that objection because the population, rather than an individual bid or bundle, is what has been continuized; each unit of accepted mass still carries the original integral package.
The main follow-up is to formalize the discrete-to-continuous dictionary: for counts \(n_t\) and inventories \(B_g\), set \(\mu_t=n_t/N\) and \(b_g=B_g/N\), then determine the LP’s gap from the finite optimum and when rounding recovers an exact or additive approximation. Further questions include conditions making the discrete formulation integral, and whether adding production transformations or XOR bids preserves tractability.
I can’t make the requested universal negative case stick. Theorem 5.1’s \(\mathrm{in\text{-}deg}(A)=0\) branch is a clean anchor: bidders request packages, the auctioneer has limited inventory, and accepted bids generate revenue. A type can record the complete package and payment. Markets with many buyers drawn from a modest menu of package-and-price profiles are plausible, and per-capita inventory is a natural part of that mirror.
The fractional \(x_t\) does not defeat it. In a nonatomic population, \(x_t\) is the mass of identical bidders accepted; every accepted unit of mass still gets its whole integral package. There is also a direct high-multiplicity link: for a finite instance scaled by \(N\), accepting \(\lfloor Nx_t\rfloor\) bidders of each type preserves feasibility because package quantities are nonnegative. With fixed support, the resulting revenue loss is at most \(\sum_t \max(p_t,0)\), so the loss per capita vanishes as \(N\) grows.
The strongest objection is that the original hardness concerns all-or-nothing decisions for finite bidders, while this mirror permits partial acceptance by type and reduces to an LP. But that objects to the intended population relaxation and its answer, rather than identifying a fundamental failure of the model. Some auctions have bespoke bidders and no useful repeated types; that rules out those instance regimes, not plausible repeated-type markets. The paper gives no basis for claiming that bidder identity must matter, that the continuum degenerates, or that this continuous computational question is already answered.
So the anchor survives. The honest negative case is weak: this paper appears to offer a worthwhile continuous-population mirror of Theorem 5.1’s no-production branch.
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.