| paper | Finding Fair and Efficient Allocations When Valuations Don't Add Up |
| authors | Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, Yair Zick |
| venue | SAGT 2020 |
| 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}\text{-hard}\), even for one additive type with unit mass and supply \(\tfrac12\) for every species. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.2
statement extracted from the paper’s text layer
Given a finite set \(T\) of complete weighted-OXS valuation types, rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), item species \(O\), and rational per-capita supplies \(b_o\), choose \(x_{t,S}\ge0\) for integral bundles \(S\subseteq O\) satisfying \(\sum_Sx_{t,S}=\mu_t\) and \(\sum_{t,S:o\in S}x_{t,S}\le b_o\). First maximize \(p=\sum_{t,S:v_t(S)>0}x_{t,S}\); among allocations attaining \(p\), compute one maximizing \(\sum_{t,S:v_t(S)>0}x_{t,S}\log v_t(S)\).
A bundle-configuration LP over a continuous population: type \(t\) carries mass \(\mu_t\), each configuration \(S\) is an integral bundle, \(x_{t,S}\) is its mass, item species have capacities \(b_o\), and the lexicographic objective is maximum positive mass followed by the linear configuration objective \(\sum x_{t,S}\log v_t(S)\).
The proposed objective is not the high-multiplicity limit of individual-level MNW: the faithful limit is bundle-level \(\sum_{t,S}x_{t,S}\log v_t(S)\) after maximizing positive mass, so the advertised flow formulation does not establish tractability. This bounds the algorithmic promise but does not eliminate the well-posed population-continuized question.
fatal: False
The mirror covers the MNW part of Theorem 4.2 and the welfare–EF1 target of Theorem 3.4. It leaves the leximin half of Theorem 4.2, Theorem 3.14's full equivalence, Theorem 4.1's binary-OXS flow result, and the experimental and axiomatic material unmirrored.
The strongest positive case is a high-multiplicity version of the paper’s matching-based fair allocation problem. The population, rather than the goods or bundles, is the continuous object.
Take a finite set of complete valuation types \(T\). A type includes the entire OXS description: its finite set of internal roles, all member–item weights, and all other constraints. Let \(\mu_t\) be the mass of type \(t\), with \(\sum_t\mu_t=1\). There are finitely many item species \(O\), each available at per-capita supply \(b_o\). Thus \(b_o\) is the mass of copies of item \(o\), not a divisible good: every unit of population still receives an integral bundle \(S\subseteq O\).
A mass allocation is \(x_{t,S}\ge 0\), where \(x_{t,S}\) is the mass of type \(t\) receiving the integral bundle \(S\). It satisfies \(\sum_Sx_{t,S}=\mu_t\) and \(\sum_{t,S:o\in S}x_{t,S}\le b_o\). The type’s valuation is the same assignment valuation as in the paper, \(v_t(S)\), and its realized type-average utility is \(\bar u_t(x)=\mu_t^{-1}\sum_Sx_{t,S}v_t(S)\). Fractional \(\bar u_t\) is only an average over people receiving integral bundles.
My lead anchor is Theorem 4.2, proved in this paper in Appendix A.12. It states:
For two agents with general assignment valuations, it is NP-hard to compute a leximin or MNW allocation.
The paper proves this by a Turing reduction from Partition. Given integers \(W=\{w_1,\ldots,w_m\}\), it creates \(m\) items and two groups, each with \(m\) internal members, so that each group’s assignment valuation becomes the additive valuation \(v(S)=\sum_{w_j\in S}w_j\). A leximin or MNW allocation has equal values for the two groups exactly when the Partition instance has a solution.
The continuous mirror is:
Continuum-MNW-General-OXS. Given two or finitely many valuation types \(T\), rational masses \(\mu_t\), per-capita item supplies \(b_o\), and weighted OXS valuations \(v_t\), find a mass allocation \(x\) maximizing the high-multiplicity Nash objective \(\sum_{t:\bar u_t>0}\mu_t\log \bar u_t\), after first maximizing the mass receiving positive utility. Equivalently, in a symmetric population of \(n_t\) copies of type \(t\), this is the normalized limit of maximizing \(\prod_t\bar u_t^{n_t}\).
This is recognizably the authors’ problem: it keeps the same assignment valuations, the same weighted matching interpretation, and the same MNW principle. The scenario is a large population of students, households, or institutional units with one of a small number of exact preference-and-constraint profiles, competing for course, housing, or service-slot copies whose supplies scale with population. The paper itself already motivates OXS valuations through groups of individuals and applications such as courses, housing, and public-resource allocation.
I expect this mirror to be a Class A candidate, at least in the natural per-capita-supply regime. Aggregate OXS allocation can be represented by matching-flow variables \(y_{t,r,o}\), with role capacities \(\mu_t\), item capacities \(b_o\), and utility constraints such as \(\mu_t\bar u_t\le\sum_{r,o}w_{t,r,o}y_{t,r,o}\). Maximizing \(\sum_t\mu_t\log\bar u_t\) over this flow polytope is a convex-optimization problem. Flow decomposition supplies a distribution over integral matchings, so the model has not simply replaced each person’s bundle by a fractional bundle.
Most importantly, the Partition obstruction no longer forces an entire item \(j\) of weight \(w_j\) to one side: mass of that item species can be distributed among many identical agents, while every individual still receives the item integrally. Whether the full weighted-OXS version has a polynomial exact algorithm, or whether its configuration-pricing problem is continuum-specifically hard, is an important boundary question. The additive subcase strongly suggests that the discrete NP-hardness can dissolve.
A second, more fairness-centred anchor is Theorem 3.4, also proved here. It states:
For matroid rank valuations, a utilitarian-optimal allocation that is also EF1 exists and can be computed in polynomial time.
The proof first computes a clean utilitarian optimum using the matroid-intersection construction of Theorem 3.7, then applies envy-induced transfers while preserving welfare and eventually reaching EF1.
Its continuous mirror is:
Continuum-Matroid-EF1. Given finite matroid-rank valuation types \(T\), masses \(\mu_t\), and per-capita item supplies \(b_o\), find a mass allocation \(x_{t,S}\) that is clean, maximizes \(\sum_{t,S}x_{t,S}v_t(S)\), and is EF1 for every pair of bundles in its positive-mass support: for all \(x_{t,S},x_{u,R}>0\), either \(v_t(S)\ge v_t(R)\), or there is an \(o\in R\) with \(v_t(S)\ge v_t(R\setminus\{o\})\).
This asks for exactly the paper’s welfare–fairness combination, with the population replaced by a finite distribution of complete types. I would expect Class A in fixed-type regimes: matroid-intersection machinery handles welfare, and the paper’s transfer argument suggests a continuous balancing procedure whose potential is an integral analogue of \(\sum_i v_i(A_i)^2\). The delicate issue is that EF1 is a support-wise condition about integral bundles, rather than a single linear constraint.
These mirrors cover Theorems 4.2 and 3.4 only. They do not claim that the paper’s experiments or general-submodular heuristic already have continuous counterparts, and they do not continuize outcomes: bundles remain integral for every unit of mass. The per-capita supply scaling is the necessary co-modification that makes a large population meaningful.
My weakest point is the lead mirror’s choice of regime. Theorem 4.2 is hard with only two agents, so its Partition hardness is driven by indivisible weighted goods rather than by population multiplicity. If one insists on a fixed stock of unique goods, or on literal individual-level Nash welfare rather than anonymous type-average welfare, the hardness may survive and the proposed tractability argument weakens substantially. But repeated exact valuation types with per-capita supplies are a legitimate and recognizable high-multiplicity instance regime, and in that regime the paper provides a particularly clear question: does the Partition barrier disappear once the population, but not individual bundles, is continuous?
The strongest negative case attacks the proposed formulations, but it does not survive their best repairs.
For Theorem 4.2, the proposed objective is not the high-multiplicity limit of the paper’s MNW objective. With \(n_t\) identical agents of type \(t\), and \(x_{t,S}\) receiving bundle \(S\), finite MNW converges to
\[ \sum_{t,S} x_{t,S}\log v_t(S), \]
not
\[ \sum_t \mu_t\log\!\left(\frac{1}{\mu_t}\sum_S x_{t,S}v_t(S)\right). \]
The latter is Nash welfare of type-average utilities. It can assign zero utility to a positive mass of agents while remaining finite, contrary to the paper’s \(N_{\max}\) refinement. Thus the proposed flow formulation does not actually mirror Theorem 4.2, and flow decomposition does not repair the mismatch.
The faithful repair must retain bundle-level mass variables and maximize average log bundle utility, first maximizing the mass receiving positive utility. That becomes a configuration-allocation problem; the claimed flow-based convex formulation no longer follows. This is a serious defect in the proponent’s anchor, but not a decisive objection to the repaired question: the repaired problem is a legitimate high-multiplicity OXS allocation problem.
Theorem 3.4 has a related ambiguity. EF1 is imposed on every pair of realized bundles, not on type-average utilities. Replacing bundles by averages changes the criterion because, for matroid ranks, \(v_t(\mathbb{E}[\mathbf{1}_S])\) and \(\mathbb{E}[v_t(S)]\) are different objects. Retaining individual bundles gives the proponent’s support-wise EF1 condition, but that condition depends only on whether a bundle has positive mass, so an arbitrarily small exceptional mass can impose the same constraint as a large population. Moreover, the paper’s transfer proof relies on integral utility changes and a discrete potential; mass transfers destroy that termination argument.
These points show that neither proposed mirror is yet a theorem-preserving continuization. They do not, however, establish the requested universal negative. Repeated exact valuation types, per-capita supplies, and integral bundles for each individual are precisely a sensible high-multiplicity regime. The corrected MNW problem and the support-wise EF1 problem both remain recognizable computational questions, not collisions with existing continuous allocation theory.
So the honest negative verdict is weak: the proponent’s formulations need substantial repair, especially the MNW objective, but I cannot defend the claim that no worthwhile continuous mirror exists in any scenario.
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.