| paper | d4-conf-ecai-2024-0162 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 9
Given house categories \(H\), valuation types \(T\) with rational masses \(\mu_t\) summing to \(1\), rational valuations \(v_t(h)\), rational per-applicant supplies \(q_h\), and a threshold \(B\), decide whether there is a feasible mass assignment \(x_{t,h},x_{t,0}\geq 0\), with \(\sum_{h\in H}x_{t,h}+x_{t,0}=\mu_t\) and \(\sum_{t\in T}x_{t,h}\leq q_h\), that first lexicographically maximizes \(r(x)=\sum_{t,h:v_t(h)>0}x_{t,h}\) and the minimum positive value used, then has maximum per-capita total envy at most \(B\). Here \(y_g=\sum_t x_{t,g}\), \(v_t(0)=0\), and the envy for a type-\(t\) person assigned \(h\in H\cup\{0\}\) is \(E_t(h;x)=\sum_{g\in H}y_g\max\{v_t(g)-v_t(h),0\}\); take the maximum over every \((t,h)\) with \(x_{t,h}>0\).
A nonatomic house-allocation model with types defined by complete valuation vectors, type masses \(\mu_t\), per-applicant category capacities \(q_h\), and assignment masses \(x_{t,h}\). Each person receives at most one whole unit, while members of a type may be split across categories; the objective is to maximize positive-assignment mass, then its egalitarian threshold, then minimize the largest normalized total envy.
The mirror addresses Theorem 9’s hardness result for minimizing minimax total envy subject to maximum egalitarian welfare; it leaves the paper’s other fairness-welfare results and experiments unmirrored.
A credible mirror is the housing allocation problem for a large programme with many applicants and many units in a small set of standardized housing categories. Applicants of the same type have the same complete valuation vector over those categories; \(\mu_t\) is the fraction of applicants of type \(t\). Let \(q_h\) be the number of units of category \(h\) per applicant. Scaling unit supply with population is part of this mirror: with a fixed number of houses, a growing population could not retain the paper’s allocation problem. Each person still receives at most one whole unit, though a type’s mass can be split across categories.
My lead anchor is Theorem 9, proved in this paper. It says that, for weighted house allocation instances, finding an allocation that minimizes the maximum total envy among allocations of maximum egalitarian welfare is NP-hard; the corresponding decision problem is NP-complete. The proof reduces from Independent Set in cubic graphs. Its construction uses vertex and edge agents, vertex houses and dummy houses, with valuations set to \(\beta\) or \(\beta+1\); it establishes the graph’s independent-set condition through whether an allocation with maximum total envy at most \(1\) exists. The reduction is the authors’ result; the source NP-hardness of Independent Set is cited.
Here is the continuous problem I would hand to a prover. An instance consists of a finite set \(H\) of house categories, a finite set \(T\) of applicant types, nonnegative rational valuations \(v_t(h)\), rational type masses \(\mu_t\) summing to \(1\), and rational per-applicant supplies \(q_h\). A feasible allocation is a mass matrix \(x_{t,h}\geq 0\), together with \(x_{t,0}\geq0\) for unassigned applicants, satisfying \(\sum_{h\in H\cup\{0\}}x_{t,h}=\mu_t\) and \(\sum_t x_{t,h}\leq q_h\). The mass entries describe how many members of a type receive each whole category of unit; they do not give anyone a fractional house.
For an allocation \(x\), let \(y_h=\sum_t x_{t,h}\). Define its positive-assignment mass as \(r(x)=\sum_{t,h:v_t(h)>0}x_{t,h}\), and its egalitarian threshold as the smallest positive \(v_t(h)\) used by positive mass, or \(0\) if no positive-value assignment is made. As in the paper’s \(k\)-egalitarian convention, first maximize \(r(x)\), then maximize that threshold. For an individual of type \(t\) assigned category \(h\), define per-capita total envy as \(E_t(h;x)=\sum_{g\in H}y_g\max\{v_t(g)-v_t(h),0\}\), taking \(v_t(0)=0\) for unassigned people. Continuous Minimax Envy at Max Egalitarian Welfare asks for a feasible \(x\) that is lexicographically optimal on those two welfare measures and minimizes the maximum \(E_t(h;x)\) over every type-category pair used by positive mass, including unassigned mass. Dividing discrete total envy by population size gives this per-capita quantity. A decision version adds a threshold \(B\) and asks whether such a welfare-optimal allocation exists with maximum envy at most \(B\). Complexity should be measured in \(|H|\), \(\tau=|T|\), and the input bit length.
This is recognizably the paper’s question: it retains one-unit assignments, envy against other people’s assigned units, the minimax-total-envy objective, and the egalitarian-welfare restriction. The scenario is plausible where both applicants and unit supply grow while standardized categories and applicant profiles are much fewer than people. I would tentatively expect continuum-specific hardness (Class C): for a fixed allocation support, the envy expressions are linear in the assigned masses, but deciding which type-category assignments receive positive mass creates a combinatorial support choice. The theorem’s graph construction points to where that choice might matter, but it does not prove hardness of this continuous problem.
The weak point is exactly that gap. The reduction’s agents encode graph vertices and edges, often as distinct valuation types; fractional mass assignments may undo the indivisible choices that make its Independent Set reduction work. A fresh reduction would be needed for Class C, while a formulation that handles support choices efficiently could instead put the mirror in Class A. I would test whether the decision problem is polynomial or fixed-parameter tractable in \(\tau\), whether type splitting yields a convex formulation, and how the continuous optimum relates to replicated finite instances. This case covers Theorem 9 only; it makes no claim about mirroring the paper’s other results.
The best negative case is that Theorem 9’s reduction is built from individually specified graph roles: a house for each vertex and separate valuation profiles for vertices and edges. In the reduction, both the alternatives and the number of types grow with the graph. That sits uneasily with the proposed setting of many applicants sharing a small set of standardized profiles and house categories. To keep the reduction intact, the mirror needs many increasingly fine categories and types; to keep the proposed high-multiplicity regime, it loses the reduction’s direct connection to the theorem.
That is a real limitation on the anchor, but it does not defeat the mirror. The housing-program scenario is plausible, and the proposed mass matrix preserves one whole unit per recipient, capacity constraints, and envy against the units actually allocated. Scaling category supply with population is a co-modification the programme explicitly permits. The paper’s envy objective also depends on valuations and assignments, not on agent identities, so grouping agents with identical complete valuation vectors does not discard information the objective uses.
Nor can I turn the gap in the reduction into a reason not to ask the question: whether fractional type assignments erase the hardness is precisely a computational question, and an easy answer would still be a useful result. I see no existing continuous-computation result here that makes the mirror a restatement. So the negative case against this anchor is weak. I can question how closely the proposed regime tracks Theorem 9’s hard instances, but I cannot honestly argue that no worthwhile continuous mirror exists.
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.