| paper | Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously |
| authors | Hannaneh Akrami, Nidhi Rathi |
| venue | AAAI 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 4.4
statement extracted from the paper’s text layer
Given finitely many complete additive valuation types with rational masses \(\mu\), rational per-capita supplies \(b\) of indivisible good kinds, and fixed \(\epsilon, \delta > 0\), compute a mass assignment \(\lambda_{t,B}\) over integral whole-bundle configurations \(B\), respecting type masses and item capacities, such that every occupied bundle gives type \(t\) at least \((2/3 - \epsilon)\) times its asymptotic MMS density and every occupied pair satisfies \((1 - \delta)\)-EFX; determine the complexity and finite-replica rounding behavior.
A high-multiplicity course or entitlement market: types encode complete additive valuations and eligibility parameters, μ is population mass, b is per-capita indivisible-seat supply, λ assigns mass to whole bundles, and feasibility enforces ex-post approximate EFX and MMS-density guarantees.
The proposed mass-flow and configuration-LP tractability is unproved because ex-post EFX support constraints are nonconvex and aggregated envy-cycle repairs require new structural machinery.
fatal: False
The mirror covers Theorems 4.4 and 5.3, concerning approximate simultaneous EFX/EF1 and MMS guarantees; it leaves exact guarantees, the charity theorem, and auxiliary structural lemmas unaddressed.
The strongest positive case is a high-multiplicity course-allocation or entitlement-allocation regime. There are millions of agents but only a small number \(\tau\) of complete valuation types. For example, students may share one of 20–100 additive preference profiles over a catalogue of courses, while each course has many indivisible seats. The relevant type contains the entire valuation vector and any eligibility or budget parameters; agents with different prices or constraints are different types.
The goods remain indivisible. Formally, let \(T\) be the finite type set, \(\mu_t\) the mass of type \(t\), and \(G\) a finite catalogue of good kinds. Let \(b_g\) be the rational number of copies of good \(g\) per unit population. For a replication factor \(K\), this means \(K\mu_t\) agents of type \(t\) and \(Kb_g\) indivisible copies of \(g\). Thus a fractional-looking aggregate allocation is only a compact description of whole-bundle allocations in large finite markets; it is not fractional ownership or a lottery.
For \(B\subseteq G\), write \(v_t(B)=\sum_{g\in B}v_t(g)\). Define the type-\(t\) maximin-share density by
\[ \operatorname{MMS}_t(b)= \max_y\ \min_{B:y_B>0}v_t(B), \]
where \(y_B\geq 0\), \(\sum_B y_B=1\), and \(\sum_{B:g\in B}y_B=b_g\). This is exactly the large-\(K\) limit of partitioning the indivisible copies into \(K\) bundles for a type-\(t\) agent.
The aggregate decision variable is \(\lambda_{t,B}\): the mass of type \(t\) receiving the whole bundle \(B\). It satisfies
\[ \sum_B\lambda_{t,B}=\mu_t,\qquad \sum_{t,B:g\in B}\lambda_{t,B}\leq b_g \]
for a partial allocation, with equality for a complete allocation. Fairness is imposed ex post on every occupied bundle, not merely in expectation.
My lead anchor is Theorem 4.4, proved in this paper: for every constant \(\delta,\varepsilon>0\), a partial allocation that is simultaneously \((1-\delta)\)-EFX and \((2/3-\varepsilon)\)-MMS can be computed in polynomial time.
The corresponding continuous problem is:
*Continuous Partial EFX–MMS.* Given \((T,\mu,v,b)\) and fixed \(\delta,\varepsilon>0\), find a finite-support \(\lambda\) satisfying the mass and item-capacity constraints, such that every occupied pair \((t,B)\) satisfies
\[ v_t(B)\geq (2/3-\varepsilon)\operatorname{MMS}_t(b), \]
and for every two occupied pairs \((t,B)\), \((u,D)\), and every \(g\in D\),
\[ v_t(B)\geq (1-\delta)v_t(D\setminus\{g\}). \]
The objective is feasibility, exactly as in the paper; equivalently, one can maximize the common MMS factor subject to the EFX constraints.
I expect this relaxed problem to be Class A in the natural bulk regime. The paper’s threshold graph becomes a type-to-bundle flow problem: instead of matching millions of named agents, one transports mass between finitely many valuation types and bundle configurations. The paper’s “most envious agent” repairs become transfers of mass between configurations. Only \(\tau\) distinct MMS thresholds need be computed. With a bounded good catalogue this is an ordinary finite configuration LP; with a variable catalogue, the natural research question is whether additive-value pricing gives an efficient separation oracle. The constants \(\varepsilon\) and \(\delta\) are important: they should permit approximate MMS computation and polynomially many repair levels, just as they do in Theorem 4.4.
My second anchor is Theorem 5.3, also proved here. It states that a complete allocation which is EF1 and \((2/3-\varepsilon)\)-MMS is computable in pseudo-polynomial time, and that replacing EF1 by \((1-\delta)\)-EF1 yields a polynomial-time algorithm.
The matching continuous problem is:
*Continuous Complete EF1–MMS.* Given the same input, find \(\lambda\) with exact item-capacity equalities, so every occupied \((t,B)\) satisfies the \((2/3-\varepsilon)\)-MMS condition and every two occupied \((t,B)\), \((u,D)\) satisfy
\[ v_t(B)\geq (1-\delta)v_t(D) \]
or, for some \(g\in D\),
\[ v_t(B)\geq (1-\delta)v_t(D\setminus\{g\}). \]
The expected classification is again Class A for fixed slack, with an exact-EF1 version likely retaining a pseudo-polynomial or knapsack-like boundary. The paper’s cited Lemma 5.1 supplies the relevant intuition: envy-cycle elimination can be aggregated into mass transfers among occupied type–bundle classes, while monotonicity preserves every type’s MMS guarantee.
These are recognisably the authors’ problems. The definitions of additive valuation, MMS, EFX, EF1, partial versus complete allocation, and the approximation factors are unchanged. The paper’s own algorithms already rely on threshold graphs, envy graphs, bundle modification, and envy-cycle elimination—all operations that have direct mass-flow analogues. Existing work on identical or restricted valuation profiles is supporting evidence that the repeated-type regime is legitimate, not a novelty collision.
The main further questions are whether the EFX-compatible configuration system has polynomial separation for variable numbers of good kinds; whether the continuous MMS density admits a uniform bit-polynomial approximation; how precisely finite allocations round from \(\lambda\); and whether exact EFX or exact EF1 introduces continuum-specific hardness.
The weakest point is unavoidable: if the goods remain a fixed finite set while the population grows, MMS collapses and the mirror becomes degenerate. The positive case therefore needs a bulk market in which indivisible goods also occur in many copies, as in nationwide course allocation or mass entitlement distribution. I would not claim this mirrors one-off inheritance or divorce instances. But it is a coherent high-multiplicity regime of the paper’s own additive indivisible-goods model, and it gives a concrete computational mirror for two of the paper’s strongest named results without changing the fairness concepts into divisible-resource or expected-utility notions.
The strongest negative case is against the proposed *literal* limit, not against the programme as a whole.
If the paper’s item set remains fixed while the number of agents tends to infinity, the mirror degenerates. Only finitely many agents can receive nonempty bundles, while almost everyone receives the empty bundle; with bounded additive values, the \(n\)-agent MMS tends to zero. The MMS guarantees therefore become vacuous, and EFX/EF1 are governed only by finitely many exceptional recipients. Theorem 4.4 and Theorem 5.3 then have no meaningful population-continuum analogue.
The proponent’s rescue—introducing per-capita supplies \(b_g\) and infinitely many copies of each good—is mathematically coherent, but it is no longer merely continuizing the population. It simultaneously changes the resource model and replaces the paper’s \(n\)-agent MMS benchmark by a new per-capita packing density. That may be a worthwhile market model, but it is a new problem rather than an automatic mirror of the stated theorems. If distinct goods are retained instead, the item universe and valuation description grow with the population, so the finite-type continuum disappears.
Nor does the proposed mass-flow intuition survive unchanged. EFX and EF1 are support conditions: whenever \(\lambda_{t,B}>0\) and \(\lambda_{u,D}>0\), constraints must hold between those particular bundles. They are not average constraints and are not preserved by convex combinations. Replacing them by expected or type-average fairness would change the paper’s notions; preserving them leaves a discrete configuration-support problem with real masses attached. Envy-cycle elimination likewise has no direct flow analogue without rebuilding the problem.
The same objection applies to both anchors. For Theorem 4.4, fixed goods make MMS trivial, while scaled goods produce a new replicated-course-market problem. For Theorem 5.3, complete allocation is impossible in the fixed-good continuum, and making the supply scale again yields that new market model; if goods themselves become divisible, deleting one good becomes measure-zero and EF1 collapses toward ordinary envy-freeness.
But this does not honestly defeat the best positive case. Course allocation with repeated valuation types, per-capita seats, whole indivisible course bundles, and ex-post EFX/EF1 is a sensible high-multiplicity regime, and its MMS-density benchmark is a legitimate limit of finite replicated instances. The paper even names course assignment as an application. Thus the negative case can reject the proponent’s claim that the formulation is automatically a simple configuration LP, but it cannot establish the requested universal conclusion. Both named anchors survive in a plausible scenario; the honest negative verdict is weak.
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.