| paper | d4-conf-ecai-2016-0323 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: an exact maximizing allocation is computable in \(\operatorname{poly}(m,\tau,L)\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given ordered categories \(A=[n]\), rational per-capita supplies \(q_j\), and a rational distribution \(\mu\) over supported bidder types \(t=(S_t,1)\) with \(S_t\in\mathcal{B}_5=\{[i,i+2]\}\cup\{\{i,j\}:i\ne j\}\), compute a revenue-maximizing allocation of type mass \(x_t\), subject to \(0\le x_t\le\mu_t\) and \(\sum_{t:j\in S_t}x_t\le q_j\) for every category \(j\). Each unit of allocated mass receives its type’s whole bundle.
A continuous multiple-supply WDP: bidder types \(t\) specify a permitted bundle \(S_t\) and value \(v_t\), with population mass \(\mu_t\); categories have per-capita capacities \(q_j\). Choose allocated masses \(x_t\) to maximize \(\sum_t v_tx_t\), subject to \(0\le x_t\le\mu_t\) and \(\sum_{t:j\in S_t}x_t\le q_j\).
The paper does not motivate a repeated market for replicated categories whose bundles combine length-three intervals with arbitrary pairs; the proponent offers a general standardized-capacity scenario but does not connect it specifically to this family.
fatal: False
The mirror covers the winner-determination questions in Theorems 4, 5, and 7 for their respective bundle families. It does not cover the paper’s tractability and fixed-parameter results or their single-copy classifications.
The strongest lead is Theorem 5. It says that WDP is NP-complete even when every bid has value \(1\) and permitted bundles are drawn from the union of length-three intervals, \([i,i+2]\), and arbitrary pairs, \(\{i,j\}\). The paper proves this by reducing from 2P1N-SAT. This is a particularly good anchor because the paper notes that intervals alone and bundles of size at most two alone are tractable: the hard case comes from combining those bundle families.
A concrete continuous mirror is the Continuous Multiple-Supply WDP, instantiated for Theorem 5 as \(\mathrm{CMWDP}_5\). Its instance has goods categories \(A=[n]\), per-capita supplies \(q_j\in\mathbb{Q}_{\ge0}\), and a distribution \(\mu\) over bidder types, with \(\sum_t\mu_t=1\). A type \(t\) specifies a permitted bundle \(S_t\) and a bid value \(v_t\); for the exact Theorem 5 anchor, \(S_t\in\mathcal{B}_5=\{[i,i+2]\}\cup\{\{i,j\}:i\ne j\}\) and \(v_t=1\). The support has size \(\tau\). The question is to find the mass \(x_t\) of each type that wins, maximizing revenue \(\sum_t v_tx_t\), subject to \(0\le x_t\le\mu_t\) and \(\sum_{t:j\in S_t}x_t\le q_j\) for every good \(j\). A solution is a feasible maximizing vector \(x\); equivalently, the decision version asks whether some feasible \(x\) earns at least a given rational threshold.
Here \(x_t\) is the measure of agents of type \(t\) allocated their whole bundle. It does not mean that individual agents receive fractions of bundles. The co-modification is explicit: each category has supply proportional to population, so \(q_j\) is its per-capita supply. This is a plausible regime for a large repeated market in standardized service or capacity slots, where many bidders share a bundle and price and available slots grow with the market. The number of agents can greatly exceed \(\tau\), while \(\tau\) may still grow with the number of categories.
Two further hardness anchors fit the same mirror, each with its own permitted bundle family. Theorem 4 says WDP is NP-complete, even with unit-valued bids, when every permitted bundle has the form \(\{i,i+1\}\cup\{j,j+1\}\), with \(j=i+\lfloor\sqrt n\rfloor\). The paper establishes this by reduction from the cited NP-hard WDP for \(2\times2\) rectangles [25, Theorem 9]. Its mirror, \(\mathrm{CMWDP}_4\), is the same mass-allocation problem with support restricted to that family. Theorem 7 says WDP is NP-complete, again even with unit-valued bids, when each permitted bundle consists of a consecutive pair and an arbitrary third good: \(\{i,j,k\}\subseteq A\) with \(j=i+1\). The paper establishes this using its Lemma 8 and a reduction from a restricted independent-set problem. Its mirror, \(\mathrm{CMWDP}_7\), uses precisely that bundle family. These are useful supporting anchors because they show the proposed model applies to more than the union-of-classes case in Theorem 5.
For all three mirrors, the expected result is Class A: tractable. The stated variables are the \(\tau\) supported types, and the constraints are the \(n\) good-capacity inequalities and the \(\tau\) population bounds. Thus each is a rational linear program, solvable in time polynomial in \(n,\tau\), and the input bit length. The discrete hardness in these theorems concerns packing bids against single-copy goods; the continuous mirror asks for the aggregate allocation of repeated bidder types against supply that scales with the population. It is exactly the kind of setting where indivisible per-agent awards can coexist with fractional type-level masses.
There is also a direct high-multiplicity dictionary. For a scale \(H\) making every \(H\mu_t\) and \(Hq_j\) an integer, form an auction with \(H\mu_t\) bidders of each type and \(Hq_j\) copies of each good. The finite WDP is the integer version of the displayed LP. Flooring \(Hx_t\) for each type preserves feasibility and loses less than \(\sum_t v_t/H\) in normalized revenue; for these unit-value anchors the loss is at most \(\tau/H\). This gives a concrete route from the continuous solution to large finite instances, as well as questions about convergence rates when the scale or the market model is less regular.
My weakest point is the supply regime. These are not mirrors for one-off land parcels or a fixed number of spectrum licences while the bidder population alone grows: with fixed supply, the share of winners can vanish. The positive case depends on the authors accepting a repeated, high-multiplicity auction in which category supply grows with the market. I think that is a defensible co-modification: agents still bid for the same kinds of bundles, each winner still receives an integral bundle, and the objective remains revenue-maximizing winner determination. Whether that market is a good application of this paper’s bundle restrictions is the key question for a referee.
The paper does have computational results to anchor: Theorems 4, 5, and 7 prove NP-completeness for the WDP. So the strongest negative case cannot be that there is nothing to mirror. It has to be that the proposed population is not part of the problem these theorems study.
The formal input is a set of goods and a mapping from permitted bundles to the largest submitted bid for each bundle. The paper explicitly leaves bidders unmodelled. With the paper’s single-copy goods, growing a population of bidders while keeping the goods fixed gives a degenerate limit: if the population is normalized to mass \(1\), each good’s capacity becomes \(1/N\), where \(N\) is the population size. Any bundle uses at least one good, so the total winning mass is at most \(n/N\), which tends to zero. Keeping allocation unnormalized avoids that limit, but does not produce a distribution of winners over a continuum population.
The proponent’s best repair is to scale supplies too. That gives a coherent repeated market if each index \(j\) is treated as a category with many interchangeable copies. But that choice changes what the paper’s goods are: its ordered items are individual assets, while the repaired model orders categories of replicated assets. Repeating the whole auction \(N\) times instead gives \(N\) separate copies of the original problem. Pooling the copies creates a capacitated allocation problem over categories. In either case, the resulting LP has one variable per supported bundle-value type and one capacity constraint per category. It works for every explicit bundle family, so the gaps and incidence structures responsible for the paper’s tractability frontier do no work in the continuous model. The issue is not that the LP is easy; it is that this is a general repeated-market model, rather than a population limit already latent in the paper’s single-copy WDP.
That same objection reaches all three anchors, including their best versions. For Theorem 5, repeated bidders with types \((S,1)\), where \(S\) is a length-three interval or a pair, make sense in a market with replicated category supplies. The resulting LP answers a sensible question, but it replaces the paper’s one-shot packing of distinct goods with fractional allocation across repeated categories; the special hardness from combining two tractable bundle families disappears into the generic capacity model. Theorem 4’s bundles \(\{i,i+1\}\cup\{j,j+1\}\), with the prescribed distance, and Theorem 7’s consecutive pair plus arbitrary third good can be put into the same model. Neither supplies an independent population rationale: each still relies on the same shift from individual goods to replicated categories. The reduction-created incidence patterns in these results make especially weak guides to a naturally repeated market.
So the negative case is strongest for the paper’s stated one-shot setting: preserving its goods gives a vanishing winning share, while preventing that degeneration requires adopting a different, multi-unit market interpretation. I cannot honestly rule out that the authors would accept that interpretation—standardized repeated resources and many single-minded bidders are plausible. That is where the case against is weak: if they accept replicated category supplies as part of the problem, the proponent has a valid continuous-population mirror for all three anchors.
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.