| paper | d4-conf-atal-2017-0067 |
| 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 under the stated explicit-table encoding. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given a finite set of complete utility types \(T\) with rational masses \(\mu_t\), a finite set of good types \(G\), rational per-capita supplies \(q_g\), and utility functions \(u_t\), decide whether there are assignment masses \(x_{t,B}\ge 0\) for integral bundles \(B\subseteq G\) such that \(\sum_{B\subseteq G}x_{t,B}=\mu_t\) for each \(t\), \(\sum_{t\in T,\,B\ni g}x_{t,B}=q_g\) for each \(g\), and every bundle receiving positive mass gives the same utility. The population has unit mass, and all goods are allocated.
A nonatomic population of unit mass is divided among complete utility types \(t\in T\), with type mass \(\mu_t\). Each person receives an integral bundle \(B\subseteq G\); the decision variables \(x_{t,B}\) give the mass of type \(t\) receiving \(B\), while \(q_g\) specifies the per-capita supply of each good type. The objective is to decide whether a feasible assignment has continuous Atkinson index zero.
The mirror covers Proposition 2's perfect-equality decision problem. It leaves the distributed-deal convergence and limitations in Proposition 3 and Theorems 4, 5, and 12 unaddressed.
The strongest positive case is Proposition 2. It is proved in this paper, using the NP-hardness of Partition cited from elsewhere. The proposition says that Perfect Index Optimisation—given a resource-allocation scenario, decide whether some allocation has Atkinson index \(I=0\)—is NP-hard even with just two agents and additive utilities. In the paper’s reduction, both agents value each good \(g\) at the Partition weight \(s(g)\), so their utilities are equal exactly when the goods split into two subsets of equal total weight.
A direct high-multiplicity version keeps each person’s bundle integral while making the population and supplies continuous. A type is a complete utility function \(u_t\); \(\mu_t\) is the fraction of the population with that type. Let \(G\) be a finite catalog of good types and \(q_g\) the per-capita supply of good \(g\). The decision variables \(x_{t,B}\) give the mass of type \(t\) assigned the integral bundle \(B\subseteq G\). They satisfy \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}=q_g\). The continuous Atkinson index is the index of the resulting distribution of individual utilities; for positive utilities it is \(1-\exp(\sum_{t,B}x_{t,B}\ln u_t(B))/\sum_{t,B}x_{t,B}u_t(B)\), with the paper’s convention for the all-zero case. It is zero precisely when all assigned mass receives the same utility.
Call the resulting decision problem Continuous Perfect Index Optimisation: given rational type masses, rational per-capita supplies, and utility functions, is there a feasible \(x\) whose positive-mass assignments all have one common utility \(\lambda\)? Its objective is perfect equality; equivalently, it asks whether the minimum continuous Atkinson index is zero.
The paper’s reduction carries over exactly. Given Partition weights \(s(g)\), use one type of mass \(1\), additive utility \(u(B)=\sum_{g\in B}s(g)\), and supply \(q_g=1/2\) for every good. If all assigned mass has utility \(\lambda\), then \(\lambda=\sum_B x_Bu(B)=\frac12\sum_gs(g)\); thus any bundle receiving positive mass is a Partition subset. Conversely, a balanced subset and its complement can each receive mass \(1/2\), giving every person the same utility and meeting every supply exactly. So this continuous problem is NP-hard, already with \(\tau=1\) and additive utilities. In a finite population of even size \(n\), it corresponds to \(n/2\) copies of each good type and \(n\) agents of the same type. The hardness comes from the goods and their binary-encoded weights, not from a large or diverse population. I expect hardness to transfer (Class B) for this anchor.
The regime is plausible for a large platform, housing system, or employer distributing standardized categories of resources among many people whose full valuations fall into a small number of profiles. The population may be large while \(\tau\) stays small; the catalog size \(m\) and the bit length \(L\) of values and supplies remain explicit parameters. Mass is the fraction of a cohort assigned each bundle. Every person still receives an integral bundle; only the cohort’s assignment shares and per-capita supplies are fractional. This mirrors the paper’s underlying question about equality among agents, rather than replacing it with fractional utility or outcome lotteries.
This case covers Proposition 2 alone; it does not claim that the paper’s distributed-deal convergence results automatically extend to a continuum. It raises further questions: how the full minimum-Atkinson optimization problem behaves in \(m,\tau,L\); what population size suffices to realize a rational continuous solution exactly; and whether mass-level Atkinson deals can guarantee convergence when the allocation state space is no longer finite.
The main weakness is the resource-scaling assumption: the mirror treats goods as standardized types whose supplies grow with the population. That fits repeated catalogs and high-multiplicity inventory, but not a setting where every good is a unique one-time object. There is also a textual caveat in the paper: its allocation definition states pairwise disjointness but does not explicitly require every good to be assigned. Proposition 2’s reduction needs complete allocation; if free disposal were allowed, assigning nothing would give all-zero utilities and hence \(I=0\) under the paper’s convention. The mirror therefore follows the complete-allocation interpretation used by the prose and proof.
The strongest objection is a defect in the paper’s formal definition. Section 2.1 requires agents’ bundles to be pairwise disjoint, but does not require every good to be assigned. Under that definition, the allocation giving every agent the empty bundle is allowed; by the paper’s convention, its Atkinson index is \(0\). So PIO is always a YES-instance, and Proposition 2’s reduction from Partition only works if allocations must use all the goods. A continuous mirror of the literal problem would therefore have nothing computationally interesting to capture.
That objection does not defeat the proponent’s repaired mirror. Complete allocation is the natural reading of the paper’s prose and proof, and the repair carries over cleanly: with one type, additive weights \(s(g)\), and per-capita supply \(1/2\) of each good, equal utility for all assigned mass forces every bundle receiving positive mass to have value \(\frac12\sum_g s(g)\). Such a bundle is a Partition subset. Conversely, a partition lets half the mass receive each side. Allowing fractional cohort assignments does not dissolve the hardness; the support still has to contain a bundle witnessing the partition. This is a meaningful high-multiplicity question, even though its hardness comes from the goods.
So the formal loophole is the only substantial negative point I can make, and it is not enough to reject a continuous mirror the authors would recognize. I cannot honestly defeat this anchor: under the intended complete-allocation model, the continuous version is well-posed and inherits the NP-hardness.
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.