we-solve (beta)

Econ-40 · economics · Economics

EFX existence for three agents with additive chores

LLM status Open unverified

Statement

ECON-002 | P | Explicit published open question, at source date

Definitions and formal target

There are exactly three agents and a finite chore set $M$. Costs are additive: $c_i(S)=\sum_{g\in S}c_{ig}$, with $c_{ig}>0$. For a complete partition $A$, agent $i$ prefers a lower cost. Chore-EFX removes an item from the envious agent's own bundle.

\[ \forall i,j\in\{1,2,3\}\;\forall g\in A_i, \qquad c_i(A_i\setminus\{g\})\leq c_i(A_j). \] Does every strictly positive additive three-agent instance admit such a complete allocation?

Clarifications and required assumptions

The quantifiers are $\forall m\in\mathbb N_0\;\forall c\in\mathbb R_{>0}^{3\times m}\;\exists A$ satisfying the displayed inequalities. Empty own bundles satisfy them vacuously and have cost zero. The item is removed from $A_i$, because $i$ dislikes chores; removing it from $A_j$ would define another property. Costs are comparable only within one agent's comparisons, so each cost row may be multiplied by a positive constant.

Variants and changes of scope

Nonnegative costs. Permit $c_{ig}=0$ and specify whether all own chores, or only strictly costly ones, are tested; these are distinct pointwise definitions. Approximate chores-EFX. Fix $\beta\geq1$ and require $c_i(A_i\setminus\{g\})\leq\beta c_i(A_j)$. Restricted domain. A personalized two-value restriction means $c_{ig}\in\{a_i,b_i\}$ for fixed $0<a_i<b_i$, not arbitrary positive costs. Efficiency. Adding PO requires exclusion of a partition decreasing all costs weakly and one strictly. A result for more agents with restricted costs must not be substituted for this three-agent unrestricted-cost question.

Audit conclusion and source relationship

[S1], Section 6, explicitly asks the three-agent additive question. Its general nonexistence result for four or more agents does not settle this entry. Strict positivity is the stated main domain; zero-cost conventions and additional efficiency requirements are separately specified variants.

References and exact source roles

[S1] Wentao He and Biaoshuai Tao (2026). EFX for Additive Chores: Nonexistence, Pareto Incompatibility, and Bi-Valued Existence. arXiv:2606.08872v2, 9 July 2026; original submission 7 June 2026. Author preprint.

Verified locator / source role: Section 6 (open questions); Section 2 (definitions). This version is newer than the draft's v1 citation.

https://arxiv.org/html/2606.08872v2

Common conventions: Additional-source status and mathematical conventions

Of the 100 supplied ECON entries, 65 distinct problems appear here; 32 close matches refine earlier entries, and three duplicate questions map to existing entries. Appendix app:audited-crosswalk lists every destination. The attachment's P/R/S/U distinctions and source audits are retained. Its precise mathematical formalizations are editorial unless the individual audit says otherwise. Candidate subsidy targets ECON-004--006 retain their U flags; the resolved approval-core question ECON-007 updates OP-0202 above. The following supplied conventions govern both this part and the attributed ECON refinements elsewhere in the catalogue, subject to local restrictions.

Parameterized questions. A problem family lists inputs that must be fixed before an instance is evaluated: population, horizon, policies, information, data law, model class and welfare weights. These are required choices, not quantities the citations are assumed to specify. Undefined applications should not be treated as identified estimands.

Indices and integrability. Sets of agents, firms and regions are finite unless a population measure is explicitly used. $i,j$ index units, $r$ regions, $t$ dates and $h$ horizons. $\mathbb E$ and $\Pr$ refer to the declared population and law; $\mathbf1\{A\}$ is an indicator. Every displayed expectation and discounted sum needs existence in the stated domain. Infinite horizons use a discount in $(0,1)$ and a convergence condition; finite horizons may use discount one.

Optimization and existence. A displayed $\max$, $\min$, or $\arg\max$ is conditional on attainment. For finite feasible menus this is immediate; general spaces need continuity and compactness/coercivity or another existence argument. Without attainment, the target is the supremum/infimum and arbitrarily near-optimal feasible choices. $\inf\varnothing=+\infty$. Empty feasibility and an unidentified target are different issues.

Potential outcomes. $Y_i(z)$ is the outcome under a specified intervention, not the observed conditional mean among people choosing $z$. In binary comparisons $\Delta Y_i=Y_i(1)-Y_i(0)$. Specify assignment, treatment versions, compliance, information and observation horizon. Interference is allowed under a full policy vector; compressed exposure notation needs a justified mapping. No interference, consistency and overlap are substantive assumptions, not automatic consequences of notation.

Populations and observation. Fix baseline eligibility and population weights. Conditioning on post-policy employment, survival, relocation or program uptake can change the population being compared. Death is not ordinary loss to follow-up; outcomes truncated by death need a composite convention, joint survival target, or explicitly defined survivor stratum. Fertility-changing interventions need a population functional rather than an unexplained fixed descendant cohort. Measurement and missingness models must be supplied.

Identification. A structural model $m\in\mathcal M$ implies observable law $P_m$ and target $\theta(m)$. Identification means \[ P_{m_1}=P_{m_2}\ \Longrightarrow\ \theta(m_1)=\theta(m_2) \quad\text{for all }m_1,m_2\in\mathcal M . \] Without identification, the target is \[ \Theta(P;\mathcal M)=\{\theta(m):m\in\mathcal M,\ P_m=P\}. \] Writing $\theta(P)$ before establishing identification can hide incompatible latent models. Confidence sets additionally need a sampling law, confidence level, asymptotic sequence and uniformity class. Point identification, coverage and informative precision are separate properties.

Mediation. Total effects of randomized assignment are distinct from cross-world natural indirect effects. Belief/effort-channel effects require a meaningful mediator intervention and additional measurement, exclusion or mediation assumptions. Randomization of the initial policy alone does not supply those assumptions. Report bounds or interventional alternatives when the stronger target is unsupported.

Equilibrium. A counterfactual $W(z)$, $p(z)$, or $\mu_t^z$ requires individual optimization, feasibility, government/resource budgets, market clearing and state-transition laws. State equilibrium existence and selection, or report ranges over compatible equilibria. Initial-state integration includes subsequent endogenous transitions; current-state integration must use the policy-dependent distribution. Reduced-form invariance after policy is not assumed.

Welfare accounts. Scores, utility, health, dollars and ecological quantities require explicit conversion before addition. Fees, taxes, subsidies, wages and extortion payments are transfers between parties; distributional weights can make them welfare relevant, but their face value is not automatically a resource loss. State ownership, geographic boundaries, foreign-income weights and fiscal finance. Do not add profits to household welfare already including dividends, or count land capitalization and the underlying benefit twice. A benefit-cost expression must distinguish gross benefits from net welfare and subtract every real cost exactly once.

Derivatives and risk. Log derivatives require positive arguments; local responses require admissible perturbations and specified equilibrium branches. Differentiation under expectations needs regularity/domination, and boundaries may allow only one-sided derivatives. Risk uses a specified law; ambiguity uses a declared nonempty law set on a common history space. Adaptive policies must be nonanticipative. A robust criterion is an editorial choice unless attributed explicitly.

Scope overlaps. Allocation, collective choice, contracts, household bargaining and coordinated policy overlap economics with optimization and game theory. They are retained because they appeared in the original catalogue; no claim of a strictly game-theory-free selection is made.

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Econ-40-A2 · Exploration · LLM-generated · gpt 6 astra pro ·

GPT 6 Astra Pro attempt on Econ-40

Three-agent EFX for positive additive chores

D63-39: research attempt and adversarial verification

9 October 2026

Tools. Web browsing: YES. Exact rational computation: YES.

FORMAL RESTATEMENT

There are exactly three agents $[3]=\{1,2,3\}$ and a finite set of chores $[m]$, where $m\ge0$. Costs are strictly positive real numbers $c_{ig}>0$ for each agent and chore, with additive extension $c_i(B)=\sum_{g\in B}c_{ig}$. A complete allocation is a partition $A=(A_1,A_2,A_3)$ of $[m]$ into disjoint, possibly empty bundles. It is EFX if \[ \forall i,j\in[3]\ \forall g\in A_i:\qquad c_i(A_i\setminus\{g\})\le c_i(A_j). \] Thus removal is from the envious agent's own bundle. The target is \[ \forall m\ge0\ \forall c\in{\mathbb{R}}_{>0}^{3\times m}\ \exists A\text{ complete}: A\text{ is EFX}. \] The $m=0$ case is the empty allocation and satisfies every condition vacuously. No Pareto-efficiency requirement is imposed. Rational or integer data will be used for computations, and Proposition Proposition (Positive integer counterexamples suffice) proves that searching positive integer costs does not exclude a possible real-valued nonexistence example.

Stress points. Four-agent counterexamples do not disprove a three-agent statement. Additivity and strict positivity are retained. Empty own bundles impose no removal condition. Existence for a finite numerical grid is not existence for a continuous cost domain. A procedure that finds only EF1, approximate EFX, or a partial allocation does not solve the question.

QUICK LITERATURE/CONTEXT CHECK

The attachment cites He and Tao, EFX for Additive Chores: Nonexistence, Pareto Incompatibility, and Bi-Valued Existence, arXiv:2606.08872v2. Section 6 leaves the unrestricted three-agent additive case open; its nonexistence construction concerns at least four agents. https://arxiv.org/html/2606.08872v2.

A later relevant preprint is Xinkai Zhang, EFX Allocations for Three Agents and Seven or Eight Chores, arXiv:2609.10585v2. Theorems 1.1--1.2 report existence for seven and eight chores with nonnegative additive costs, via hand reductions and SMT unsatisfiability checks. The paper also identifies earlier coverage up to six chores. https://arxiv.org/html/2609.10585v2. Its external solver runs are not independently reproduced here. Accordingly, the elementary and algorithmic proofs below are distinguished from this cited computer-assisted coverage; the source does not settle arbitrary $m$.

Common-order existence is already part of the literature discussed in these sources. The full constructive proof below is included for verification, not presented as a novelty claim.

ATTACK PLAN

Proof track. Compress EFX to its maximum residual cost; prove a sufficient insertion condition; show that rotations toward cheapest bundles preserve EFX; use these lemmas to obtain a complete, complexity-bounded construction in the common-order class. Test whether the insertion step extends to heterogeneous rankings.

Disproof track. Enumerate all allocations of small positive instances; construct failures of naive insertion at nonenvying agents; encode nonexistence by strict linear inequalities for every allocation and reduce real candidates to positive integers.

Tools and roles. Additive residual thresholds give exact verification; pigeonhole arguments restrict empty bundles; choosing cheapest chores solves very small instances; functional directed graphs locate envy cycles; bundle-rank potentials bound rotations; common item ordering supplies the insertion inequality; strict-inequality perturbation controls numeric domains; disjunctive linear arithmetic describes complete counterexample searches.

Tiny cases. At most one chore per agent is always EFX. With four chores, giving one agent its two cheapest chores and one remaining chore to each other agent works, as proved next. These checks retain every removal and every comparison agent.

WORK

Lemma (Residual characterization and empty bundles): For nonempty $A_i$ put \[ T_i(A)=c_i(A_i)-\min_{g\in A_i}c_{ig}. \] For empty $A_i$ put $T_i(A)=0$. Then EFX is equivalent to $T_i(A)\le c_i(A_j)$ for all $i,j$. If $m>3$ and all costs are positive, every bundle in an EFX allocation is nonempty.
Proof: For nonempty $A_i$, the largest remaining cost after one deletion is obtained by removing a smallest-cost chore, giving exactly $T_i(A)$. Its inequality is equivalent to all the removal inequalities. For empty $A_i$, the original conditions are vacuous and the new ones read $0\le c_i(A_j)$, which hold.

If some bundle is empty and $m>3$, distributing the chores among at most two nonempty bundles leaves some agent with at least two chores. Removing any one from that bundle leaves at least one positive-cost chore, so its residual cost is positive. Its EFX comparison with the empty bundle, of cost zero, fails. More generally the same argument applies whenever an empty bundle coexists with a bundle of size at least two. ∎

Proposition (Elementary existence through four chores): Every positive additive instance with three agents and $m\le4$ has a complete EFX allocation.
Proof: For $m\le3$, use at most one chore per agent, so every own residual is zero. For $m=4$, give agent 1 two chores of smallest cost according to $c_1$, and give the remaining two chores singly to agents 2 and 3. Agent 1's residual is the larger cost of its two chores, which is at most the cost under $c_1$ of either remaining chore. Its comparisons with the other two bundles hold, and its comparison with itself follows because a positive cost was removed. Each other agent has own residual zero and hence satisfies every comparison. Ties among cheapest chores can be broken arbitrarily. ∎
Lemma (A sufficient insertion condition): Let $A$ be an EFX allocation of an already assigned subset, let $g$ be unassigned, and suppose an agent $i$ does not envy any bundle in the cost sense: \[ c_i(A_i)\le c_i(A_j)\quad\text{for all }j. \] If $A_i=\varnothing$, or if $c_{ig}\le\min_{h\in A_i}c_{ih}$, then adding $g$ to $A_i$ preserves EFX for all agents.
Proof: If $A_i$ is empty, its new residual is zero. Otherwise $g$ is a minimum-cost chore in the new bundle, and its new residual is $c_i(A_i)+c_{ig}-c_{ig}=c_i(A_i)$, which is at most every other bundle's cost by the hypothesis. Its comparison with its own new bundle also holds. Every other agent's own residual is unchanged. Its comparisons with bundles other than $i$ are unchanged, and its comparison with bundle $i$ weakly relaxes because $c_{jg}>0$. Thus all EFX inequalities hold. ∎
Lemma (Cheapest-bundle cycle rotations): For an EFX allocation with $n\ge1$ agents, draw one arrow $i\to j$ whenever agent $i$ envies some bundle, choosing $j$ to minimize $c_i(A_j)$; draw no arrow from a nonenvying agent. A directed cycle can be rotated by giving each agent on it the bundle of its outgoing neighbor. This preserves EFX and strictly reduces each rotating agent's own cost. For a fixed multiset of $n$ bundle contents, at most $n(n-1)$ such rotations are needed before the resulting graph has no directed cycle. At that point it has a vertex with no outgoing arrow, that is, a nonenvying agent.
Proof: Every arrow leads to a strictly cheaper bundle than the sender's current bundle, and specifically to one cheapest among all the current bundles. In a cycle rotation each rotating agent therefore receives a cheapest old bundle. From that agent's perspective the new own residual is at most its new whole-bundle cost, which is at most the cost of every old bundle. The new list of bundles is a permutation of the old list, so every one of its EFX comparisons holds. An agent outside the cycle retains its own bundle and residual, while the comparison bundles are merely permuted; its inequalities remain true as well. Strict improvement of the rotating agents follows from the definition of an arrow.

During a sequence of rotations with no insertion, the $n$ bundle contents are fixed. Each agent can move strictly downward in cost among these bundles at most $n-1$ times, including when several have equal cost. Across all agents there are at most $n(n-1)$ such strict improvements. Every rotation makes at least one strict improvement (in fact at least two), so the stated bound follows. Finally, a finite directed graph where every vertex has exactly one outgoing arrow contains a directed cycle: following arrows from any start eventually repeats a vertex. Thus a cycle-free graph with outdegree zero or one must have a vertex of outdegree zero. ∎

Theorem (Complete EFX under a common chore order): Suppose $n\ge1$ agents have positive additive costs and there is an order $g_1,\ldots,g_m$ such that \[ c_{i,g_1}\ge c_{i,g_2}\ge\cdots\ge c_{i,g_m}\quad\text{for every }i. \] Then a complete EFX allocation exists. For rational input, one can construct it with a strongly polynomial number of arithmetic operations and polynomial-size intermediate encodings. This includes proportional costs but permits agents to disagree arbitrarily about cost ratios while agreeing on the order.
Proof: Start with all bundles empty. Before adding $g_t$, eliminate every directed cycle by Lemma Lemma (Cheapest-bundle cycle rotations). At most $n(n-1)$ rotations occur in this phase; EFX is preserved and a nonenvying agent $i$ is obtained. Every chore already assigned precedes $g_t$ in the common order, including after bundle rotations. Hence $c_{i,g_t}\le c_{ih}$ for every $h\in A_i$. If $A_i$ is empty, the alternate condition in Lemma Lemma (A sufficient insertion condition) applies. Add $g_t$ to this agent. EFX is preserved. Induction proves that every prefix is completely allocated and EFX, and after $m$ steps the allocation is complete.

The common order can be found or verified in polynomial arithmetic time. If such an order exists, every pair of chores has coordinatewise comparable cost vectors: all agents weakly rank them in the same direction. Sorting by the sums $s_g=\sum_i c_{ig}$ therefore gives a common order. Indeed, if $s_g>s_h$, comparability excludes $c_{ig}\le c_{ih}$ for all $i$, so $c_{ig}\ge c_{ih}$ for all $i$; if their sums tie, comparability forces coordinatewise equality. Verify the obtained ordering for every row. This step takes $O(nm+m\log(m+1))$ arithmetic operations and comparisons.

Maintain the matrix $B_{ij}=c_i(A_j)$. Constructing all minimum-bundle arrows requires $O(n^2)$ comparisons; finding a cycle in the finite graph is polynomial in $n$. A rotation permutes columns of $B$, and an insertion adds the vector $(c_{1g},\ldots,c_{ng})$ to one column. With straightforward implementations, $O(mn^4+nm+m\log(m+1))$ arithmetic operations suffice, a deliberately loose bound. Entries are sums of at most $m$ input costs, so their rational encodings, and all comparisons, have polynomial bit length. The rotation bound depends on bundle ranks, not cost magnitudes. ∎

The obstruction to extending this proof indiscriminately

A nonenvying agent need not satisfy the minimum-cost condition for the next chore. This is not a minor technicality. Take three identical rows \[ c_1=c_2=c_3=(1,1,1,100) \] and the partial allocation $A_1=\{1\}$, $A_2=\{2\}$, $A_3=\{3\}$. It is EFX, and every agent is nonenvying. Adding chore 4 to any bundle gives its recipient residual cost 100 after the old unit-cost chore is removed, while another bundle has cost 1. Thus every direct insertion fails. A complete EFX allocation still exists: assign chore 4 alone, two unit chores to a second agent, and one unit chore to the third. This example disproves automatic extension by appending to a sink; it does not disprove existence. The common-order algorithm avoids it by processing the expensive chore first. Heterogeneous rankings provide no single order that automatically serves every row.
Proposition (Positive integer counterexamples suffice): For each fixed $m$, if a strictly positive real $3\times m$ cost matrix has no complete EFX allocation, then a strictly positive integer matrix of the same dimensions has none.
Proof: For every complete allocation $A$, choose one failure witness $i,j,g\in A_i$ with \[ D_{A,i,j,g}(c):=c_i(A_i\setminus\{g\})-c_i(A_j)>0. \] There are finitely many allocations and chosen strict inequalities. Each is a continuous linear inequality. All cost entries are also strictly positive. Therefore a sufficiently small neighborhood of the given matrix preserves positivity and every chosen strict violation. A rational matrix exists in this neighborhood by density of the rationals. It retains a violation for every allocation. Multiplying by a common positive denominator preserves the inequalities and yields positive integers. ∎
Corollary (Finite counterexample specification): For fixed $m$, existence of a positive-cost counterexample is equivalent to feasibility of \[ c_{ig}\ge1\quad(i,g),\qquad \bigwedge_{A\text{ complete}} \bigvee_{\substack{i,j\in[3],\ g\in A_i}} [D_{A,i,j,g}(c)\ge1]. \]
Proof: A feasible matrix gives a strict EFX violation for every allocation. Conversely, the positive integer matrix from Proposition Proposition (Positive integer counterexamples suffice) has every positive entry and every selected positive violation at least one. This proves feasibility of the displayed system. The formula must include all $3^m$ allocations, not merely balanced bundle sizes. ∎
Scaling each agent's whole cost row by any positive factor preserves every EFX inequality involving that agent. Thus row-sum normalization is another legitimate search convention, but it is a different normalization from the all-integer, unit-margin formula and should not be imposed simultaneously without justification.

VERIFICATION

Executed exact enumeration. Every positive $\{1,2\}$ cost matrix was tested for three agents and each $m=1,\ldots,5$. The respective matrix counts were $8,64,512,4,096,32,768$, and every one admitted an EFX allocation. A further 1,000 generated positive integer instances with three agents, nine chores, and costs in $\{1,\ldots,50\}$ also admitted EFX allocations. All allocation comparisons used integer sums, not floating point. This is a finite search, not an unsatisfiability proof over all real costs.

The shared bundled program checks/fairness_check.cpp includes both this enumeration and the goods tests. Its unsigned 32-bit generator is initialized to 20261009 and updated by $s\leftarrow1664525s+1013904223\pmod{2^{32}}$, with each entry $1+(s\bmod50)$. The nine-chore batch follows the 1,000 four-agent/six-good matrices; the exhaustive tests consume no generator states. The source and report specify that ordering.

Independent constructive checks. The bundled Python program checks/D63-39_common_order.py constructed allocations for 650 common-order positive instances: $n=1,\ldots,5$, $m=0,\ldots,12$, ten generated matrices per pair. It checked EFX after every rotation and insertion, and checked final completeness. Across these runs 151 cycle rotations occurred. It also verified failure of direct insertion in all three choices of recipient in the displayed four-chore example. These checks supplement, rather than replace, Theorem Theorem (Complete EFX under a common chore order).

The following standalone exact checker supplies the basic exhaustive-search method and the insertion test: 

\begin{lstlisting}[language=Python]
from itertools import product

def efx_chores(c,a): n,m=len(c),len(a) bundles=[[g for g in range(m) if a[g]==i] for i in range(n)] for i in range(n): if not bundles[i]: continue residual=sum(c[i][g] for g in bundles[i])-min(c[i][g] for g in bundles[i]) if any(residual>sum(c[i][g] for g in bundles[j]) for j in range(n)): return False return True

def find_allocation(c): for a in product(range(len(c)),repeat=len(c[0])): if efx_chores(c,a): return a return None

c=((1,1,1,100),)*3 for recipient in range(3): assert not efx_chores(c,(0,1,2,recipient)) assert efx_chores(c,(1,1,2,0)) for m in range(1,4): checked=0 for flat in product((1,2),repeat=3*m): c=tuple(flat[i*m:(i+1)*m] for i in range(3)) assert find_allocation(c) is not None checked+=1 assert checked==2**(3*m) print(m,checked,'exact EFX witnesses found') # The bundled C++ implementation runs the same exhaustive specification # through m=5 and the separate 1000-instance nine-chore sample. 

\end{lstlisting}

Adversarial audit. Every removal is from the owner's bundle. The rotation proof uses cheapest outgoing bundles, not arbitrary envy edges. Outsiders retain EFX because the whole list of comparison bundles is permuted. The polynomial rotation bound applies within a phase with fixed bundle contents and is restarted after each insertion. The common-order proof does not infer order agreement from additivity. A failed insertion can be repaired by reallocations in the explicit example, so it is not mislabeled a nonexistence counterexample. External computer-assisted results are not claimed as locally rerun certificates.

FINAL

LABEL: UNRESOLVED for unrestricted three-agent positive additive costs.

Strongest fully proved partial result. A complete EFX allocation is constructed with a strongly polynomial arithmetic bound for any number of agents whose chore orders agree, with fully proved insertion and cycle-rotation lemmas. All three-agent instances through four chores have an elementary direct proof. Possible real counterexamples reduce to positive integers and a complete finite linear-arithmetic specification. No counterexample was found in the executed finite searches.

Exact first gap. For three agents with heterogeneous chore rankings and arbitrary $m$, no procedure is proved to transform a partial EFX allocation into a complete one while preserving exact EFX. The specific missing step in the current strategy is an insertion or reassignment lemma that always produces an eligible recipient when no common order supplies the minimum-cost condition. The direct-insertion version of that step is explicitly false.

Three next targets. First, strengthen insertion by allowing a controlled sequence of bundle reassignments and prove its residual inequalities for the receiving agent, not only for unaffected agents. Second, solve the full unit-margin counterexample system for a fixed next dimension, retaining every allocation pattern and obtaining checkable rational witnesses or unsatisfiability certificates. Third, isolate a finite set of cross-order configurations that obstruct the common-order argument and prove a repair lemma for each; neither exhaustiveness nor such repairs have been established.

Minimal-counterexample information. The proofs here exclude $m\le4$ and every common-order instance. Taking the cited seven/eight-chore results together with their stated earlier coverage as external theorems excludes all $m\le8$, making $m\ge9$ the remaining range; this stronger bound is a literature dependency, not the outcome of our grid checks. A counterexample can be assumed to have positive integer costs. When $m>3$, any allocation that could be EFX must have all three bundles nonempty, but no particular nonempty bundle-size pattern may be assumed sufficient.

Go to contribution →

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

GPT 6 Astra Ultra attempt on Econ-40

Three-agent chore EFX: robust subcases and exact finite-type search

Problem D63-39. Status: unresolved. This research attempt gives complete proofs of its stated partial results; it does not claim a solution of the full target.

Recap and a current literature correction

For exactly three agents and finitely many chores, costs $c_i$ are additive with every singleton cost strictly positive. A complete partition $A$ is EFX if \[ c_i(A_i\setminus\{g\})\leq c_i(A_j) \quad\text{for all }i,j\in\{1,2,3\},\quad g\in A_i. \] The item is removed from the agent's own burden. The target quantifies over all real positive cost matrices and all numbers of chores.

The July 2026 version of He and Tao [he], Theorem 1, constructs nonexistence examples for every number of agents at least four. Section 6 explicitly leaves the three-agent additive question open. Their four-agent bi-valued existence result and their efficiency incompatibilities do not settle this target. This is essential: a blanket assertion that additive chore EFX existence remains unknown for every number of agents would now be inaccurate.

Our attempt develops an exact finite-type search formulation, proves that any real counterexample has a strictly positive integer counterpart, and provides constructive robust positive domains. The identical-cost positive result is known; the following elementary proof is included for completeness. None of these restricted statements is presented as a new general existence theorem.

The exact comparison and a robustness lemma

For an allocation define \[ D_i(A_i)=\begin{cases} c_i(A_i)-\min_{g\in A_i}c_i(g),&A_i\ne\varnothing,\\0,&A_i=\varnothing. \end{cases} \] Then EFX is equivalent to $D_i(A_i)\leq c_i(A_j)$ for every pair. Indeed removing the least costly own chore leaves the largest possible residual burden; for an empty bundle every original test is vacuous and $0\leq c_i(A_j)$.
Proposition (Any counterexample can be made integral): Fix the number $m$ of chores. The set of strictly positive real $3\times m$ cost matrices admitting no EFX allocation is open in ${\mathbb{R}}_{>0}^{3m}$. Consequently a real strictly positive counterexample exists for some $m$ if and only if a strictly positive integer counterexample exists for some $m$.
Proof: For each of the finitely many $3^m$ complete allocations $A$, failure of EFX means there is a triple $(i,j,g)$ with $g\in A_i$ such that the linear form $c_i(A_i\setminus\{g\})-c_i(A_j)$ is strictly positive. Choose one such witness for each $A$ at a counterexample $c$. All selected linear forms remain positive in a sufficiently small neighborhood of $c$, because there are only finitely many of them. Shrink the neighborhood to keep all singleton costs positive. Every matrix in it still fails EFX for every allocation. Density of rational matrices supplies a positive rational counterexample there. Multiplying each row by a positive common denominator produces positive integers and preserves every strict within-row comparison. The reverse implication is immediate. If $m=0$ the empty allocation is EFX, so there is no counterexample and openness is vacuous. ∎

This is a completeness justification for searching integer instances. It gives no upper bound on $m$ or on the required integer sizes, and therefore is not a finite decision procedure for the universal statement.

An exact finite-type reduction

Suppose chores fall into $t$ types. Type $h$ has multiplicity $M_h$ and strictly positive cost vector $(d_{1h},d_{2h},d_{3h})$, the same for all its copies. An allocation is described by nonnegative integers $x_{ih}$ satisfying $\sum_i x_{ih}=M_h$.
Theorem (Complete count formulation and search bound): A type-count array describes an EFX allocation if and only if for every $i,j$ with $\sum_hx_{ih}>0$, \[ \sum_h d_{ih}x_{ih}-\min_{h:x_{ih}>0}d_{ih} \leq \sum_h d_{ih}x_{jh}. \] For rational explicitly listed costs, exhaustive type-count search decides existence and outputs an allocation, or certifies nonexistence by checking all arrays, in \[ \left(\prod_{h=1}^t {M_h+2\choose2}\right)\operatorname{poly}(L,m,t) \ \leq\ (m+2)^{2t}\operatorname{poly}(L,m,t) \] bit operations. Thus it is polynomial for every fixed number of types $t$.
Proof: Within a type, identities of copies affect no cost comparison. The own total is $\sum_hd_{ih}x_{ih}$ and the smallest assigned singleton has cost $\min_{h:x_{ih}>0}d_{ih}$. The preceding exact comparison proves both directions; if the own bundle is empty its tests are vacuous. For a type with $M_h$ copies, the number of ordered triples of nonnegative counts summing to $M_h$ is ${M_h+2\choose2}$: place two separators among $M_h+2$ positions. Choices for types are independent. Enumerate every array and check its at most nine comparisons by exact arithmetic. A successful array is expanded into a partition by handing each agent its counted copies. If every array fails, every possible partition fails because it has one of these arrays. All sums have at most $t$ rational terms times integers at most $m$, so their bit lengths are polynomial in the explicit input length. The final estimate bounds each binomial coefficient by $(m+2)^2$. ∎

Constructive positive neighborhoods

Theorem (Scaled identical costs): If $c_i(g)=a_iw_g$ with $a_i>0$ and $w_g>0$, a complete EFX allocation is obtained by sorting chores in nonincreasing weight and assigning each chore to a bundle of minimum current weight. For rational inputs the algorithm runs in polynomial bit time.
Proof: Fix a nonempty final bundle $A_i$ and its last assigned chore $g_i$. It has minimum weight in $A_i$. Immediately before its assignment the weight of $A_i\setminus\{g_i\}$ was no more than the current weight of every other bundle. Other bundles only grow, so $w(A_i\setminus\{g_i\})\leq w(A_j)$ in the final allocation for every $j$. Removing any other $g$ from $A_i$ leaves at most this much weight. Multiplication by $a_i$ proves every chore-EFX comparison. Empty bundles have no own-removal tests. Sorting and accumulating rational weights take polynomial bit time. For no chores, output all empty bundles. ∎
Proposition (Quantitative persistence under heterogeneous costs): Fix a partition $A$ and positive reference weights $w_g$. Suppose $(1-\epsilon)a_iw_g\leq c_i(g)\leq(1+\epsilon)a_iw_g$ for $a_i>0$, $0\leq\epsilon<1$. If \[ (1+\epsilon)w(A_i\setminus\{g\}) \leq(1-\epsilon)w(A_j) \quad(i\ne j,\ g\in A_i), \] then $A$ is EFX for the heterogeneous costs. If each reference comparison is strict at $\epsilon=0$, a positive $\epsilon$ satisfies all these inequalities.
Proof: Bound the own residual using the upper singleton bounds and the compared bundle using the lower ones. The displayed inequality then yields $c_i(A_i\setminus\{g\})\leq c_i(A_j)$. Self-comparisons hold because costs are nonnegative. For strict reference comparisons, put $b=w(A_j)>a=w(A_i\setminus\{g\})\geq0$. Every such inequality holds for $\epsilon\leq(b-a)/(b+a)$; the minimum over the finite nonempty test set is positive. If there are no tests, every $\epsilon<1$ is allowed. ∎
Corollary (A sharp guarantee for every balanced partition): Let $m=3k$, $k\geq2$, and assume each agent's costs lie in $[a_i,R a_i]$ for some $a_i>0$. If $R\leq k/(k-1)$, every partition with $k$ chores per agent is EFX. This ratio is sharp for a guarantee that every such partition is EFX under only these bounds. For $k=1$, every singleton partition is EFX without a ratio restriction.
Proof: In a balanced partition any own bundle after deletion has at most $k-1$ chores, each of cost at most $Ra_i$, while a compared bundle has $k$ chores, each of cost at least $a_i$. Thus $(k-1)Ra_i\leq ka_i$ gives EFX. For sharpness at $R>k/(k-1)$, take any balanced partition, make all chores in agent 1's bundle cost $R$ to agent 1, and all chores in agent 2's bundle cost $1$ to agent 1; assign any allowed positive costs to the remaining entries. After any removal agent 1's residual cost is $(k-1)R>k$, violating EFX toward agent 2. This refutes the universal-partition guarantee, not existence of a different EFX partition. Singleton residuals are empty. ∎

Verification and first gap

The finite-type theorem is a complete finite certificate format: failed allocation arrays can each be accompanied by one strict violated comparison. The robustness and balanced-partition arguments use the chore removal direction throughout and allow empty bundles. Integer-counterexample density does not supply a bounded search region. For three unrestricted real cost rows, the number of item types can grow with $m$, and the count algorithm becomes exponential; the positive subclasses do not constrain those rows. No invariant is proved that guarantees at least one successful count array for all such instances, and no three-agent counterexample is produced. That is the exact remaining gap to the target.
Finite implementation checks.
An exact integer implementation compared the count criterion with every one of the $3^6=729$ labeled allocations on each of 30 six-chore instances having three types of two copies, with independently drawn positive integer cost vectors and random seed $20261009$. For each instance the sets of successful count arrays agreed exactly. The proportional-cost greedy proof was additionally checked on 100 instances. These are finite consistency checks, not a universal existence certificate.

References

  • [he] W. He and B. Tao, EFX for Additive Chores: Nonexistence, Pareto Incompatibility, and Bi-Valued Existence, arXiv:2606.08872v2, 9 July 2026. Section 2 fixes the chore definition; Theorem 1 concerns $n\geq4$; Section 6 expressly retains the three-agent question. https://arxiv.org/html/2606.08872v2.

Completion Estimate

15%

Go to contribution →