| paper | The Good, the Bad and the Submodular: Fairly Allocating Mixed Manna Under Order-Neutral Submodular Preferences |
| authors | Cyrus Cousins, V. Viswanathan, Yair Zick |
| venue | WINE 2023 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: polynomial-time solvable · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7.1
statement extracted from the paper’s text layer
Given finite complete valuation types \(T\), item classes \(O\), rational type masses \(\mu_t\), rational per-capita supplies \(\rho_o\), and additive valuations \(v_t(B)=\sum_{o\in B}a_{t,o}\) with \(a_{t,o}\in\{-p,q\}\), choose masses \(x_{t,B}\ge0\) of type-\(t\) agents receiving integral bundles \(B\subseteq O\), subject to \(\sum_Bx_{t,B}=\mu_t\) and \(\sum_{t,B:o\in B}x_{t,B}=\rho_o\). Compute an allocation maximizing continuum leximin: maximize the lowest attained utility level, then minimize the mass at that level, then maximize the next attained level, and so on over the finite set of attainable utilities.
A configuration model with complete valuation types, continuous mass \(x_{t,B}\) over integral bundles, per-capita item-class supplies \(\rho_o\), and continuum leximin over the induced utility distribution. The natural formulation is a sequence of configuration LPs whose pricing problem selects an integral bundle for one type.
The proposed continuum leximin objective must be fixed as a finite attainable-utility-level lexicographic rule, and the repeated-resource model changes the integral matching obstruction into fractional supply constraints; the proponent sketches this consequence but does not establish its canonical finite-replica interpretation.
fatal: False
The mirror covers only Theorem 7.1 and its \(\{-p,q\}\)-additive hardness reduction. It leaves the algorithmic leximin theorem and the proportionality, EF1, MMS, Lorenz-dominance, and welfare results unmirrored.
The strongest positive case is a high-multiplicity mirror of the paper’s hardness result, Theorem 7.1. This theorem is proved in the paper, although its reduction uses the cited NP-completeness of Exact \(p\)-Dimensional Matching.
Theorem 7.1 states that computing leximin allocations is NP-hard even when every agent has additive \(\{-p,q\}\)-valuations, for any coprime positive integers \(p,q\) with \(p\ge 3\). The reduction starts from a \(p\)-dimensional matching instance with \(p\) vertex sets of size \(a\), and \(b\) hyperedges. Each vertex becomes an item, \(aq\) dummy items are added, and each hyperedge becomes an agent. That agent values its \(p\) incident vertices at \(q\), and every other item at \(-p\). If a perfect matching exists, matched agents can receive their \(p\) valued items and \(q\) dummy items, while all other agents receive nothing; everyone then gets utility \(0\). If no perfect matching exists, some agent must have negative utility in every complete allocation. Coprimality implies that a nonempty bundle of utility \(0\) must contain exactly the \(p\) valued items and exactly \(q\) negatively valued items. Thus leximin computation distinguishes the two cases.
My lead mirror is:
\[ \textsc{Mixed-Manna-Leximin}_{\infty}(p,q). \]
An instance has a finite set \(T\) of complete agent types, a finite set \(O\) of item classes, a rational population distribution \(\mu\in\mathbb{Q}_{\ge0}^{T}\) with \(\sum_{t\in T}\mu_t=1\), and rational per-capita supplies \(\rho_o\in[0,1]\) for the item classes. Type \(t\) has an additive valuation
\[ v_t(B)=\sum_{o\in B}a_{t,o}, \qquad a_{t,o}\in\{-p,q\}. \]
The item classes are still indivisible: an individual receives an integral bundle \(B\subseteq O\). What is continuous is the mass of agents receiving each bundle. A feasible allocation is a table \(x_{t,B}\ge0\), where \(x_{t,B}\) is the mass of type \(t\) receiving bundle \(B\), satisfying
\[ \sum_{B\subseteq O}x_{t,B}=\mu_t \]
for every type \(t\), and
\[ \sum_{t\in T}\sum_{B\ni o}x_{t,B}=\rho_o \]
for every item class \(o\). Thus every unit of population receives an integral bundle, while type-level bundle frequencies and item usage are fractional.
The objective is continuum leximin. Let
\[ \lambda_x(u)=\sum_{t,B:v_t(B)=u}x_{t,B} \]
be the mass receiving utility \(u\), and let \(Q_x(z)\) be the lower quantile of the resulting utility distribution. The task is to output a feasible \(x\) whose sorted utility quantile function \(Q_x\) is lexicographically maximal, reading from the least-utility end. Equivalently: maximize the essential worst utility; subject to that, minimize the mass at the worst level; then maximize the next utility level, and continue through the finitely many attainable utility levels. This is the direct limit of sorting utilities in finite populations with many copies of each type.
The regime is a large standardized workforce: there are many employees of each type, where a type records the complete pattern of which task or shift classes are valued at \(q\) and which impose cost \(-p\). The task inventory also comes in repeated classes with supply proportional to population size. For \(M\) copies of every agent type, the population is \(M|T|\), while \(|T|\) and \(|O|\) remain fixed. Clearing denominators in \(\mu\), \(\rho\), and \(x\) recovers a finite allocation of named agents and indivisible items. This is therefore a genuine high-multiplicity regime, not merely fractional utility or outcome-space continuity.
The mirror is especially plausible because it preserves the paper’s central object exactly: allocating integral bundles under mixed goods-and-chores additive valuations to optimize leximin welfare. It changes only the population representation and the inventory scale. It also asks a meaningful question about Theorem 7.1: does the NP-hardness come from the number of named agents, or from the combinatorics of the item/valuation structure?
For this mirror I expect Class A. In the reduction behind Theorem 7.1, let \(z_e\) denote the mass of edge type \(e\) receiving its \(p\) valued vertex items and \(q\) dummy items. The zero-utility constraints become fractional matching constraints such as
\[ \sum_{e\ni v}z_e=\frac1b \]
for every vertex \(v\), together with the corresponding dummy-item equation. The discrete perfect-matching obstruction is replaced by a fractional \(p\)-dimensional matching problem, which is an LP. A configuration-LP formulation is also natural for the full problem: configurations are integral bundles, while \(x_{t,B}\) gives their masses. For \(\{-p,q\}\)-valuations, the pricing problem for a utility threshold reduces to choosing suitable numbers of \(q\)-items and \(-p\)-items, so it appears amenable to polynomial separation. I would therefore expect a sequence of configuration LPs to compute the continuum leximin allocation, though that algorithm and its bit-complexity would be new results rather than claims already proved by the paper.
The mirror covers only Theorem 7.1. I would not stretch it to claim that the paper’s Lorenz, proportionality, EF1, or MMS propositions automatically become continuum theorems; those would require separate definitions and proofs.
The weakest point is that the paper itself has no population model. A referee could object that per-capita item supplies and quantile leximin introduce a new inventory regime and a nontrivial extension of the objective. That objection is real. The defence is that the extension is forced by high multiplicity: \(x_{t,B}\) is not a fractional bundle given to one agent, but the limiting frequency of integral bundles among many indistinguishable agents. The paper’s hardness reduction then provides exactly the right stress test: its integral matching obstruction plausibly dissolves into fractional matching, making the continuous question both faithful and computationally substantive.
The natural follow-up questions are whether the configuration LP admits a polynomial separation algorithm, how fast finite replicated instances converge to the continuum optimum, and whether adding indivisible organizational groups or type-specific coupling constraints restores the Theorem 7.1 hardness.
The strongest negative case is a two-branch objection. If the paper’s finite item set is retained, the continuum degenerates: finitely many indivisible items can reach only a measure-zero set of agents. Almost every agent receives the empty bundle, so the essential utility distribution is trivial; if “complete allocation” requires every agent to receive an item, feasibility itself disappears. On that reading, there is no useful continuum mirror.
The proponent’s escape is to scale item supplies with population. That is the right repair, but it also exposes the weakness of the proposed anchor. Theorem 7.1 is not merely being continuized in its population axis: its one-copy vertex constraints and one-copy dummy supply are replaced by a repeated-resource market. The central obstruction—whether individually assigned hyperedges form an integral perfect matching—has been intentionally replaced by whether mass can satisfy fractional incidence constraints. The resulting problem is a configuration or transportation LP over bundle frequencies, not a limit in which the paper’s original allocation structure remains intact.
The proposed quantile leximin objective also needs more than the paper supplies. Lexicographic maximization of a function \(Q_x\) over all \(z\in[0,1]\) is not automatically defined. A defensible formulation would first list the finitely many attainable utility levels \(u_1<\cdots<u_K\), then lexicographically optimize the associated masses \((\lambda_x(u_1),\ldots,\lambda_x(u_K))\) after maximizing the lowest attained level. That is a reasonable new objective, but it is a modelling choice, not a consequence of Theorem 7.1. Different choices about whether vanishingly small bad populations matter produce different “continuum leximin” limits.
Nor does the configuration-LP observation establish the claimed computational mirror. The pricing problem for a single threshold may be easy, but continuum leximin requires a sequence of welfare-level constraints and a precise encoding of all attainable utilities. Polynomial separation and bit-complexity still need to be proved. Thus the proponent has proposed a promising research problem, not shown that the paper’s theorem has a canonical or faithful continuous counterpart.
However, this is not enough for the requested universal negative verdict. The programme explicitly permits per-capita supply scaling when population continuization forces it, and the proposed workforce story is a sensible high-multiplicity regime: many agents share each complete valuation type, while each task class has repeated supply. Splitting a type across integral bundles is exactly what many indistinguishable copies of that type do. The disappearance of the integral matching obstruction would be a substantive Class A result, not a defect; “continuity does not help” would likewise be a legitimate result.
So I cannot honestly defeat Theorem 7.1’s anchor in every admissible scenario. The fixed-inventory mirror is degenerate, and the stated version is under-specified, but a repaired repeated-resource version is a worthwhile continuous-population question. The negative case is therefore weak precisely where it must be strongest: there is no fundamental identity, multiplicity, or continuum obstruction.
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.