| paper | d4-conf-atal-2015-0055 |
| 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: \(\mathrm{P}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 6
statement extracted from the paper’s text layer
Given \(M\) resource categories and a finite set of types \(\theta=(\succ_\theta,e_\theta)\), each with rational mass \(\mu_\theta>0\) summing to \(1\), let category supplies be \(\beta_r=\sum_{\theta:e_\theta=r}\mu_\theta\) and initial allocation be \(x^0_{\theta,e_\theta}=\mu_\theta\). A move chooses types \(\theta,\theta'\), categories \(r,s\), and \(\delta>0\) with \(x_{\theta,r},x_{\theta',s}\ge\delta\), \(s\succ_\theta r\), and \(r\succ_{\theta'}s\), then exchanges mass \(\delta\) between those cells. Given a rational threshold \(q\), does a finite sequence of such moves reach an allocation \(x\) with \(\sum_{\theta,r}x_{\theta,r}(M+1-\operatorname{rank}_\theta(r))\ge q\)?
A finite-support distribution over types defined by a strict ranking of standardized resource categories and an initial category. The decision variables are the masses \(x_{\theta,r}\) currently holding each category; each move exchanges equal positive masses between two types that strictly prefer the other's category. The objective is average utilitarian rank welfare.
A positive-mass cohort swap is a bulk operation, and the proponent does not show that finite sequences of such moves are exactly the high-multiplicity limit of finite sequences of individual bilateral deals.
fatal: False
The mirror covers the utilitarian and egalitarian welfare-threshold reachability problems in Proposition 6. It leaves the single-peaked Pareto-optimality result, welfare bounds, and experimental results outside its scope.
I would lead with Proposition 6, proved in this paper. It says that both MIN-USW-C2 and MIN-ESW-C2 are NP-complete. For each problem, the input is a house-allocation instance with an initial allocation \(A_0\) and an integer \(k\). MIN-USW-C2 asks whether some sequence of mutually improving bilateral swaps from \(A_0\) reaches an allocation \(A'\) with \(\mathrm{swu}(A')\ge k\); MIN-ESW-C2 asks the same for \(\mathrm{swe}(A')\ge k\). The authors prove hardness by reduction from Hamiltonian circuit in directed graphs with in-degree and out-degree at most \(2\); the paper cites [14] for that source problem. The utilitarian version is my lead, since its rank-based objective lifts directly to average welfare over mass.
Here is the mirror I would put to a prover. Consider a large exchange pool of interchangeable resource units, grouped into \(M\) categories. An agent type is \(\theta=(\succ_\theta,e_\theta)\): a strict ranking of the categories and the category the agent initially holds. The input is a finite support \(\Theta\) with rational masses \(\mu_\theta>0\) summing to \(1\). Thus a type’s mass is the fraction of the population with that ranking and endowment. The supply of category \(r\) is fixed at \(\beta_r=\sum_{\theta:e_\theta=r}\mu_\theta\).
A current allocation is a matrix \(x_{\theta,r}\ge 0\), where \(x_{\theta,r}\) is the mass of type \(\theta\) currently holding category \(r\). It must preserve each type’s mass and each category’s supply. Initially, \(x_{\theta,e_\theta}=\mu_\theta\). A legal mass swap chooses types \(\theta,\theta'\), categories \(r,s\), and a rational amount \(\delta>0\), with \(x_{\theta,r},x_{\theta',s}\ge\delta\), such that \(s\succ_\theta r\) and \(r\succ_{\theta'}s\). It moves mass \(\delta\) from each of those two cells to \(x_{\theta,s}\) and \(x_{\theta',r}\). A solution is a finite sequence of such swaps.
For Mass-USW-C2, set \(u_\theta(r)=M+1-\operatorname{rank}_\theta(r)\). Given a rational threshold \(q\), ask whether a finite legal sequence reaches \(x\) with \(\sum_{\theta,r}x_{\theta,r}u_\theta(r)\ge q\). This is average utilitarian welfare, the paper’s total welfare divided by population size. Mass-ESW-C2 asks whether such a sequence reaches \(x\) with \(\min_{x_{\theta,r}>0}u_\theta(r)\ge q\). These are two mirrors of the two claims in Proposition 6; Mass-USW-C2 is the lead.
A plausible regime is a large university or municipal exchange pool with many copies of a small set of standardized resource categories. For example, many participants might hold one unit of a standard item category and share one of a moderate number of rankings and initial endowments. The population can be much larger than the support size \(\tau=|\Theta|\). Mass is then the fraction of participants of each type, and swaps retain the paper’s defining constraints: each participant holds one resource, and both sides must strictly prefer what they receive. This is population continuization, not fractional assignment of each person’s outcome. The model also allows the supply of each category to scale with the population, as high multiplicity requires.
My provisional expectation is Class B, hardness transfers, because the reduction’s combinatorics are organized around resource identities and a graph path, rather than around a large count of otherwise identical agents. But the transfer is a question, not a conclusion: splitting each type’s mass could allow fractional exchanges that bypass the Hamiltonian-path obstruction. A central follow-up is whether reachability in this finite type-and-category model collapses to a flow or LP formulation, or whether the order of individually rational swaps still carries hard path structure. Other useful questions are whether fixed \(M\) or bounded \(\tau\) yields tractability, and whether a precise discrete-to-continuous dictionary can identify when replication preserves reachability.
The weakest point is that the paper’s resources are distinct indivisible objects, and its hardness gadget uses that distinctness. This mirror treats repeated units within a category as interchangeable and permits submasses of a type to trade separately. That is a meaningful high-multiplicity version of the same swap-reachability problem, but the paper’s NP-hardness proof does not establish hardness for it. I would claim only this scope: a continuous-population counterpart to Proposition 6’s two welfare-threshold reachability problems. I would not stretch it to cover the paper’s single-peaked Pareto-optimality proposition, price-of-anarchy results, or experiments.
Proposition 6 is the only computational anchor the proponent raises, in its utilitarian and egalitarian versions. The strongest objection is that the proposed mass-swap model may change what makes this paper’s reachability problem a problem.
The paper’s states are bijections between agents and individually named resources. That identity matters to the swap process: a deal moves particular objects between particular agents. In the hardness construction, for example, a unique resource \(u\) moves among agents holding distinct \(r_i\)’s, and the order of those exchanges records a path in the graph. To get repeated agent types, the proponent groups people by ranking and initial endowment. If resource identities are retained, each distinct endowment can leave a type represented by only one agent. Grouping many agents therefore requires collapsing distinct resources into categories. The resulting question concerns exchange of interchangeable commodity units, with preferences over categories. That may be a sensible model, but the paper does not establish that it is the same resource-allocation problem the authors set out to study.
There is also a mismatch in the move itself. A positive mass swap matches two whole subpopulations and exchanges their holdings at once. In an atomless population, an ordinary deal between two individuals changes zero mass; any finite sequence of such deals leaves the aggregate allocation unchanged. A nontrivial mass transition therefore represents many bilateral swaps bundled together. In a finite replica those swaps might be serialized, but the continuum transition assumes a bulk matching of cohorts. Since the paper motivates bilateral deals partly by the difficulty of coordinating exchanges, the authors might reasonably regard this as a different operation. A mean-field meeting process could preserve pairwise encounters, but then reachability would need a time and rate model; that is another modelling choice rather than a direct lift of Proposition 6.
The egalitarian mirror has an additional limit issue. The finite problem’s minimum counts a single badly served agent. In an atomless model, the corresponding essential minimum ignores zero-mass exceptions, so a badly served group of size \(1/N\) can determine the finite answer while disappearing in the limit. Requiring a positive fraction of the population to meet the threshold could repair that, but it changes the objective. The utilitarian mirror avoids this particular issue; its main vulnerability remains the interpretation of mass swaps.
This is the best case against the anchor: preserving individual resource identities leaves little room for repeated types, while making the population continuous seems to replace individual deals with cohort-level exchanges. It challenges whether the proposed models are mirrors of this paper’s distributed dynamics, rather than whether their answers would be interesting.
That challenge does not establish the universal negative the task demands. A large exchange pool with a fixed set of standardized resource categories is plausible, and a mass swap can be understood as an aggregate of many serial bilateral swaps among interchangeable units. The paper’s subject is broad enough that its authors might recognize that as their problem. High-multiplicity work would support the regime, not count against it. So the negative case is weak at its decisive point: if the authors accept cohort mass swaps as the aggregate counterpart of \(C_2\) deals, the utilitarian mirror 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.