| paper | Improved Approximate EFX Guarantees for Multigraphs |
| authors | Alireza Kaviani, Alireza Keshavarz, Masoud Seddighin, A. Shahrezaei |
| venue | WINE 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5.9
statement extracted from the paper’s text layer
Given finite agent types \(T\) with masses \(\mu_t\ge0\) and \(\sum_t\mu_t=1\), finite good types \(E\) with per-capita supplies \(s_e\ge0\), additive values \(v_t(e)\ge0\), and \(|\{t:v_t(e)>0\}|\le2\) for every \(e\), output a complete mass allocation \(\lambda_{t,B}\ge0\) over integral multisets \(B\) satisfying \(\sum_B\lambda_{t,B}=\mu_t\) and \(\sum_{t,B}\lambda_{t,B}b_e(B)=s_e\), such that whenever \(\lambda_{t,B}>0\), \(\lambda_{u,C}>0\), and \(b_e(C)>0\), \(v_t(B)\ge \frac{1}{\sqrt{2}}v_t(C\setminus\{e\})\).
A finite type-level multigraph has vertex masses \(\mu_t\) and per-capita edge-copy supplies \(s_e\); variables \(\lambda_{t,B}\) assign population mass to integral bundle patterns, subject to supply equalities and support-wise \(1/\sqrt{2}\)-EFX constraints.
Replacing per-good relevance to at most two named agents by relevance to at most two types means a copied good can be valued by [?25l\Theta(N) individuals, so the exact individual multigraph promise and its algorithmic invariants are not preserved; the proponent argues this is the forced quotient but does not establish that the original authors would accept it.
fatal: False
The mirror covers Theorem 5.9 and its five-rule constructive allocation procedure; it leaves aside the cited two-agent theorem, background existence results, and any unproved runtime or complexity classification.
The strongest positive case is a high-multiplicity version of the paper’s complete approximate-EFX allocation problem. The paper contains no named theorem asserting membership in \(P\), NP-hardness, or another complexity class. Its best computationally relevant anchor is therefore its constructive guarantee.
The lead anchor is Theorem 5.9, proved in this paper. In the paper’s additive \((2,\infty)\)-bounded setting, Algorithm 1 returns a complete allocation \(\alloc^*\) that is \((1/\sqrt{2})\)-EFX. Concretely, every good is relevant to at most two agents; the algorithm starts from a basic feasible allocation, repeatedly applies its five update rules to the pool and the weighted envy graph, and finally allocates all remaining goods. The resulting allocation satisfies, for every pair \(i,j\) and every good \(g\in\alloc^*_j\), \(v_i(\alloc^*_i)\geq \frac{1}{\sqrt{2}}v_i(\alloc^*_j\setminus\{g\})\).
I would mirror this as follows.
Call the problem \(\textsc{Continuous-Approx-EFX}_{2,\infty}\). An instance has finitely many agent types \(T\), with population masses \(\mu_t\geq 0\) summing to \(1\). It also has finitely many good types \(E\), with per-capita supplies \(s_e\geq 0\). A good type \(e\) has additive value \(v_t(e)\) for agent type \(t\), and is relevant to at most two types: \(\lvert\{t:v_t(e)>0\}\rvert\leq 2\). There is no bound on how many good types can be relevant to the same pair, matching the paper’s multigraph interpretation of \((2,\infty)\)-boundedness.
A bundle is still an integral multiset of goods. The continuum does not make goods divisible. Let \(\lambda_{t,B}\) be the mass of type-\(t\) agents receiving integral bundle \(B\). A feasible allocation satisfies
\(\sum_B\lambda_{t,B}=\mu_t\) for every \(t\), and
\(\sum_{t,B}\lambda_{t,B}b_e(B)=s_e\) for every good type \(e\),
where \(b_e(B)\) is the number of copies of \(e\) in \(B\). Thus fractional quantities occur only as masses of agents receiving whole bundles: \(\lambda_{t,B}=0.37\) means that \(37\%\) of that type receives the integral bundle \(B\), not that each agent receives \(0.37\) of a good.
The question is to output a complete feasible \(\lambda\) such that, for every two bundles \(B,C\) receiving positive mass and every good copy \(e\) in \(C\),
\[ v_t(B)\ \geq\ \frac{1}{\sqrt{2}}\,v_t(C\setminus\{e\}) \]
for every type \(t\) whose agents receive \(B\). Equivalently, maximize the worst EFX factor over all such mass assignments and ask whether it is at least \(1/\sqrt{2}\). The objective is therefore the paper’s fairness guarantee, not Nash welfare; the paper’s NSW-maximizing initial allocation is only an internal algorithmic device.
A plausible regime is a very large allocation programme distributing standardized, indivisible packages to households. There are millions of agents but only a small number of complete valuation and eligibility profiles. Packages are produced in high multiplicity, and each package class is useful to at most two profiles—for example, a specialized item serving one household category or a pair of categories. The relevant comparison is \(N\gg |T|\), with \(N\) and the numbers of parallel package copies growing while the number of profiles remains fixed or moderate. Agent types include every attribute that affects values, so this is genuine high multiplicity rather than pretending idiosyncratic agents are identical.
The authors should recognize this as their problem. The mirror preserves additive valuations, integral bundles, complete allocation, the “remove any one good” definition of EFX, and the multigraph condition that each good has at most two relevant endpoints. It merely aggregates repeated vertices and parallel edges by mass. It also preserves the paper’s central objects: a type-level weighted envy graph, a pool of unallocated goods, heavy and light envy relations, and cycle-based updates. It is not cake cutting, fractional matching, or probabilistic allocation: each unit of population receives an ordinary indivisible bundle.
I would provisionally expect this fixed-guarantee problem to be Class A, although Theorem 5.9 does not prove that. The proof is built from local structural operations—removing zero-outdegree vertices, resolving two-cycles, rotating homogeneous cycles, and handling heterogeneous cycles—that appear naturally suited to a finite type-level graph with parallel edge masses. The obvious algorithmic target is a compressed version of the paper’s procedure, or a finite-support pattern formulation in which integral bundle patterns are generated only when needed. The exponential number of possible bundles is a real pricing/separation issue, but it is exactly the sort of issue the continuization programme is meant to expose.
The further questions are substantial: can the five rules be lifted to masses without losing the invariant that each remaining bundle has at most one relevant incoming type? Can a rational mass solution be rounded to a finite high-multiplicity allocation while preserving \(1/\sqrt{2}\)-EFX, perhaps with an additive \(O(1/N)\) loss? Is maximizing the EFX factor tractable even if finding a \(1/\sqrt{2}\)-solution is? And does a type-level analogue of Theorem 5.9 admit a column-generation or separation algorithm?
The weakest point is that the literal paper condition is per physical good and per individual agent. If one standardizes goods into types, one copy of a good type may be relevant to many cloned agents, even though it is relevant to only two valuation types. A strict referee could regard this as changing \((2,\infty)\)-boundedness. The honest defence is that this is the forced high-multiplicity co-modification: the paper itself identifies the instance with a multigraph, and the continuous object is the quotient multigraph with masses on vertices and parallel edges. If exact individual-level incidence is insisted upon, one can instead use a continuum of exchangeable finite multigraph copies, but that version is less ambitious and closer to a replicated finite problem.
Thus the positive claim is not that the paper already proves a continuous algorithm, nor that it contains a complexity-class result. It is that Theorem 5.9 supplies a precise, constructive fairness problem whose high-multiplicity analogue remains faithful to the paper’s mathematical question while making the population—not the goods or the fairness notion—the continuous object.
The proponent has only one real anchor: Theorem 5.9. But it is not a computational-complexity result. The theorem gives a constructive existence guarantee, while Algorithm 1 has no input encoding, runtime bound, compressed-output guarantee, or formally specified implementation of its key subroutines. In particular, it invokes another existence theorem, uses choice protocols, and processes named agents and goods one at a time. The proposed continuous questions about column generation, rounding, and pricing would therefore be new problems, not continuizations of a computational result proved in the paper.
More fundamentally, the paper’s \((2,\infty)\)-boundedness is incompatible with genuine high multiplicity under the programme’s definition of type. Let \(A\) be a type containing \(r\) agents. Since a type is a complete valuation description, whenever \(v_A(g)>0\), every one of those \(r\) agents regards \(g\) as relevant. The paper’s promise then gives \(r\leq 2\). Hence every nontrivial type has multiplicity at most two. With finitely many types, the number of nonzero-valued agents is bounded by \(2\tau\); there is no regime of millions of interchangeable agents over a fixed type space.
Keeping the paper’s individual-level incidence while scaling the population does not repair this. The agents must then have different sets of incident goods, so their complete valuation types proliferate with the population. The type distribution ceases to be a compressed description. If the goods are not scaled, the limit degenerates anyway: once there are at least as many agents as goods, assign each good to a different agent. Every bundle has size at most one, so after removing any good the remaining bundle is empty and the allocation is exact EFX. Almost all population mass receives nothing.
The proposed rescue—good types with per-capita supply, each relevant to at most two agent types—changes the central promise. A copy of such a good is relevant to every clone of those types, potentially to \(\Theta(N)\) individual agents, whereas the paper requires relevance to at most two named agents. This is not merely a harmless restatement of the multigraph: it replaces an individual multigraph by a type-level capacitated resource system. The variables \(\mu\), \(s_e\), and \(\lambda_{t,B}\) also forget which individual endpoints a good copy has. Restoring that information requires an additional incidence or matching measure between agents and goods; preserving it makes types proliferate, while erasing it produces a different problem.
One can impose EFX support-wise on the proposed bundle distribution, but then the central constraint is
\[ \lambda_{t,B}>0,\ \lambda_{u,C}>0 \;\Longrightarrow\; v_t(B)\geq \alpha\,v_t(C\setminus\{e\}) \]
for every relevant \(e\). This is a nonconvex configuration-support condition, not the paper’s finite-agent graph invariant or a straightforward continuous LP. Replacing it by average or type-level EFX would make the problem easier, but would no longer mirror Theorem 5.9.
The honest limitation is that a repeated-package fair-division problem with type-level relevance could be worthwhile in its own right, and the programme permits some co-modification when it is forced by scaling. I do not see a proof that such a new problem is uninteresting. But it is not a faithful continuous mirror of this paper’s \((2,\infty)\)-bounded model: the faithful version has no nontrivial high-multiplicity regime, while the nondegenerate version changes the incidence promise and introduces the actual research problem from scratch.
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.