| paper | d4-conf-atal-2010-0048 |
| 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: \(\mathrm{P}\), with bit running time \((m+\tau+L)^{O(1)}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.1
Given finitely many agent types \(T\) with rational masses \(\mu_t\) summing to \(1\), resource categories \(R\) with rational per-capita supplies \(b_r\), and explicitly represented bundle utilities \(u_t(B)\), is there an allocation of integral bundles to almost every agent such that each receives utility at least \(K\) and total use of each resource category stays within its supply? Equivalently, decide whether there are masses \(x_{tB}\ge 0\) satisfying \(\sum_{B\subseteq R}x_{tB}=\mu_t\), \(\sum_{t\in T,\,B\ni r}x_{tB}\le b_r\), and \(x_{tB}=0\) whenever \(u_t(B)<K\).
A society is a distribution \(\mu\) over complete bundle-utility types \(t\). Decision variables \(x_{tB}\) give the mass of type \(t\) receiving whole bundle \(B\); resources have per-capita supplies \(b_r\). The objective is to maximize the minimum utility across the population, or, at threshold \(K\), test feasibility of the corresponding rational linear program.
The mirror covers the egalitarian bundle-form threshold result in Theorem 4.1. It leaves the theorem’s Nash-product result, as well as the paper’s utilitarian and \(k\)-additive results and its inapproximability discussion, outside this mirror.
The strongest mirror is the egalitarian part of Theorem 4.1, proved in the paper. It says that \(\mathrm{ESWO}_{\mathrm{bundle}}\) is NP-complete: given agents with bundle-form utilities and a threshold \(K\), decide whether some allocation gives every agent utility at least \(K\), that is, whether \(\min_i u_i(X_i)\ge K\). The theorem also proves NP-completeness for the bundle-form Nash-product threshold problem, which I leave outside this mirror. [Theorem 4.1 in the paper](https://ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/13_05_FP_0328.pdf)
Call the proposed mirror Continuous Egalitarian Bundle Allocation. An instance has a finite set \(T\) of supported agent types, rational masses \(\mu_t\ge0\) summing to \(1\), resource categories \(R\) with rational per-capita supplies \(b_r\), and, for each type \(t\), its bundle utility function \(u_t(B)\) for \(B\subseteq R\). A type is the complete utility function over bundles, so agents of the same type are indistinguishable in every respect used here. Given rational \(K\), ask whether the unit mass of agents can be assigned integral bundles so that resource use stays within each supply \(b_r\) and almost every agent receives utility at least \(K\).
A solution can be given by masses \(x_{tB}\ge0\), where \(x_{tB}\) is the mass of type \(t\) assigned bundle \(B\). It must satisfy
\[
\sum_{B\subseteq R}x_{tB}=\mu_t,\qquad
\sum_{t\in T,\;B\ni r}x_{tB}\le b_r,
\]
and \(x_{tB}=0\) whenever \(u_t(B)<K\). The fractions describe how many agents receive each whole bundle; no individual receives a fractional bundle. This preserves the paper’s maximin objective as the essential minimum utility across the population.
The regime is a large, recurring allocation system: for example, a regional agency assigning combinations of indivisible support services to many households whose complete bundle valuations fall into a modest number \(\tau\) of profiles. There might be hundreds of thousands of households but only tens or hundreds of types. Resource inventories grow with the cohort, so \(b_r\) records supply per person. This inventory scaling is a co-modification needed to keep scarcity meaningful as the population grows. It is plausible for recurring programs with replenished stocks; it is a poor fit for a one-off allocation from a fixed, tiny inventory.
For fixed \(K>0\), the question is rational LP feasibility over the bundles with \(u_t(B)\ge K\). With bundle-form utility data, its size is polynomial in the explicit input; when the utility lists are sparse with omitted values zero, only listed positive-utility bundles can qualify. The maximum egalitarian value can likewise be found by checking the finitely many utility values in the input. I therefore expect this mirror to be tractable, Class A. It offers a concrete way the finite NP-hardness could dissolve: the continuum permits each repeated type’s mass to be split among whole bundles, removing the integer coordination between individual agents.
The authors should recognize this as their allocation problem: agents still receive resource bundles, resources remain nonshareable, utility remains bundle-based, and the criterion remains egalitarian welfare. The mirror changes the population representation and scales the stock with it. Its weakest point is that this is an atomless relaxation: a feasible mass assignment need not be exactly realizable by a finite cohort with integer type counts and inventories. That gap motivates follow-up questions about rounding guarantees for finite high-multiplicity instances, and about where tractability stops when utilities use a compact representation such as the \(k\)-additive form, whose bundle-separation problem may be hard.
The hardest anchor to defeat is the egalitarian part of Theorem 4.1. Its strongest mirror is also clear: group agents with identical bundle utilities into types, scale resource supplies with population size, and ask whether every positive-mass type can be assigned whole bundles worth at least \(K\). The resulting feasibility problem is an LP over type–bundle masses. For explicitly listed bundle utilities, it is polynomial in the input size, and splitting a type’s mass among bundles is exactly what an atomless high-multiplicity model permits.
The skeptical case is that this mirror fits recurring allocation systems with replenished stocks much better than the paper’s one-off allocation of distinct, nonshareable resources. In the paper’s hard instances, positive utility requires resources; keeping a fixed finite stock while the population grows makes positive maximin thresholds impossible. Scaling supplies avoids that collapse, but narrows the setting to allocations where resource capacity grows with the cohort. If utility profiles are also highly varied, the number of complete types may grow with the population, weakening the high-multiplicity premise.
Those points limit the mirror’s reach, but they do not defeat it under this programme’s rules. Scaling per-capita supplies is an allowed co-modification, and recurring allocations of households to combinations of services are plausible. Defining a type by its complete bundle utility handles heterogeneity correctly. The LP is a real computational question about the population, not continuity in the outcome. A compact utility encoding might make pricing difficult, but that shifts the question to another representation rather than invalidating the bundle-form mirror.
So the honest negative case is weak: the anchor survives. I can argue that this mirror covers a narrower regime than the paper’s full resource-allocation model, but I cannot credibly argue that no worthwhile continuous mirror exists in any scenario.
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.