| paper | Almost Envy-Free Allocation of Indivisible Goods: A Tale of Two Valuations |
| authors | Alireza Kaviani, Masoud Seddighin, A. Shahrezaei |
| venue | WINE 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\mathrm{P}\). Every valid instance admits a complete \(\frac{\sqrt{2}}{2}\)-EFX allocation. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 6.1
statement extracted from the paper’s text layer
Given finitely many complete types \(T\) with masses \(\mu_t\ge0\), \(\sum_t\mu_t=1\), good classes \(G\) with per-capita supplies \(\sigma_g\), and restricted-additive values \(a_{t,g}\in\{0,w_g\}\), choose masses \(x_{t,\mathbf b}\ge0\) over integral configurations \(\mathbf b\in\mathbb Z_{\ge0}^{G}\) satisfying \(\sum_{\mathbf b}x_{t,\mathbf b}=\mu_t\) and \(\sum_{t,\mathbf b}b_gx_{t,\mathbf b}=\sigma_g\). Minimize \(\lambda\), where \(v_t(\mathbf b)=\sum_hb_ha_{t,h}\), subject to \(x_{t,\mathbf b}>0\) and \(x_{u,\mathbf b'}>0\) implying \(v_t(\mathbf b'-\mathbf e_g)\le\lambda v_t(\mathbf b)\) for every \(g\) with \(b'_g>0\); decide whether \(\lambda\le\sqrt{2}\), equivalently whether a \(\frac{\sqrt{2}}{2}\)-EFX allocation exists.
A high-multiplicity restricted-additive fair-division model: \(\mu_t\) is the mass of complete type \(t\), \(x_{t,\mathbf b}\) is mass receiving integral bundle \(\mathbf b\), \(\sigma_g\) is per-capita supply, and the objective is the minimum support-wise EFX violation factor \(\lambda\).
The support-wise condition makes any positive mass of a bundle impose the full EFX constraint, so the mirror may be a discrete support-selection problem with mass variables rather than a smooth continuous relaxation; the proponent does not settle its computational tractability.
fatal: False
The mirror covers the restricted-additive \(\frac{\sqrt{2}}{2}\)-EFX guarantee in Theorem 6.1. It leaves the \((\infty,1)\)-bounded results, the \((2,\infty)\)-bounded restricted-additive result, the \(\eftx\) and charity guarantees, and the structural rank/virtual-value lemmas outside.
The strongest honest mirror is based on the paper’s restricted-additive result, not on its \((p,q)\)-bounded results. The latter contain relational restrictions on named agents and goods that do not survive aggregation cleanly. My lead anchor is therefore Theorem 6.1, proved in this paper.
The theorem says: for restricted additive valuations—each agent’s valuation is additive and every good \(g\) has value either \(0\) or a common intrinsic value \(v_g\)—the algorithm \(\algot\) returns a \(\frac{\sqrt{2}}{2}\)-EFX allocation. Concretely, for every pair of agents \(i,j\) and every good \(g\in X_j\), the output satisfies \(v_i(X_j\setminus\{g\})\le \sqrt{2}\,v_i(X_i)\), equivalently \(v_i(X_i)\ge \frac{\sqrt{2}}{2}v_i(X_j\setminus\{g\})\). The result is proved here, in Section 6, using two update rules, envy elimination, and a final allocation step. The paper does not give a polynomial-time complexity classification for this algorithm; the named result is an algorithmic fairness guarantee.
Here is the continuous-population problem I would put before the authors.
Call it Continuous Restricted-Additive EFX Optimization. The population has total mass \(1\), with finitely many complete agent types \(T\). Type \(t\) has mass \(\mu_t\), where \(\sum_t\mu_t=1\), and restricted-additive values \(a_{t,g}\in\{0,w_g\}\) for each good class \(g\). There are per-capita supplies \(\sigma_g\) of each good class. These supplies are the necessary high-multiplicity co-modification: after scaling by a population size \(N\), they become \(N\sigma_g\) individually indivisible copies. Every individual still receives an integral bundle; only the population proportions are continuous.
An allocation is a finite-support distribution \(x_{t,\mathbf b}\), where \(\mathbf b\in\mathbb Z_{\ge0}^{G}\) is an integral bundle and \(x_{t,\mathbf b}\) is the mass of type-\(t\) agents receiving it. It must satisfy \(\sum_{\mathbf b}x_{t,\mathbf b}=\mu_t\) and \(\sum_{t,\mathbf b}b_gx_{t,\mathbf b}=\sigma_g\) for every good class \(g\). The value of a bundle is \(v_t(\mathbf b)=\sum_g b_ga_{t,g}\).
The optimization variable is \(x\), together with the smallest violation factor \(\lambda\). We minimize \(\lambda\) subject to the following support-wise EFX condition: whenever \(x_{t,\mathbf b}>0\), \(x_{u,\mathbf b'}>0\), and \(b'_g>0\), require \(v_t(\mathbf b'-\mathbf e_g)\le \lambda v_t(\mathbf b)\). The decision version asks whether there is an allocation with \(\lambda\le\sqrt{2}\), or equivalently a \(\frac{\sqrt{2}}{2}\)-EFX allocation.
This is genuinely a population mirror. It does not replace indivisible bundles by fractional bundles, average valuations across agents, or turn fairness into an axiomatic property of a finite profile. A unit of population receives an integral bundle. The continuous object is the mass \(x_{t,\mathbf b}\) assigned to each integral bundle. The type \(t\) is complete: agents of the same type have the same values, eligibility, and all other parameters used by the problem.
A convincing regime is a large institution allocating repeated indivisible resources—training kits, equipment packages, licenses, or housing-related goods—to a very large cohort. There may be millions of recipients but only a small number \(\tau\) of eligibility and valuation profiles: for example, students in a few standardized programs or employees in a few contractual categories. The number of agents is large, the number of distinct types is small, and supplies are naturally specified per capita. The paper’s restricted-additive assumption is also recognizable in this setting: a resource has a common value to the agents who are eligible for it and zero value to the rest.
The high-multiplicity bridge is exact for rational data. Given rational \(\mu_t\) and \(\sigma_g\), choose a common denominator \(N\). Create \(N\mu_t\) agents of type \(t\) and \(N\sigma_g\) physical copies of each good class. A discrete allocation aggregates directly into an \(x\)-allocation. Conversely, any rational \(x\) can be expanded into a finite discrete allocation. Applying Theorem 6.1 to the expanded instance therefore proves existence of a feasible continuous allocation with \(\lambda\le\sqrt{2}\). That observation is a useful baseline, but it is not yet a continuous complexity result: the denominator \(N\) may be exponentially large, and the new question is whether the allocation can be computed from the compressed type-and-mass description.
I would initially send this problem toward Class A, via a configuration formulation or a separation algorithm over integral bundle configurations. The mass constraints themselves are linear, and the finite type description removes the irrelevant dependence on the number of named agents. The real technical obstacle is the support-sensitive EFX condition: it quantifies over bundles that receive positive mass, so it is not immediately an ordinary LP. If that obstacle produces hardness, it would be a genuinely continuum-specific Class C phenomenon, not hardness transferred from this paper. I would not claim hardness transfer, since the paper contains no named NP-hardness, coNP-hardness, or parameterized-hardness result.
The further questions are substantial: can the \(\sqrt{2}\) guarantee be obtained in time polynomial in \(m\), \(\tau\), and the input bit length; can the continuous optimum \(\lambda^\star\) be characterized exactly; and can a compressed continuous solution be rounded back to a discrete high-multiplicity allocation without losing the fairness ratio?
The weakest point is the supply scaling. The paper presents a finite set of individually named goods, whereas my mirror uses repeated good classes with per-capita supply. I think that change is forced by taking a population limit: keeping only finitely many unique goods makes their normalized supply vanish. Still, it is a real co-modification, and an author could object that repeated goods are a neighboring fair-division model. The rest of the mirror is faithful: the population is the continuous object, agents remain integral bundle recipients, restricted-additive valuations are preserved, and the paper’s exact \(\frac{\sqrt{2}}{2}\)-EFX guarantee becomes the target computational question.
The negative case is strongest at the level of the anchor itself: Theorem 6.1 is not a computational-complexity result in the programme’s sense. It proves that a finite restricted-additive instance admits a \(\frac{\sqrt{2}}{2}\)-EFX allocation and describes a terminating procedure, but gives no complexity classification, running-time theorem, optimization problem, or compressed-instance question. The proposed “Continuous Restricted-Additive EFX Optimization” therefore does not continuize a computational question from the paper; it invents a new optimization problem inspired by one fairness guarantee.
The faithful population limit is also degenerate. The paper has finitely many individually indivisible goods. If the population grows while those goods remain fixed, then at most \(m\) agents receive nonempty bundles, so the mass of recipients is at most \(m/N\), which tends to zero. Almost the entire limiting society receives the empty bundle, and the theorem’s fairness guarantee loses the competition that made it interesting.
The proponent’s repair—creating \(N\sigma_g\) copies of each good and specifying per-capita supplies—is sensible, but it is a substantial change of model. It replaces the paper’s finite collection of individually scarce goods by repeated commodity classes. That may be a good fair-division problem, but its connection to Theorem 6.1 is then only the restricted-additive valuation syntax. The paper proves nothing about this repeated-supply regime, and the institutional story is doing the work of justifying a new model rather than recovering the paper’s own one.
The proposed exact EFX condition exposes the same problem. It requires, for every pair of bundles with positive mass,
\[
x_{t,\mathbf b}>0,\ x_{u,\mathbf b'}>0
\quad\Longrightarrow\quad
v_t(\mathbf b'-\mathbf e_g)\leq \lambda v_t(\mathbf b).
\]
Thus an arbitrarily small positive mass of a bundle imposes exactly the same constraint as a mass close to \(1\). Retaining this condition gives a support-selection problem over integral configurations, decorated with mass variables; it is not a smooth or naturally convex continuous relaxation. The envy graph and lexicographic potential in the paper also do not pass through unchanged: agents of one type may receive several bundles, so the relevant vertices are type–bundle classes, and envy elimination can move arbitrarily small masses without the discrete progress measure used in the proof.
If instead one adopts an almost-everywhere or average version to obtain a genuinely measure-based problem, the exact high-multiplicity correspondence is lost. A bundle assigned to mass \(1/N\) may be ignored in the limit even though its owner is still a named agent and must be protected by EFX in every finite expansion. One cannot simultaneously retain the paper’s universal EFX notion and make the fairness constraint insensitive to vanishing masses.
This is not an identity objection: EFX depends only on valuations and bundles, so a repeated-good, finite-type model can indeed be aggregated and rational instances can be expanded back to finite ones. That is the proponent’s strongest point, and high-multiplicity fair division would support rather than undermine it.
Accordingly, the honest negative is limited. Theorem 6.1 supplies no named computational result to mirror, and its only nondegenerate continuous version requires a new repeated-supply configuration problem whose substantive difficulty is not inherited from the paper. But the universal claim that no worthwhile mirror exists is not defensible: if the programme accepts that co-modification, the proposed mirror is coherent.
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.