| paper | Parameterized Guarantees for Almost Envy-Free Allocations |
| authors | — |
| venue | AAMAS 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.8
Given a finite type set \(T\), rational masses \(\mu_t\), \(m\) indivisible good classes with rational per-agent supplies \(\rho_g\), additive values \(v_t(g)\), and \(\gamma=\min_g\frac{\min_{t:v_t(g)>0}v_t(g)}{\max_t v_t(g)}\), compute a finite-support mass distribution \(\pi_{t,B}\) over \(t\in T\) and \(B\in\mathbb{Z}_{\ge 0}^m\) satisfying \(\sum_B\pi_{t,B}=\mu_t\), \(\sum_{t,B}\pi_{t,B}B_g=\rho_g\), and \(v_t(B)\ge\alpha v_t(D-e_g)\) for every positive-mass pair \(\pi_{t,B},\pi_{u,D}\) and every \(g\) with \(D_g>0\) and \(v_t(g)>0\), at target \(\alpha=\frac{2\gamma}{\sqrt{5+4\gamma}-1}\).
A finite-type nonatomic agent population \(\mu\) competing for a per-capita supply \(\rho\) of repeated, individually indivisible good classes; the decision variables are integer-bundle mass couplings \(\pi_{t,B}\), and the objective is to compute or optimize the \(\mathrm{EFx}\) factor \(\alpha\).
The mirror jointly scales per-capita supply and leaves unrestricted integer-bundle support, so its computational class is not inherited automatically from Theorem 3.8; this bounds the claim but does not invalidate the question.
fatal: False
The mirror directly covers the named algorithmic guarantees of Theorems 3.8 and 4.2, including their \(\gamma\)-dependent \(\mathrm{EFx}\) and PMMS factors; it leaves the auxiliary structural results, exact fairness existence, and welfare or MMS questions untouched.
The strongest mirror is a large-market version of the paper’s fair-division problem in which both the population and the inventory scale, while each individual good remains indivisible. The lead anchor is Theorem 3.8.
Let \(T\) be a finite set of complete valuation types. Type \(t\) has additive valuation
\[ v_t(B)=\sum_{g=1}^m B_gv_t(g), \]
where \(B\in\mathbb{Z}_{\ge 0}^m\) is an integer bundle. Let \(\mu_t\) be the fraction of agents of type \(t\), and let \(\rho_g\) be the number of copies of good class \(g\) per agent in the large-market limit.
Thus, for an integer \(N\), the corresponding discrete instance has \(N\mu_t\) agents of type \(t\) and \(N\rho_g\) individually indivisible copies of good \(g\). Copies in the same class have identical valuations, but are still allocated one at a time. This is exactly a sequence of ordinary instances from the paper, not divisible-goods fair division.
A continuous allocation is a finite-support mass distribution \(\pi_{t,B}\): the mass of type-\(t\) agents receiving integer bundle \(B\). It must satisfy
\[ \sum_B\pi_{t,B}=\mu_t \]
and
\[ \sum_{t,B}\pi_{t,B}B_g=\rho_g \]
for every good \(g\). A rational \(\pi\) can be expanded exactly into a finite allocation by choosing a common denominator \(N\). Conversely, every finite allocation induces such an empirical distribution. This gives the required high-multiplicity bridge.
The range parameter is inherited directly:
\[ \gamma_g= \frac{\min_{t:v_t(g)>0}v_t(g)} {\max_t v_t(g)}, \qquad \gamma=\min_g\gamma_g. \]
The first continuous problem is Mass-EFx\(_\infty\). Given \((T,\mu,\rho,\{v_t\})\), find an allocation \(\pi\) maximizing \(\alpha\), subject to the following condition: whenever \(\pi_{t,B}>0\) and \(\pi_{u,D}>0\),
\[ v_t(B)\ge \alpha\,v_t(D-e_g) \]
for every \(g\) with \(D_g>0\) and \(v_t(g)>0\). Here \(e_g\) removes one indivisible copy of \(g\). Equivalently, the decision version asks whether an \(\alpha\)-EFx allocation exists and, if so, outputs \(\pi\).
The paper’s Theorem 3.8, proved by the authors in the supplied paper, states that Algorithm 1 computes an
\[ \frac{2\gamma}{\sqrt{5+4\gamma}-1} \]
-EFx allocation in polynomial time. My continuous analogue asks for exactly the same guarantee,
\[ \alpha= \frac{2\gamma}{\sqrt{5+4\gamma}-1}, \]
but with agents represented by masses of valuation types. This is my strongest anchor. The correspondence is especially credible because the paper’s proof uses only additive values, zero/nonzero incidence, base values, ordering of goods, and envy-cycle elimination. In the large-market setting, agents of the same valuation type can be batched, and envy-cycle operations become mass transfers among finitely many type–bundle states.
I provisionally expect the bounded-load version of Mass-EFx\(_\infty\) to be Class A: a type-level, batched version of LaBase should be expressible through a configuration or flow formulation, with the exponentially large population removed. The unrestricted version, where a vanishing mass may receive an unbounded bundle, is a genuine boundary question rather than something Theorem 3.8 settles automatically.
My second anchor is the paper’s Theorem 4.2, also an authors’ result rather than a cited theorem. It states that one can compute a
\[ \frac{5\gamma}{6} \]
-PMMS allocation in polynomial time. The detailed argument combines the authors’ Theorem 4.1 and Theorem 5.1; some proofs are deferred to the full version, but the result is claimed and established by this paper.
The corresponding problem is Mass-PMMS\(_\infty\). For an integer bundle \(S\), define
\[ M_t(S)= \max_{0\le X\le S} \min\{v_t(X),v_t(S-X)\}, \]
where the inequality is coordinatewise. Given two bundles \(B,D\), a type-\(t\) agent’s pairwise maximin share is \(M_t(B+D)\). The continuous problem asks for \(\pi\) maximizing \(\alpha\), subject to
\[ v_t(B)\ge \alpha M_t(B+D) \]
whenever \(\pi_{t,B}>0\) and \(\pi_{u,D}>0\), for distinct agents represented by those positive-mass states. The target mirroring Theorem 4.2 is \(\alpha=5\gamma/6\). As in the paper’s proof, one can additionally require every type to receive only goods it values positively.
This mirror is also plausible: PMMS is still evaluated on actual integer bundles and actual two-way partitions of those bundles. Nothing is replaced by expected utility or fractional ownership. The paper’s reduction to range parameter \(1\) is particularly compatible with the continuum: replacing every positive \(v_t(g)\) by the good’s base value is a transformation of type data and commutes with taking the distribution \(\mu\).
I would also provisionally expect the bounded-load Mass-PMMS problem to be Class A, though less confidently than Mass-EFx. For fixed bundle size, the maximin-share calculation ranges over finitely many bundle partitions, and the range-\(1\) envy-graph construction should admit batching by type and bundle state. With unrestricted bundle sizes, the partition structure may create a continuum-specific pricing or support-selection problem.
The natural regime is, for example, a large public-housing or course-allocation market: many households or students, relatively few complete valuation types, and many individually indivisible units or seats. A type records the entire valuation vector, including zeros and all relative values. Thus the objection that the mirror erases individual prices does not apply: idiosyncratic prices simply create additional types. The intended regime is \(\tau\ll N\), with \(N\) and the number of item copies growing together.
The weakest point is unavoidable. If the paper is interpreted as having a fixed finite inventory of \(m\) goods while only the number of agents tends to infinity, then no useful population continuum emerges: only \(m\) agents receive goods, and almost everyone is empty. My mirror therefore requires a genuine large-market regime with repeated or near-identical goods and per-capita inventory. That is a substantive modelling choice, but it is natural for housing units, course seats, food parcels, and similar applications. If that regime is accepted, the paper supplies two clear computational anchors for continuous population questions; if it is rejected, the objection is to the chosen instance regime, not to the mathematical continuity construction itself.
The strongest negative case is that neither theorem yields a nondegenerate mirror if only the population is continuized while the paper’s inventory of \(m\) indivisible goods remains fixed.
Take \(N\) agents and fixed \(m\). At most \(m\) agents can receive a nonempty bundle, so the fraction of nonempty agents is at most \(m/N\), which tends to zero. The limiting allocation therefore assigns the empty bundle to almost all mass. For EFx, comparisons against an empty bundle are vacuous. For PMMS, \(v_t(\emptyset)=M_t(\emptyset)=0\), so every multiplicative guarantee is vacuous. The finitely many recipients disappear as measure-zero exceptions. Keeping them as named exceptional agents merely leaves a finite discrete problem alongside a vacuous continuum.
This defeats both proposed anchors in the programme’s strict population-only scope. Theorem 3.8 cannot produce a meaningful Mass-EFx problem from a fixed inventory, and Theorem 4.2 has the same problem, with PMMS degenerating even more directly through pairwise unions of empty bundles.
The proponent’s repair is to scale the inventory as well: \(N\rho_g\) copies of each good class. That is a coherent model, but it is no longer merely a continuous population version of the paper. It is a joint large-market limit with two high-multiplicity objects: agent types and good classes. If the growing goods remain genuinely distinct, then a complete valuation type has a coordinate for every good, so the finite type space changes with \(N\). If one keeps a fixed type space, one has necessarily imposed repeated, valuation-indistinguishable copies and introduced the supply profile \(\rho\). The resulting problem is a new class-based allocation market, not the paper’s allocation problem with its population axis alone continuized.
The same issue appears in the proposed \(\pi_{t,B}\) formulation. The society distribution \(\mu\) does not determine fairness; the essential object is the coupling between types and integer bundle configurations. A finite-support \(\pi\) is perfectly legitimate, but it is then a compressed description of a sequence of discrete allocations, not a population-only continuum. Allowing genuinely nonatomic bundle distributions creates a further ambiguity: pairwise EFx and PMMS constraints must be interpreted almost everywhere or through essential support, since individual bundle states may have measure zero.
That is the best case against the anchors. It is, however, not enough to sustain the universal negative claim. The joint large-market model is not mathematically defective: many students with finitely many valuation types competing for repeated course seats, or many households receiving repeated housing units, are sensible high-multiplicity regimes. The goods remain individually indivisible, and EFx and PMMS remain integer-bundle notions. The programme explicitly treats high multiplicity as supporting evidence, so it would be wrong to dismiss this model merely because it is a high-multiplicity formulation.
Consequently, the honest verdict is that the negative case blocks a population-only mirror, but it does not defeat the proponent’s stronger large-market construction. Theorem 3.8 supplies a genuine continuous-population question in that regime, and Theorem 4.2 supplies a second plausible one. A universal “no worthwhile mirror in any scenario” verdict is not defensible.
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.