| paper | Fair and Efficient Allocations under Lexicographic Preferences |
| authors | Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, Lirong Xia |
| venue | AAAI 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given finite goods categories \(M\), complete-ranking types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and rational per-capita supplies \(\rho_g\), decide whether there exist masses \(x_{t,B}\ge0\) over integral bundles \(B\subseteq M\) satisfying \(\sum_Bx_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}=\rho_g\), such that every positive-support pair satisfies EFX and \(R_j(x)=\sum_{t,B}x_{t,B}\mathbf{1}[g_j(t)\in B]\) is lexicographically maximal among feasible allocations.
A configuration or mass-allocation model in which types are complete rankings plus relevant eligibility data, \(x_{t,B}\) is the mass of type \(t\) receiving indivisible bundle \(B\), \(\rho_g\) is per-capita category supply, and feasibility requires support-level EFX together with a lexicographically maximal rank signature.
Per-capita category supplies replace the paper's one-copy named-good inventory, while exact EFX retains discrete support selection; the relation between this extension and the original hardness gadgets therefore needs independent validation.
fatal: False
The mirror covers the EFX+RM and EF\(k\)+RM hardness results in Theorems 3 and 4. It leaves the EFX+PO and mechanism characterizations, the MMS algorithm, auxiliary propositions and examples, and the experiments without a canonical population-continuous computational question.
The strongest honest mirror is the paper’s EFX-plus-rank-maximality problem, with Theorem 3 as the lead anchor. The right continuization keeps bundles indivisible for each agent, but makes the population and aggregate supplies continuous.
Let \(M\) be the set of goods and \(T\subseteq \mathcal L(M)\) a finite set of complete rankings. A society is a distribution \(\mu=(\mu_t)_{t\in T}\), where \(\mu_t\) is the mass of agents of type \(t\). Let \(\rho_g\in\mathbb Q_{\ge 0}\) be the supply of good \(g\) per unit population. This is the natural scaling: a finite instance with \(n_t\) agents of type \(t\) and \(q_g\) copies of \(g\) gives \(\mu_t=n_t/n\) and \(\rho_g=q_g/n\).
A continuous allocation is a collection \(x_{t,B}\ge 0\), for \(t\in T\) and \(B\subseteq M\), where \(x_{t,B}\) is the mass of type \(t\) receiving the integral bundle \(B\). It must satisfy
\[ \sum_{B\subseteq M}x_{t,B}=\mu_t \]
and
\[ \sum_{t\in T}\sum_{B\ni g}x_{t,B}=\rho_g \]
for every \(t\) and \(g\). Thus \(x\) is fractional only at the population level: every unit of mass still receives an indivisible bundle.
For a type \(t\), write \(g_j(t)\) for its \(j\)-th-ranked good. The continuous rank-maximal signature is
\[ R_j(x)=\sum_{t,B}x_{t,B}\mathbf 1[g_j(t)\in B]. \]
An allocation is rank-maximal if \((R_1(x),\ldots,R_m(x))\) is lexicographically maximal among feasible allocations. This is exactly the paper’s signature, with numbers of agents replaced by masses.
The continuous EFX condition is also direct. Whenever \(x_{t,A}>0\), \(x_{u,B}>0\), and \(B\neq\varnothing\), every \(g\in B\) must satisfy
\[ A\succeq_t B\setminus\{g\}. \]
The continuous \(\mathrm{EF}k\) condition replaces the removal of one good by the existence of some \(S\subseteq B\), \(|S|\le k\), such that
\[ A\succeq_t B\setminus S. \]
This is not fractional allocation of outcomes: it is a distribution over ordinary integral allocations.
The regime is plausible in large course-allocation or housing-cohort settings. Imagine tens of thousands of students, but only a few dozen curriculum or priority types. Students of one type have the same ranking, eligibility, and other relevant parameters; course seats or housing slots are supplied in quantities proportional to population. The paper’s own motivation from course allocation therefore extends naturally to a high-multiplicity setting with \(N\gg |T|\). A type is not merely a preference ranking if the problem uses other data: all prices, eligibility constraints, budgets, and priorities that matter must also be included in the type.
The lead anchor is Theorem 3, proved in this paper:
“Determining whether a given instance admits an EFX and rank-maximal allocation is NP-complete.”
More fully, the input is a finite fair-division instance with lexicographic preferences; the question is whether there exists a complete allocation that is simultaneously envy-free up to any good and rank-maximal. The paper proves membership in NP and NP-hardness by reducing from \((2/2/3)\)-SAT. The reduction uses literal agents, dummy agents, signature goods, clause goods, and dummy goods. Rank-maximality forces signature and dummy assignments, while EFX ensures that clause goods can be assigned only in a way corresponding to a satisfying truth assignment.
The corresponding continuous problem is:
\(\mathsf{EFX_\infty+RM}\)-Existence. Given rational \((M,T,\mu,\rho)\), decide whether there exists a mass allocation \(x_{t,B}\) satisfying the supply constraints, continuous EFX, and continuous rank-maximality.
A YES certificate is the mass assigned to each integral bundle, together with the claim that its signature is lexicographically optimal. This is a faithful question about the paper’s underlying problem, not about its ILP encoding. The fairness condition remains pairwise and bundle-based; rank-maximality remains lexicographic optimization of first-, second-, and later-choice mass.
I would tentatively expect this mirror to be Class A in a genuine high-multiplicity regime, although that is a conjectural direction rather than a consequence of Theorem 3. The discrete reduction’s assignment choices can become mass-splitting choices. In particular, the SAT gadget may turn into a configuration or transport LP whose variables describe how much mass receives each relevant bundle. The continuous analogue might therefore be solvable by a configuration LP, column generation, or a separation oracle over ranked bundles. The main unresolved issue is that EFX is support-sensitive rather than plainly convex. If that support structure itself encodes a hard combinatorial choice, the problem could instead be Class C. Either outcome would be informative: the theorem’s NP-hardness would not automatically transfer merely because the same words “EFX” and “rank-maximal” appear.
A second worthwhile anchor is Theorem 4, also proved in this paper:
For every fixed \(k\in\mathbb N\), determining whether a lexicographic instance admits an \(\mathrm{EF}k\) and rank-maximal allocation is NP-complete.
Here \(k\) is fixed in advance and is not part of the input. The problem is in NP because a proposed allocation can be checked for both \(\mathrm{EF}k\) and rank-maximality. The paper proves NP-hardness by reducing from balanced tripartite Partition Into Triangles. Its construction forces selector goods and dummy goods into prescribed groups; the remaining main goods must be partitioned into triples, and the \(\mathrm{EF}k\) constraints ensure that each triple forms a triangle.
The matching continuous question is:
\(\mathsf{EF}k_\infty+RM\)-Existence. For fixed \(k\), given rational \((M,T,\mu,\rho)\), decide whether there is a feasible mass allocation \(x\) that is continuously \(\mathrm{EF}k\) and continuously rank-maximal.
I would again expect the natural high-multiplicity version to be substantially more amenable to continuous optimization than the discrete theorem suggests. The triangle gadget appears likely to become a fractional triangle-factor or configuration problem: mass can be distributed among allowed triples even when no integral partition into triangles exists. That makes this a particularly clean test of whether the paper’s hardness is driven by population integrality or by the alternatives and preference structure. The fixed-\(k\) condition is important; allowing \(k\) to vary with the input could introduce a separate complexity parameter.
These mirrors deliberately cover only Theorems 3 and 4. I would not claim, without further work, that the mechanism characterizations in Theorems 1, 2, 6, or 7 have a canonical continuum analogue: serial dictatorship and strategyproofness require an additional model of reports and individual-level mechanism implementation. Nor do the Mallows-model experiments themselves constitute computational anchors.
The weakest point is that continuous EFX may be viewed as an overly demanding support condition. If one type is split across several bundles, every positive-mass bundle must satisfy the EFX comparison, which can make the continuum problem less economically natural than a weaker almost-everywhere or average notion. There is also no guarantee that the NP-hardness in Theorems 3 or 4 survives fractional mass splitting. But that vulnerability concerns the answer to the mirror, not whether the mirror is legitimate. The model preserves the paper’s central objects—integral bundles, lexicographic preferences, EFX, and rank-maximality—while making the population and supply high-multiplicity. That is precisely the computational question a continuous-population version should ask.
The strongest case against the proposed mirrors is that the paper’s computational difficulty is tied to a finite inventory of individually named goods, whereas population continuization either makes that inventory disappear or changes the problem.
With the paper’s literal model, \(M\) contains one copy of each good. If the number of agents grows while \(M\) is fixed, at most \(m\) agents can receive nonempty bundles. In normalized mass terms, the nonempty population has mass at most \(m/n\), which tends to zero. Rank-maximality becomes a statement about vanishing mass, and almost everyone receives the empty bundle. EFX consequently becomes largely vacuous in the limit. Thus the literal high-multiplicity limit is not a meaningful version of either Theorem 3 or Theorem 4.
The proponent avoids this by scaling supplies per capita. But then the good universe has changed. A finite realization contains \(n\rho_g\) copies of each category, whereas the paper has one named good \(g\). If copies remain distinct, the preference rankings and rank-maximal signature change with \(n\), so there is no fixed type space. If copies are treated as identical, one has introduced a new category-level fair-division problem rather than continuized the paper’s finite allocation problem. That may be a reasonable model, but it needs independent justification; it is not forced by the paper.
More seriously, exact EFX does not become a continuous optimization constraint. In the proposed model, a forbidden pair of bundles imposes
\[ x_{t,A}>0\ \wedge\ x_{u,B}>0 \]
being impossible. Equivalently, one has a constraint \(x_{t,A}x_{u,B}=0\). The feasible region is therefore a union of faces, not a convex mass-allocation polytope. Splitting a type across bundles does not soften EFX: every bundle in its positive-mass support must be compatible with every bundle in every other positive-mass support. Preserving exact EFX therefore retains a discrete support-selection problem. Replacing it by expected or average envy would restore convexity, but would no longer mirror EFX.
This undercuts Theorem 3 in particular. The SAT gadget does not naturally become the configuration LP suggested by the proponent. Its truth-assignment choices survive as choices of which bundle patterns are allowed positive support. A continuous algorithm would have to resolve those disjunctive support choices; the fractional masses only determine how much of a chosen pattern is used.
Theorem 4 makes the difficulty especially clear. Under per-capita scaling, the triangle gadget becomes a fractional triangle-factor problem: a cohort may split its mass among several triangle bundles. That is a legitimate new question, but it is not the paper’s integral partition problem with a continuous population substituted for \(n\). It replaces “does a triangle partition exist?” by “does a fractional mixture of triangle bundles exist?” If splitting is disallowed to preserve the original combinatorics, integrality returns and the supposed continuization has done no work. If splitting is allowed, the central NP-hard witness has been replaced by a different relaxation.
This is the best negative case, but it is not decisive. The programme explicitly permits per-capita supplies and co-modelling, and large course-allocation or housing cohorts with repeated rankings are genuinely plausible high-multiplicity settings. The fractional triangle-factor interpretation could itself be a worthwhile Class A/Class C boundary problem. Thus I cannot honestly establish the requested universal claim. The proposed mirrors are vulnerable as faithful continuizations of the paper’s exact finite model, but the category-supply version remains a credible and potentially valuable continuous-population problem.
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.