| paper | Towards Envy-Freeness Relaxations for General Nonmonotone Valuations |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given finite agent types \(T\) with rational masses \(\mu_t\), repeated item classes \(J\) with rational per-capita supplies \(\sigma_j\), a finite deletion-closed bundle catalogue \(\mathcal B\), and valuations \(v_t(B)\in\{0,-1\}\), find or decide existence of nonnegative masses \(y_{t,B}\) satisfying \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B}y_{t,B}B_j=\sigma_j\), such that whenever \(y_{t,B}>0\), \(y_{u,D}>0\), and \(v_t(B)<v_t(D)\), either some \(j\) with \(B_j>0\) satisfies \(v_t(B-\mathbf e_j)\ge v_t(D)\), or some \(j\) with \(D_j>0\) satisfies \(v_t(B)\ge v_t(D-\mathbf e_j)\).
High-multiplicity fair division with a distribution over complete negative-Boolean agent types, mass assigned to whole repeated bundles, and per-class item-balance constraints; items remain indivisible and valuations are not averaged.
With fixed manna, almost all continuum agents receive the empty bundle; the nondegenerate model therefore needs repeated anonymous item classes, and its support-wise EF1 constraints are nonconvex. Theorem 3's explicit-instance polynomial algorithm does not automatically yield a compressed algorithm independent of the clone denominator.
fatal: False
The mirror covers only Theorem 3's polynomial-time result for negative Boolean valuations. Theorem 1, Theorems 4, 13–16, and the SSP existence results are not covered because they lack the required explicit named complexity classification; cake-cutting remains outside the population-continuization scope.
The strongest positive case is a high-multiplicity mirror of the paper’s negative-Boolean EF1 result.
The anchor is Theorem 3, proved in this paper: “Given a fair division instance with negative Boolean valuations, Algorithm NegBooleanEF1 returns an EF1 allocation in polynomial time.” This is the paper’s only unambiguous named \(P\)-time result. I would not use Theorems 14 or 15 as computational anchors: they prove existence, but do not state a complexity classification.
Call the mirror Typed Negative-Boolean EF1\(_\infty\). An instance has finitely many complete agent types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), finitely many repeated item classes \(J\), rational item supplies \(\sigma_j\) per unit population, and a finite deletion-closed catalogue \(\mathcal B\subseteq\mathbb Z_{\ge0}^{J}\) of indivisible bundle configurations. Type \(t\) has a valuation \(v_t(B)\in\{0,-1\}\) for every \(B\in\mathcal B\) and every one-item deletion \(B-e_j\).
The decision variable is \(y_{t,B}\ge0\), the mass of type \(t\) receiving the whole indivisible bundle \(B\). It must satisfy
\(\sum_{B\in\mathcal B}y_{t,B}=\mu_t\) for every \(t\),
and
\(\sum_{t,B}y_{t,B}B_j=\sigma_j\) for every item class \(j\).
The solution is support-wise EF1: whenever \(y_{t,B}>0\), \(y_{u,D}>0\), and \(v_t(B)<v_t(D)\), there must be an item class \(j\) such that either \(B_j>0\) and \(v_t(B-e_j)\ge v_t(D)\), or \(D_j>0\) and \(v_t(B)\ge v_t(D-e_j)\). Thus every positive-mass agent is EF1 toward every other positive-mass agent. The task is to output such a \(y\), or report infeasibility.
This is recognisably the authors’ problem. EF1 remains a statement about complete bundles and single-item removal; only the population is aggregated. A rational clone expansion gives the bridge exactly: choose a common denominator \(N\), create \(N\mu_t\) agents of type \(t\) and \(N\sigma_j\) item copies of class \(j\), and replace \(y_{t,B}\) by \(Ny_{t,B}\) agents receiving \(B\). Conversely, any typed finite allocation induces \(y\). No individual receives a fractional item, and valuations are not averaged.
The regime is plausible in settings with millions of users but a small number \(\tau\) of complete need or acceptability types—say, a large service platform assigning repeated discrete packages, or a national allocation of standardised aid bundles. Agents of one type agree on the acceptability of every bundle, not merely on a few marginal values. The repeated-item assumption is likewise natural where \(|J|\) is small and supplies scale as \(\Theta(N)\). It is essential: keeping only \(O(1)\) items while \(N\) grows would make the fairness question degenerate.
I expect this mirror to be Class A, at least for an explicit bundle catalogue. The paper’s \(\{0,-1\}\)-valued structure is unusually coarse, and the individual operations of NegBooleanEF1 should plausibly lift to mass transfers between bundle configurations. The target would be a runtime polynomial in \(\tau\), \(|J|\), \(|\mathcal B|\), and the encoding length \(L\), independent of the denominator \(N\). With an implicit bundle catalogue, the central follow-up is a configuration/separation problem: can one find EF1-compatible bundles without enumerating exponentially many configurations?
The weakest point is substantial. Theorem 3’s polynomial runtime does not itself imply polynomial time in the compressed mass representation: expanding rational masses may create exponentially many clone agents, and support-wise EF1 is a nonconvex compatibility condition rather than an ordinary LP constraint. For unrestricted negative-Boolean valuations, the required configuration oracle might itself be hard. So the honest claim is that Theorem 3 supplies a strong, author-recognisable Class-A candidate, not that this paper has already proved the continuous algorithm.
The mirror deliberately covers only Theorem 3. Theorem 1, Theorems 4, 13–16, and the SSP results remain outside the main claim: they concern existence, non-existence, or algorithms without the required explicit complexity classification. Cake-cutting in the related work is not a collision, because it continuizes the resources or outcomes; this proposal continuizes the population while retaining indivisible outcomes.
Theorem 3 is the only serious anchor, but its proposed mirror quietly changes the problem in two fundamental ways.
In the paper, the manna \(M\) is a finite set of indivisible items and valuations are arbitrary functions \(v_i:2^M\to\{0,-1\}\). If one continuizes only the population, \(M\) remains fixed while the number of agents grows. Then at most \(|M|\) agents can receive nonempty bundles, so their population mass tends to zero. Almost every agent receives \(\varnothing\), whose value is \(0\). Under any almost-everywhere continuum interpretation, the EF1 question therefore collapses to the empty allocation. If exceptional zero-mass agents must still be tracked, the model has retained the individual agents that continuization was supposed to remove.
The proposed rescue scales the item supply as well, using repeated item classes and a bundle catalogue. That is a coherent high-multiplicity allocation problem, but it is not the high-multiplicity version of Theorem 3. Arbitrary negative-Boolean valuations may distinguish every item copy. To obtain finitely many item classes and a fixed catalogue, one must impose anonymity under permutations of copies and make valuations depend only on class counts. This is a new valuation domain, not the unrestricted domain for which Theorem 3 was proved. If item identities are retained, the catalogue and the complete valuation descriptions grow with the number of copies, defeating the fixed-type compression.
The clone correspondence does not repair this gap. Expanding rational masses gives a finite allocation, but the theorem’s polynomial algorithm is polynomial in the explicit number \(N\) of agents. It gives no algorithm polynomial in \(\log N\), the natural requirement for a compressed high-multiplicity input. Conversely, compressing the allocation into \(y_{t,B}\) introduces constraints of the form
\[ y_{t,B}>0\ \wedge\ y_{u,D}>0 \quad\Longrightarrow\quad \text{the pair }(t,B),(u,D)\text{ is EF1-compatible}. \]
Equivalently, every incompatible pair imposes a disjunctive support constraint such as \(y_{t,B}y_{u,D}=0\). The masses matter only through whether they are zero; an arbitrarily small positive mass creates exactly the same obligation as a large mass. Thus the exact continuum formulation is not an aggregate fairness condition or an LP over masses. It is a configuration-support selection problem followed by a transportation problem. Replacing it by expected or mass-weighted envy would remove this pathology, but would no longer mirror Theorem 3’s ex-post EF1 guarantee.
So the proponent has identified a possible new research problem, not a computational consequence of this paper. Under the programme’s strict population-only scope, the faithful mirror degenerates, while the nondegenerate version requires a second high-multiplicity assumption on the items and a substantially different valuation model.
That said, the universal negative claim is not airtight. A setting with millions of agents, repeated standardized bundles, and finitely many anonymous negative-Boolean need types is genuinely plausible. Its compressed EF1 problem could be worthwhile precisely because the support constraints may reveal new complexity. The strongest defensible conclusion is therefore that the proposed anchor does not establish a worthwhile mirror of Theorem 3; it does not honestly prove that no broader fair-division 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.