| paper | EFX Allocations for Indivisible Chores: Matching-Based Approach |
| authors | Yusuke Kobayashi, Ryoga Mahara, Souta Sakamoto |
| venue | SAGT 2023 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Given finite cost types \(T\), rational population masses \(\mu\), chore categories \(E\), rational per-capita supplies \(\rho\) with \(\sum_{e\in E}\rho_e\le 2\), and additive costs \(c_t(e)\), find a finite-support rational assignment \(x_{t,b}\ge 0\), indexed by \(t\in T\) and \(b\in\mathbb{Z}_{\ge0}^{E}\), satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_e x_{t,b}=\rho_e\), such that whenever \(x_{t,b}>0\) and \(x_{u,d}>0\), every individual receiving \(b\) satisfies \(c_t(b\setminus\{e\})\le c_t(d)\) for every chore copy \(e\) in \(b\).
A high-multiplicity repeated-indivisible-chore model: types \(t\) carry mass \(\mu_t\), chore categories have per-capita integral-copy supplies \(\rho_e\), variables \(x_{t,b}\) assign mass to integral bundles, and EFX is enforced across all positive-support type-bundle pairs.
The compressed problem may lack a polynomial-size support or matching formulation because support-wise EFX yields incompatible bundle patterns; this bounds what the paper establishes but does not defeat the mirror.
fatal: False
The mirror covers Theorem 3.1 for \(m\le 2n\); it leaves Theorems 4.1 and 5.1, and the auxiliary matching results, without a separate mirror.
The strongest honest positive case is a single-anchor Class A mirror of Theorem 3.1.
The anchor is Theorem 3.1, proved in this paper: when there are \(n\) agents, \(m\) indivisible chores with \(m\le 2n\), and every agent has an additive cost function, an EFX allocation always exists and can be found in polynomial time. The proof gives a constructive algorithm based on the EFX-graph and bipartite perfect matching; its stated running time is \(O(mn^2)\).
I would mirror this as Mass-EFX\(_2\). Let \(T\) be a finite set of complete cost types. A type \(t\in T\) specifies additive costs \(c_t(e)\) for each chore category \(e\in E\). The population is a rational distribution \(\mu\), where \(\mu_t\) is the mass of agents of type \(t\). Chores remain indivisible for every individual, but supplies scale with population: \(\rho_e\) is the number of copies of chore category \(e\) per unit population, with
\[ \sum_{e\in E}\rho_e\le 2. \]
A solution is a finite-support assignment \(x_{t,b}\ge 0\), where \(b\) is an integral bundle of chore copies and \(x_{t,b}\) is the mass of type-\(t\) agents receiving \(b\). It must satisfy
\[ \sum_b x_{t,b}=\mu_t \]
for every \(t\), and
\[ \sum_{t,b} b_e x_{t,b}=\rho_e \]
for every chore category \(e\). Thus \(x\) may be fractional at the population level, but every agent represented by \(x_{t,b}\) receives an integral bundle \(b\).
The EFX requirement is imposed exactly on the underlying individuals. If \(x_{t,b}>0\), \(x_{u,d}>0\), and \(e\) is a copy in \(b\), then
\[ c_t(b\setminus\{e\})\le c_t(d). \]
Equivalently, every positive-mass type-bundle pair must not strongly envy any other positive-mass bundle. The computational question is: given \((T,\mu,E,c,\rho)\), find such an \(x\), or decide that none exists. Under the promise \(\sum_e\rho_e\le 2\), the conjectured answer is always yes.
This is a genuine population continuization rather than divisible-chores fair division. Consider a large housing cooperative, hospital, or workplace assigning repeated duty slots. There may be hundreds of thousands of agents but only a few dozen recurring cost profiles: agents with the same profile rank and evaluate every chore identically. The number of chore copies also scales with membership, so a rational \(\rho_e\) means that a large finite population has approximately that many copies per agent. The regime is \(N\gg |T|,|E|\), with repeated agent types and repeated chore categories.
The finite-to-continuous dictionary is exact on rational instances. Choose \(Q\) clearing the denominators of \(\mu\) and \(\rho\). Then there are \(Q\mu_t\) agents of type \(t\) and \(Q\rho_e\) chore copies of category \(e\). Applying Theorem 3.1 gives an ordinary finite EFX allocation; grouping agents by type and bundle produces \(x\). Conversely, a rational \(x\) can be scaled into a finite allocation. Hence the question is not merely “replace counts by percentages”: it is the high-multiplicity version of precisely the same EFX problem, with integral bundles preserved.
I expect Mass-EFX\(_2\) to be tractable, but this would be a new result, not something already proved by the paper. The EFX-graph and matching invariant suggest a population-level flow or configuration formulation in which masses replace named agents. The interesting computational question is whether that formulation can be solved in time polynomial in \(|T|\), \(|E|\), and the input bit length, without expanding the denominator \(Q\). If so, Theorem 3.1 would become a genuinely compressed continuous algorithmic theorem.
The mirror covers only Theorem 3.1. I would not use Theorems 4.1 or 5.1 as additional anchors: “one exceptional agent” and “exactly three agents” do not scale cleanly to a high-multiplicity population. They are useful follow-up directions—especially type-level identical ordering and personalized bi-valued populations—but forcing them into the main case would weaken it.
The weakest point is important: the paper’s polynomiality is measured in the explicit number \(n\) of agents. Clearing denominators can make \(Q\) exponentially large in the encoded continuous input, so Theorem 3.1 alone does not establish a polynomial-time algorithm for Mass-EFX\(_2\). Moreover, EFX depends on which bundles have positive mass, so the compressed problem may have a nontrivial support-selection or configuration-pricing obstacle. That is precisely the computational question the mirror contributes. It remains a plausible Class A continuation because the population ratio \(m/n\le 2\) translates exactly into per-capita chore supply, while indivisibility and the EFX predicate remain intact.
The strongest negative case is that the proposed mirror is not actually supplied by Theorem 3.1. The theorem is polynomial in the explicitly listed \(n\) agents and \(m\) chores; it says nothing about an algorithm polynomial in the number of cost types, chore categories, and the bit-length of rational masses.
If the chore set remains fixed while the population grows, the mirror is vacuous. Once \(n\ge m\), assign every chore to a different agent. Every nonempty bundle is a singleton, so removing its only chore leaves cost \(0\), and the allocation is EFX for arbitrary additive costs. In an atomless society, the finitely many recipients are even a null set. Thus a genuine limit requires scaling chore supply with population.
But scaling supply introduces a new repeated-resource problem. The proposed variables \(x_{t,b}\) preserve integral bundles, which is the right way to avoid accidentally replacing EFX by divisible-chore fairness. It also creates the central obstruction: EFX is support-wise. Whenever \(x_{t,b}>0\) and \(x_{u,d}>0\), the corresponding bundles must satisfy all pairwise EFX inequalities, however tiny either mass is. Consequently, the feasible set is a union of nonconvex support patterns, not a configuration LP. Combining two valid mass allocations can introduce a previously absent incompatible bundle pair. Replacing this by type-average EFX would restore linearity, but would no longer mirror the paper’s individual EFX predicate.
The paper’s matching proof does not resolve this compression issue. Its invariant uses \(Q\) explicitly named agent vertices after clearing denominators, repeatedly chooses individual agents and chores, and maintains a matching on those expanded objects. With rational input of encoding length \(L\), \(Q\) can be exponentially large. Hence the stated \(O(mn^{2})\) algorithm becomes only a pseudo-polynomial construction in the continuous encoding. The proponent’s promised flow or configuration algorithm is a conjectured new result, not a consequence of Theorem 3.1.
That is a respectable objection to the mirror’s strength: at best it is an open compressed-input repeated-chore allocation problem, and the paper gives no evidence that its matching structure survives type aggregation. The fixed-inventory version is trivial; the nontrivial version changes the resource ontology; and exact EFX prevents the obvious LP relaxation.
It does not, however, support the requested universal negative conclusion. The repaired model—with recurring indivisible chore categories, per-capita supplies \(\sum_e\rho_e\le2\), complete cost types, and support-wise EFX—is coherent and recognisable as a high-multiplicity version of the theorem. For rational data, clearing denominators gives an exact finite-instance dictionary in both directions. A large workplace or hospital with recurring duties and repeated cost profiles is a credible regime. The unresolved question of whether such allocations admit polynomial-size supports or a compressed matching algorithm is precisely a computational question about the continuous population.
So the honest negative verdict is qualified: the proponent overstates what the paper establishes, and the mirror may be a difficult new Class A/Class C problem rather than a direct continuization. But Theorem 3.1 survives as a worthwhile anchor; I cannot honestly defeat it in every plausible scenario.
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.