| paper | d4-conf-atal-2013-0348 |
| 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: Exactly solvable in polynomial time in \(m,\tau,L\), achieving approximation factor \(1\) with supply relaxation \(0\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given \(m\) goods with rational per-capita supplies \(b_\ell\), and \(\tau\) types with rational masses \(\mu_t\) summing to \(1\), where type \(t\) has value \(v_t\) and an integral demanded bundle \(d_t\in\mathbb{Z}_{\ge 0}^m\), choose served masses \(x_t\in[0,\mu_t]\) to maximize \(\sum_t v_t x_t\), subject to \(\sum_t d_t(\ell)x_t\le b_\ell\) for every good \(\ell\).
A society is a distribution \(\mu\) over single-minded bidder types, each fully specified by its value \(v_t\) and integral bundle \(d_t\). The decision variable \(x_t\) is the mass of type \(t\) served; each served unit receives the whole bundle. Per-capita supply constraints bound total mass allocated across types.
The mirror covers Proposition 1’s single-minded welfare-allocation problem and its graph reduction. It leaves aside the truthful-mechanism results, including Theorems 1–4 and the approximation guarantees for submodular and general bidders.
My lead is a continuous version of the welfare-allocation problem behind Proposition 1. The paper proves that, with \(m\) goods, it is NP-hard to approximate social welfare within a factor better than \(m^{1/2}\), even when supply may be increased by a factor \(1+\epsilon\) for any \(\epsilon<1\). The proposition is proved here, using the reduction from maximum independent set: goods correspond to graph edges, and each single-minded bidder wants the edges incident to one vertex.
A plausible high-multiplicity setting is a large allocation of spectrum rights across regions to repeated classes of standardized operators. A class is fully described by the bundle it wants and its value for that bundle; operators in the same class share both. With \(N\) operators and \(\tau\) classes, take \(N\) much larger than \(\tau\), with supplies scaling with the population. This is a specific regime for standardized buyers, not a claim that ordinary spectrum auctions always have high multiplicity.
Continuous Single-Minded Welfare (CSMW). An instance has \(m\) goods, per-capita supplies \(b_\ell\), and \(\tau\) types. Type \(t\) has population mass \(\mu_t\), an integral demand bundle \(d_t\in\mathbb{Z}_{\ge 0}^{m}\), and value \(v_t\) per served member, with \(\sum_t\mu_t=1\). Choose \(x_t\in[0,\mu_t]\), the mass of type \(t\) receiving its demanded bundle; the rest receive nothing. Each served member still gets the whole integral bundle \(d_t\). Find \(x\) maximizing
\[
\sum_t v_t x_t
\quad\text{subject to}\quad
\sum_t d_t(\ell)x_t\le b_\ell \quad\text{for every good }\ell.
\]
This is the continuous-population version of the proposition’s underlying welfare-allocation problem. The discrete-to-continuous dictionary is direct: for \(N\) agents, set \(\mu_t=N_t/N\) and \(b_\ell=S_\ell/N\), where \(N_t\) is the number of agents of type \(t\) and \(S_\ell\) is the supply. To mirror the proposition’s resource-augmentation allowance, one could permit returned allocations to use up to \((1+\epsilon)b_\ell\) while comparing their welfare with the optimum at \(b\).
I expect Class A: tractable. CSMW is a rational linear program with one variable per type. It finds the exact optimum under the original supplies, so it also meets the proposition’s approximate-welfare target without using the permitted supply augmentation. The graph reduction makes the change especially clear: with equal type masses, scaling \(x_u\) by the number of types yields variables \(y_u\in[0,1]\) and edge constraints \(y_u+y_v\le1\). The discrete independent-set choice requires \(y_u\in\{0,1\}\); the continuous problem permits fractions and is an LP. The goods and each individual’s bundle remain discrete—the fractional quantity is how much of a type cohort is served.
This mirror covers Proposition 1’s welfare hardness and its single-minded reduction, not the paper’s truthful-mechanism results. Further questions include the welfare loss when an LP solution must be rounded to serve a finite number of agents per type, and whether useful truthfulness guarantees survive when reports and payments are made for large cohorts.
My weakest point is that the reduction has a distinct type for each graph vertex, so \(\tau\) grows with the hard instance. Repeating each type many times gives a genuinely large population relative to its support, but that does not make the hard instance itself a fixed-support limit. The case is therefore for a continuous mirror of the stated allocation problem across a high-multiplicity regime, not for every finite auction instance or for the paper’s full mechanism-design agenda.
The only real anchor is Proposition 1 and its reduction from maximum independent set. The strongest case against it is that the reduction’s combinatorics live in the *distinct types*: each graph vertex is a bidder type, and each edge is a good. Replicating every type many times makes the population large, but leaves the hard structure in the type support. In the proposed continuous model, the reduction becomes the fractional independent-set LP: after scaling, each vertex has a variable \(y_v\in[0,1]\), with \(y_u+y_v\le1\) for every edge. The relaxation discards precisely the discrete choice that made the source problem hard.
That weakens the connection to a high-multiplicity regime if the intended setting is a few recurring buyer classes: the reduction needs the support to grow with the graph. But it does not defeat the mirror. The programme counts support size as a parameter, does not require it to stay fixed, and expressly treats fractional service of a type cohort as a legitimate continuous population model. Repeating standardized buyers while scaling supplies makes the LP a sensible question about an auction regime. The fact that its answer is tractability is not a reason against it; that is exactly the kind of change a continuization is meant to expose.
The proposed LP also changes the allocation problem from indivisible bidders to divisible mass. That is a real change, but it is the natural high-multiplicity relaxation here: each unit of mass still receives an integral bundle, while the served share of a type can be fractional. The LP optimizes welfare under the original per-capita supplies, so it answers a sharper fractional question than Proposition 1’s approximation lower bound with supply augmentation. That is a meaningful computational mirror, even if it says nothing by itself about truthful mechanisms.
The best negative point is therefore about priority, not validity: the reduction’s hard instances do not become small-support instances, and the mirror does not preserve the paper’s incentive-compatibility results. But the proponent claims only a mirror of Proposition 1, and the programme requires only one good anchor. I can’t honestly turn those limitations into a case that no worthwhile continuous mirror exists. The negative case is weak here: this anchor survives.
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.