| paper | d4-conf-aaai-2014-0362 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\); feasibility is \(\mathrm{NP}\text{-complete}\), even for \(\tau=1\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given finite good categories \(G\), complete additive-valuation types \(T\), rational type masses \(\mu_t\) summing to \(1\), rational per-capita supplies \(q_g\), and rational values \(v_t(g)\), assign mass \(x_{t,b}\ge 0\) of each type \(t\) to integral bundles \(b\in\mathbb{N}^{G}\), using finitely many bundles. Require \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}x_{t,b}b_g=q_g\), and \(v_t(b)\ge v_t(b')\) whenever \(x_{t,b}>0\) and \(x_{s,b'}>0\). Decide whether such an envy-free allocation exists and, if it does, compute one maximizing \(\sum_{t,b}x_{t,b}v_t(b)\).
A high-multiplicity fair-division model with a finite set of complete valuation types, masses \(\mu_t\), indivisible bundles \(b\in\mathbb{N}^{G}\), and supplies \(q_g\) per unit population. The allocation variables \(x_{t,b}\) split each type’s mass among bundles, enforce exact envy-freeness, and maximize total welfare.
The theorem’s distinctive guarantee concerns the highest-value assignment under atomless random valuations; the proposed mirror asks a deterministic welfare-maximizing envy-free allocation problem over repeated types, so that probability guarantee has no direct counterpart.
fatal: False
The mirror covers the envy-free allocation and welfare-maximization question connected to Theorem 2; it leaves Theorem 1’s random nonexistence bound, the distribution-specific probability thresholds, and the empirical phase-transition runtime results unmirrored.
The best positive case is narrow: Theorem 2, proved in this paper, is the only named result I would use as an anchor. It assumes [A2]: for each good, every agent has probability \(1/n\) of being its unique highest valuer, and a winning agent’s expected value exceeds a losing agent’s by fixed constants. It proves that when \(n=O(m/\ln m)\), an envy-free allocation exists with probability tending to \(1\). The proof gives a specific allocation: give each good to its highest-valuing agent. That allocation maximizes utilitarian welfare and is envy-free with high probability. Computing it takes \(O(nm)\) comparisons. The paper has no numbered worst-case result classifying EF allocation as NP-hard, in P, or otherwise; this theorem is a constructive, distributional algorithmic result. The cited hardness result of Bouveret and Lang is prior work, not a numbered result in this paper.
The mirror I would put to a prover is Continuous EF Welfare Allocation. An instance has a finite set \(G\) of good categories, a finite set \(T\) of agent valuation types, rational masses \(\mu_t\) summing to \(1\), additive rational values \(v_t(g)\), and rational supply \(q_g\) of copies of each category per unit population. Each individual still receives an integral bundle \(b\in\mathbb{N}^{G}\). The decision variable \(x_{t,b}\) is the mass of type \(t\) receiving bundle \(b\).
Find a feasible allocation, or report that none exists, and among feasible allocations maximize
\[ \sum_{t\in T}\sum_{b\in\mathbb{N}^{G}} x_{t,b}\,v_t(b), \qquad v_t(b)=\sum_{g\in G}v_t(g)b_g, \]
with finite support in the bundles used. Feasibility requires
\[ \sum_b x_{t,b}=\mu_t,\qquad \sum_{t,b}x_{t,b}b_g=q_g\quad\text{for each }g. \]
It also requires envy-freeness: whenever \(x_{t,b}>0\) and \(x_{s,b'}>0\), \(v_t(b)\ge v_t(b')\). Thus every positive-mass group weakly prefers its own bundle to every bundle assigned to anyone else. This keeps goods indivisible within each person’s bundle while allowing mass to divide across bundle assignments. The supplies scale with population, as they must for a population limit with goods still available.
This is a plausible continuous form of the paper’s computational question: can one compute a welfare-best envy-free allocation when the society is represented by masses of valuation types? In a high-multiplicity regime, repeated customer or household profiles and many copies of product categories make that question meaningful. Theorem 2 gives the stochastic motivation: in its regime, a welfare-maximizing rule itself produces an EF allocation. My expectation for the general problem is Class C, with tractable special cases possible under distributional or structural assumptions. The theorem does not establish that classification. Further questions include whether its welfare-maximizing rule has a continuous analogue under finite-support type distributions, how the per-capita supply needed for EF scales, and when mass allocations can be rounded to finite high-multiplicity instances.
The weak point is substantial: in the paper, non-atomic random valuations make agents’ complete valuation vectors almost surely distinct. Replacing them with a small number of repeated types changes the model. In particular, splitting one type’s mass among different bundles can make members of that type envy one another. The proposed problem addresses that directly through its EF constraints, but Theorem 2 does not prove that the continuous version is tractable or that its probability bounds survive. The mirror is a credible new computational question suggested by the constructive result, rather than a consequence already delivered by it.
The only anchor is Theorem 2. Its proof depends on a specific random structure: each good has a unique highest-valuing individual, and that individual’s expected advantage over a nonwinner is bounded away from zero. Concentration across goods then makes the rule “give each good to its highest valuer” envy-free with high probability. The theorem supplies a simple construction, rather than a complexity classification; the paper’s hardness bump comes from experiments with finite MIP instances.
That structure fits poorly with high multiplicity. A complete type includes an agent’s entire valuation vector. Under the paper’s non-atomic valuations, almost surely every agent has a distinct type, so the support grows with the population and each type has mass \(1/n\). In an atomless limit, a good’s unique highest-valuing type has zero mass. If the model instead uses finitely many types with positive mass, copies of the maximizing type tie for each good. Dividing goods among them does not preserve the proof’s allocation: exact envy-freeness requires every positive-mass bundle assigned within a type to give that type the same utility. Concentration may make utilities close, but closeness does not meet the paper’s exact envy-free condition.
The proponent’s bundle model is the strongest repair. With per-capita supplies and integral bundles for individuals, it is a coherent continuous-population fair-division problem. But it replaces the paper’s independently sampled individual valuations with repeated type valuations and asks a new configuration-allocation question. It could be worth studying on its own; Theorem 2 neither supplies its mechanism nor gives reason to expect its probability bounds or phase-transition behavior to carry over. Approximate envy-freeness or lotteries might restore a concentration argument, at the cost of changing the question again.
So I would argue that this paper does not offer a compelling continuous mirror of its named result. The negative case is weaker against the universal claim: repeated household profiles and scaled supplies make the proposed model plausible, and the authors might recognize it as a worthwhile companion problem. I cannot honestly conclude that no scenario yields a worthwhile mirror; I can conclude that the case for this particular mirror rests on a new model, rather than on a continuization of Theorem 2’s result.
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.