| paper | Almost Envy-freeness, Envy-rank, and Nash Social Welfare Matchings |
| authors | Alireza Farhadi, Mohammad Taghi Hajiaghayi, M. Latifian, Masoud Seddighin, Hadi Yami |
| venue | AAAI 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
Given finitely many valuation types \(T\), type masses \(\mu_t\), good categories \(G\), per-capita supplies \(\sigma_g\), and additive values \(v_t(g)\), compute a feasible bundle-mass plan \(\pi_{t,B}\) assigning integral bundles \(B\) to population mass while satisfying \(\sum_B\pi_{t,B}=\mu_t\) and \(\sum_{t,B}B_g\pi_{t,B}=\sigma_g\), maximizing or guaranteeing \(\alpha\) such that \(v_t(B)\ge\alpha R_t(B')\) whenever \(\pi_{t,B}>0\) and \(\pi_{u,B'}>0\), where \(R_t(B')\) is the expected value after uniformly deleting one good from \(B'\).
A high-multiplicity fair-division market with finitely many agent types, continuous masses \(\mu\), per-capita supplies \(\sigma\), integral bundles \(B\) for each individual, and bundle-mass variables \(\pi_{t,B}\); the objective is to maximize the worst support-wise \(\mathrm{EFR}\) factor \(\alpha\), with Nash-welfare matching represented by a transportation relaxation.
The mirror covers the polynomial-time \(0.73\)-\(\mathrm{EFR}\) result and its Nash-welfare matching and completion structure, but does not claim to continuize the separate \((\phi-1)\)-\(\mathrm{EFX}\) result or all auxiliary observations.
A credible positive mirror is a high-multiplicity market for replicated indivisible goods—not cake cutting and not fractionalizing an individual’s bundle.
The lead anchor is Theorem 1, the paper’s main theorem, proved here. Under the paper’s standing assumption of additive valuations, it says that every instance of fair allocation admits a \(0.73\)-approximate envy-free-up-to-a-random-good allocation, and that such an allocation can be computed in polynomial time. The proof actually obtains the factor \(\sqrt{3}-1\approx 0.73\). The paper has no comparable named hardness theorem, so this algorithmic anchor is the strongest available one.
The natural regime is a large recurring allocation market. Suppose a public agency serves \(N\) households, each receiving a bundle of indivisible service vouchers, training places, childcare slots, or similar goods. There are only \(\tau\) household types: agents of the same type have the same additive valuation vector, eligibility, and other parameters relevant to allocation. The number of households is enormous, while \(\tau\) is fixed or grows very slowly. Each voucher category has supply proportional to \(N\), so the goods, like the population, are replicated. This is precisely the setting in which “\(16.8\%\) of households of type \(t\)” is more meaningful than naming the households individually.
Formally, let \(T\) be the finite set of agent types, \(\mu_t\) the mass of type \(t\), and let \(G=\{1,\ldots,q\}\) be the catalogue of good types. Let \(\sigma_g\) be the supply of good \(g\) per unit population. A type \(t\) has additive valuation
\[ v_t(B)=\sum_{g=1}^q B_g v_t(g) \]
for an integral bundle \(B\in\mathbb Z_{\ge 0}^q\). A solution is a bundle-mass plan \(\pi_{t,B}\), where \(\pi_{t,B}\) is the mass of type-\(t\) agents receiving the integral bundle \(B\). It must satisfy
\[ \sum_B \pi_{t,B}=\mu_t \]
for every \(t\), and
\[ \sum_{t,B} B_g\pi_{t,B}=\sigma_g \]
for every good \(g\). Thus every individual receives an integral bundle; \(\pi\) only aggregates how many identical agents receive each bundle. The fractional object is population mass, not an indivisible item assigned fractionally to one person.
For a nonempty bundle \(B'\), define the value to type \(t\) after removing a uniformly random good by
\[ R_t(B') = \frac{1}{|B'|} \sum_{g=1}^q B'_g\,v_t(B'-e_g). \]
The continuous problem is:
Given \((T,\mu,G,\sigma,v)\), output a feasible bundle-mass plan \(\pi\) such that, whenever \(\pi_{t,B}>0\) and \(\pi_{u,B'}>0\),
\[ > v_t(B)\ge (\sqrt{3}-1)R_t(B'). > \]
Equivalently, maximize the largest \(\alpha\) for which the same inequalities hold with \(\alpha\) in place of \(\sqrt{3}-1\).
This is the exact population-continuous analogue of the paper’s \(\mathrm{EFR}\) question. The random deletion is unchanged, valuations remain additive, and the requirement is still pairwise: every agent of type \(t\) must be sufficiently satisfied with their own bundle relative to every bundle actually received by another type. Averaging bundles merely because the population is continuous would be a weakening and would not be the proposed mirror.
The high-multiplicity dictionary is direct. If \(\mu\) and \(\sigma\) are rational, multiply by a common denominator \(N\). The instance becomes a finite fair-division instance with \(N\mu_t\) agents of type \(t\) and \(N\sigma_g\) copies of each good category. Conversely, grouping identical valuation rows and identical good copies in such finite instances produces \((\mu,\sigma)\). The paper’s problem is therefore not being replaced by a different fairness notion; it is being expressed in the regime where population multiplicity is the dominant parameter.
I would expect this mirror to be Class A, although that is a research question rather than a claimed corollary of Theorem 1. The paper’s first step is a Nash Social Welfare matching. In the replicated market, its natural counterpart is the transportation problem
\[ \max_x \sum_{t,g}x_{t,g}\log v_t(g) \]
subject to
\[ \sum_g x_{t,g}=\mu_t, \qquad \sum_t x_{t,g}=\sigma_g, \qquad x_{t,g}\ge 0. \]
This is the high-multiplicity version of maximizing the product of agents’ utilities in the one-good-per-agent matching step. The rest of the proof suggests mass allocation, flow, and column-generation formulations for the refinement and completion stages. The continuous optimization toolbox is therefore addressing the same combinatorial structure, rather than simply exploiting divisible outcomes.
The mirror immediately raises useful questions. Does the \(\sqrt{3}-1\) guarantee survive when envy-rank classes become masses rather than named agents? Can the optimal continuous \(\mathrm{EFR}\) factor be computed by a transportation or column-generation algorithm? Can every continuous solution be discretized for an \(N\)-agent instance with only \(O(1/N)\) loss? And does exact support-wise \(\mathrm{EFR}\) remain tractable, or does it require a continuum-specific separation problem over integral bundle types?
The weakest point is that the paper’s proof uses an agent-level envy graph, topological order, and envy-rank. A type may be split across several first-round goods, so one type may no longer have one envy-rank or one outgoing choice. Moreover, exact \(\mathrm{EFR}\) depends on the worst bundle in another type’s support, not merely its average bundle. Aggregating the proof is therefore nontrivial and could conceivably produce Class C hardness.
That weakness does not undermine the mirror itself. The question remains faithful to the paper: many agents share complete valuation types, goods are still indivisible at the individual level, the fairness criterion is unchanged, and the main algorithmic object—the Nash-welfare matching followed by fair completion—has a natural mass-transport counterpart. The proposed mirror covers Theorem 1 and deliberately does not claim to continuize the paper’s separate \(\mathrm{EFX}\) discussion.
The strongest negative case is that the paper’s theorem does not have a stable literal population limit. With a fixed set of \(m\) goods and \(N\to\infty\), almost every agent receives nothing, while the paper’s \(\mathrm{EFR}\) condition is defined through the integral contents of another agent’s bundle. The limit either becomes degenerate or requires special conventions for empty bundles. Thus the direct limit of Theorem 1 is not a meaningful continuous society.
The proponent’s repair, however, is the obvious better mirror: scale the goods with \(N\), group identical valuation vectors into types, and retain integral bundles for each individual while aggregating only population mass. That repair is fully legitimate under ChoCo’s scope. A rational bundle-mass plan \(\pi_{t,B}\) is exactly a compressed finite instance after multiplying by a common denominator, and the support-wise condition
\[
v_t(B)\ge (\sqrt{3}-1)R_t(B')
\]
faithfully represents every type-\(t\) agent’s comparison with every bundle receiving positive mass. The random deletion remains nondegenerate because each individual still receives an integral bundle.
The more serious objection is that the paper’s proof does not continuize cleanly. Its essential objects are an agent-level Nash-welfare matching, one envy-rank per agent, a topological order, and sequential best-item choices. In the mass model, one type can be split among many first-round goods and many final bundles, so it has no single envy-rank or position in an envy graph. The proposed transportation program captures only the first matching step; it does not establish a continuous analogue of the \(\sqrt{3}-1\) theorem. The exact \(\mathrm{EFR}\) constraints are support-sensitive and potentially require optimizing over exponentially many integral bundle types, rather than solving the paper’s polynomial matching problem.
That is a real weakness in the proposed case, but it is not a decisive objection to the mirror. It identifies precisely the computational question: whether the envy-rank machinery has a mass-transport or column-generation replacement, whether support-wise \(\mathrm{EFR}\) admits efficient separation, and whether the finite guarantee survives discretization. A positive answer would give a Class A result; a negative answer could give a continuum-specific hardness result. Both are worthwhile outcomes.
I therefore cannot honestly defeat this anchor. Theorem 1 supplies a named computational result, the high-multiplicity scenario is sensible, the indivisibility is preserved at individual level, and no existing continuous treatment already answers the computational question. The negative case can show that the proposed mirror is technically unproved and substantially different from a routine translation, but it cannot support the universal claim that no worthwhile continuous 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.