we-solve (beta)

Econ-298 · economics · Economics

EFX existence for chores with binary submodular costs

LLM status Open unverified

Statement

ID: GT-064. Category: Fair division of chores.  Kind: P. Status: Open in the cited source.

Definitions and mathematical statement

Let $N=\{1,\ldots,n\}$, $n\geq 1$, and let $C$ be a finite set of chores. For each $i$, let $c_i:2^C\to\mathbb Z_{\geq 0}$ satisfy $c_i(\varnothing)=0$, monotonicity, submodularity, and binary marginal costs: \[ \begin{gathered} S\subseteq T\ \Longrightarrow\ c_i(S)\leq c_i(T),\\ c_i(S)+c_i(T)\geq c_i(S\cup T)+c_i(S\cap T) \qquad(S,T\subseteq C),\\ c_i(S\cup\{g\})-c_i(S)\in\{0,1\} \qquad(S\subseteq C,\ g\in C\setminus S). \end{gathered} \] A complete allocation $A=(A_1,\ldots,A_n)$ is an ordered partition of $C$. It is EFX if \[ c_i(A_i\setminus\{g\})\leq c_i(A_j) \qquad(i,j\in N,\ g\in A_i). \]
Question.
Does every instance satisfying these hypotheses admit a complete EFX allocation?

Short English statement

Must binary submodular chore costs always permit an EFX allocation?

Variants and scope boundaries

The removed chore belongs to the potentially envious agent's own bundle. Every chore is tested, including a chore of zero marginal cost. Binary marginals do not mean that the value of an entire bundle is binary. Negative results for other monotone cost classes do not answer the submodular question.

Source relationship and status

[S1, Section 4] explicitly singles out binary submodular costs as an unresolved class.

References

[S1] Zehan Lin, Shengxin Liu, Biaoshuai Tao, and Shengwei Zhou, Non-Existence of EFX Chore Allocations for Monotone Cost Functions with Binary Marginals, 2026, arXiv:2608.10572v1. https://arxiv.org/html/2608.10572v1. Locators: Section 2 (cost and EFX definitions); Section 4, Conclusion and Open Problem.

Common conventions: Source mathematical conventions

Finite games. For a finite set $A$, $\Delta(A)$ is its probability simplex. Players choose independent mixed strategies in Nash equilibrium; correlation is allowed only when explicitly part of the solution concept. In a game with payoff functions $u_i$ and strategy profile $x$, an additive $\varepsilon$ Nash equilibrium satisfies \[ u_i(x)\geq u_i(x_i',x_{-i})-\varepsilon \quad\text{for every player $i$ and every admissible deviation $x_i'$}. \] For numerical approximation, payoffs are normalized as locally specified. An $\varepsilon$ payoff residual is distinct from distance at most $\varepsilon$ to the set of exact equilibria. Point convergence, convergence of empirical play, and convergence in distance to an equilibrium set are also distinct.

Computational representations. Unless stated otherwise, a complexity question takes rational data with binary encoding; polynomial time is measured in total bit length. A fixed-accuracy polynomial algorithm is not necessarily polynomial in $1/\varepsilon$, and neither is necessarily polynomial in $\log(1/\varepsilon)$. Succinct games and value, demand, or sampling oracles must declare their interfaces. Exact real solutions require an explicit representation; an unspecified list of arbitrary real numbers is not a finite computational output. A claimed algorithmic barrier is meaningful only for its specified model and reductions.

Dynamic games. Histories, information, observation, and allowable randomization are part of the model. A stationary strategy depends only on the current state; a positional strategy in a deterministic graph game chooses one action at each controlled vertex. Nash equilibrium at an initial state and equilibrium after every history are different requirements. An expectation of a pathwise $\liminf$ payoff, a $\liminf$ of expected averages, a limiting expected average, and a uniform finite-horizon equilibrium are different criteria. None is silently substituted for another.

Allocation and mechanisms. A complete allocation assigns every item exactly once unless otherwise stated. Zero-valued goods, negative values, capacity constraints, feasibility, lotteries, and copies of goods affect fairness definitions and are specified locally. Dominant-strategy incentive compatibility, Bayesian incentive compatibility, universal truthfulness, and truthfulness in expectation impose different inequalities. Whenever an objective ratio has zero denominator, its convention is stated or those instances are excluded.

Infinite-dimensional models. Expectations, integrals, stochastic equations, and optimization objectives require their local regularity, integrability, filtrations, and admissible domains. A backward--forward mean-field system is a boundary-value problem; it is not an initial-value semiflow without an additional construction. Long-time, large-population, and vanishing-noise limits require an order of limits and a convergence topology. If a minimum need not be attained, the objective is its infimum or supremum and the approximation requirement is stated separately.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-298-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-298

Binary submodular chores: two-agent construction and matroid subclasses

Status: Unresolved. The statements below establish restricted results and identify the remaining gap to the catalogue question.

Question and achieved scope

For normalized monotone submodular integer costs with marginal increments in $\{0,1\}$, must every finite chore instance admit a complete EFX allocation? Here EFX tests removal of every chore from the envious agent's own bundle, including zero-marginal chores. We prove a constructive two-agent result, even without submodularity, and two all-agent subclasses. The arbitrary-agent, arbitrary-matroid-rank question remains unresolved. These restricted statements are not asserted to be new in the fair-division literature.

Why matroid rank is the relevant representation

Write $c$ for one agent's normalized binary submodular cost, and let $m$ be the number of chores.
Lemma (Rank representation): The family $\mathcal I=\{S:c(S)=|S|\}$ is the independent-set family of a matroid, and $c(S)$ is its rank for every $S$.
Proof: Binary increments give $c(S)\leq|S|$. If $I\in\mathcal I$ and $J\subseteq I$, then $c(I)\leq c(J)+|I\setminus J|$, forcing $c(J)=|J|$; hence the family is hereditary. If $I,J\in\mathcal I$ and $|I|<|J|$, suppose no $g\in J\setminus I$ raises the rank of $I$. Submodularity makes all those zero increments remain zero as elements are added. Thus $c(I\cup J)=c(I)=|I|<|J|=c(J)$, contrary to monotonicity. This proves augmentation.

To find an independent subset of a given $S$, scan its elements and retain an element exactly when it increases the cost of the retained set. Each retention adds one to both size and cost. A rejected element has zero marginal cost at rejection and still has zero marginal cost at the final retained set by submodularity. Adding all rejected elements therefore changes nothing. The retained independent subset has size $c(S)$, while monotonicity shows no independent subset of $S$ can be larger. This proves the rank assertion. ∎

A zero marginal upon removal need not mean a chore is a loop: it can be redundant inside a dependent bundle. Treating rank costs as additive binary item costs would lose this distinction.

Two agents: an explicit cut-and-choose construction

First consider two bundles evaluated by a single normalized monotone integer cost $c$ with binary increments; submodularity is not needed. For a partition $(B_1,B_2)$ put $r=\max_j c(B_j)$ and $s=\min_j c(B_j)$. If $r>s$, let $h$ be the number of chores in the unique higher-cost bundle; if $r=s$, set $h=0$. Order the integer triples $(r,-s,h)$ lexicographically.
Lemma (A decreasing finite potential): If the two-bundle partition is not EFX for $c$, there is a move of one chore from the higher-cost bundle to the lower-cost bundle that strictly decreases $(r,-s,h)$. Repeated such moves stop at an EFX partition after at most $(m+1)^3$ moves.
Proof: The lower-cost bundle cannot violate EFX, by monotonicity. Thus $r>s$ and some chore $g$ in the higher bundle $H$ has $c(H\setminus\{g\})>s$. Move it to the other bundle $L$. Binary increments imply $c(H\setminus\{g\})\in\{r-1,r\}$ and $c(L\cup\{g\})\in\{s,s+1\}$. If the former is $r-1$, the violation inequality gives $s\leq r-2$, so both new costs are at most $r-1$ and the first potential coordinate decreases. Otherwise the higher cost stays $r$. If the lower cost rises, either the costs become equal or the second coordinate strictly decreases. If the lower cost does not rise, both costs stay unchanged and the unique higher bundle loses one chore, decreasing the third coordinate. Every case is a strict lexicographic improvement. There are at most $(m+1)^3$ possible triples, so the procedure terminates. At termination there is no violating chore, which is exactly EFX for both bundles under $c$. ∎
Theorem (Complete EFX for two binary-marginal agents): For any two normalized monotone integer cost functions with binary increments, a complete EFX allocation exists and can be found with $O(m^4)$ value-oracle calls.
Proof: Agent 1 constructs a partition EFX under its own cost using the lemma. Agent 2 chooses the bundle of smaller cost according to its own function; agent 1 receives the other. Agent 1 satisfies EFX for either possible assignment because both sides of its partition satisfied the removal inequalities. Agent 2 is envy-free, and removing any own chore cannot increase its cost, so it is EFX as well. Completeness is preserved by every move. Checking all candidate removals takes $O(m)$ oracle calls per step, and the lemma bounds the number of steps by $O(m^3)$. Choosing the cheaper bundle requires two further calls. ∎

Two subclasses for arbitrary numbers of agents

Proposition (Agent-specific uniform ranks): Suppose $c_i(S)=\min\{k_i,|S|\}$ for integers $k_i\geq0$. Any complete allocation whose bundle cardinalities differ by at most one is EFX, for any number of agents.
Proof: For every nonempty own bundle and every $g\in A_i$, balanced cardinalities give $|A_i|-1\leq|A_j|$. Applying the increasing map $t\mapsto\min\{k_i,t\}$ gives $c_i(A_i\setminus\{g\})\leq c_i(A_j)$. Empty bundles impose no removal condition. Such balanced partitions exist by distributing chores cyclically. ∎
Proposition (Divisible common partition classes): Let $C_1,\ldots,C_d$ partition the chores, with each $|C_\ell|$ divisible by the number $n$ of agents. Suppose \[ c_i(S)=\sum_{\ell=1}^d\min\{k_{i\ell},|S\cap C_\ell|\} \] for arbitrary nonnegative integer capacities. Giving each agent exactly $|C_\ell|/n$ chores of every class is envy-free and hence EFX.
Proof: Each agent evaluates every bundle by the same vector of class counts, so all bundles have the same cost under its own function. Monotonicity preserves the weak inequality after any removal. Divisibility makes the proposed complete allocation feasible. ∎

Completion Estimate

40%

This is a post hoc, heuristic estimate for the full catalogue target. The attempt proves complete EFX existence constructively for two binary-marginal agents and for uniform-rank and divisible partition-rank subclasses with arbitrary agent counts. The central existence question for arbitrary numbers of agents with unrelated matroid-rank costs remains unresolved, including redundant chores with zero removal marginals.

Remaining obstruction and reference

The two-agent proof uses one common evaluation for the cutting step; a third agent cannot generally be accommodated by the same choice argument. The uniform-rank proof uses cardinality alone, whereas general matroid rank depends on which chores are together. The divisible-class proof does not handle arbitrary remainders or unrelated matroids. None of these arguments licenses dropping zero-marginal removals from the EFX definition.

Zehan Lin, Shengxin Liu, Biaoshuai Tao and Shengwei Zhou (2026), Non-Existence of EFX Chore Allocations for Monotone Cost Functions with Binary Marginals, arXiv:2608.10572v1, Sections 2 and 4. https://arxiv.org/html/2608.10572v1. The paper distinguishes its negative results from the remaining binary-submodular question. The proofs above address precisely the subclasses stated, with no inference from negative examples in other cost classes.

Go to contribution →