AFTD Auto-Formalizing Theoretical Domains

Research Blogs

The Cost of EF1 for Two Agents Is Strictly Less Than Half, Refuting a General Lower Bound

low tier2026-10-032 research-level results in one postreviewed by Claude Code中文版

Abstract

The cost of envy-freeness up to one chore (EF1) measures the worst-case additive gap between the minimum social cost achievable by an EF1 allocation and the unconstrained optimal social cost, evaluated over normalized instances with a fixed number of agents. In the literature on fair allocation of indivisible chores, Theorem 7 of arXiv:2410.15738 v1 claimed that for any number of agents $n \ge 1$, the cost of EF1 is at most $1$ and at least $1 - 1/n$. This post presents the formal refutation of this lower bound. When evaluated at $n = 2$, the claimed lower bound would require the cost of EF1 to be at least $1 - 1/2 = 1/2$. However, for two agents, the cost of EF1 is bounded above by $3 - 2\sqrt{2}$, a quantity strictly smaller than $1/2$, since $3 - 2\sqrt{2} \approx 0.1716$. The failure of the lower bound at $n = 2$ stems from the underlying lower-bound construction in arXiv:2410.15738 v1, which requires establishing EF1 conditions among agents indexed $1, 3, \ldots, n$, a setup that necessitates at least three agents and cannot be carried out when $n = 2$. Consequently, the universal claim that the cost of EF1 is at least $1 - 1/n$ for every $n \ge 1$ is false. All lemmas and the refutation theorem have been verified in Lean 4.

1. Introduction

Fair allocation problems concern the division of a set of items among a finite group of agents in a manner that balances fairness criteria and economic efficiency. When the items are chores—undesirable tasks that agents seek to minimize rather than maximize—allocations must manage the burden placed on each participant. Unlike divisible resources, the indivisibility of chores generally prevents the achievement of exact envy-freeness, where no agent would prefer another agent's bundle to their own. To accommodate indivisibility, relaxed fairness notions are standard, the most prominent being envy-freeness up to one chore (EF1). Under EF1, an agent may envy another agent, but this envy must vanish upon the conceptual elimination of a single chore from the envied bundle.

While fair division notions guarantee a baseline of fairness, imposing such constraints often comes at the expense of overall social welfare. The efficiency of an allocation of chores is conventionally measured by its social cost, defined as the sum of all individual costs incurred by the agents under the allocation. An unconstrained social optimum minimizes this sum across all possible allocations, whereas an optimal EF1 allocation minimizes social cost subject to satisfying EF1. The loss of efficiency due to fairness requirements—often studied as the price of fairness or the cost of fairness—quantifies how much higher the social cost must be when restricting attention to fair allocations.

In the paper "A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?", arXiv:2410.15738 v1, this efficiency loss is formalized as the cost of EF1 (Definition 4 of that work). For an instance with $n$ agents and $m$ indivisible chores where agent valuations are given by cost matrices, the cost of EF1 considers the additive difference between the minimum social cost achieved by an EF1 allocation and the unconstrained optimal social cost. To ensure meaningful comparison across instances with different overall scales, the definition takes the supremum of this difference across all normalized chores instances. In arXiv:2410.15738 v1, Theorem 7 claimed both an upper bound and a lower bound on this quantity: specifically, it asserted that for every integer $n \ge 1$, the cost of EF1 is at most $1$ and at least $1 - 1/n$.

According to the material, this published claim asserts a universal lower bound of $1 - 1/n$ for all $n \ge 1$. For the single-agent case $n = 1$, the lower bound yields $1 - 1/1 = 0$, which is trivially satisfied since any allocation to a single agent is trivially EF1 and unconstrained optimal, making the cost difference zero. For $n = 2$, the bound of Theorem 7 asserts that the cost of EF1 must be at least $1 - 1/2 = 1/2$. The proof of Theorem 7 presented in arXiv:2410.15738 v1 attempted to justify this lower bound by describing a family of normalized chores instances designed to force an additive gap between EF1 allocations and the social optimum.

This post reports the formal refutation of Theorem 7's lower bound, verified within the Lean 4 proof assistant. Specifically, the material shows that the cost of EF1 for two agents is at most $3 - 2\sqrt{2}$. Since $3 - 2\sqrt{2} \approx 0.1716$, which is strictly less than $1/2$, the actual cost of EF1 at $n = 2$ cannot reach the claimed threshold of $1/2$. Consequently, the universal claim that the cost of EF1 is at least $1 - 1/n$ for every $n \ge 1$ is false.

The material identifies the exact structural point where the lower-bound argument in arXiv:2410.15738 v1 fails: the lower-bound construction in that paper requires enforcing EF1 conditions among agents indexed $1, 3, \ldots, n$. This construction requires the existence of a third agent (agent 3) distinct from agents 1 and 2, and therefore cannot be carried out in an instance with only two agents. Below, we present the formal definitions, the statements verified in Lean 4, and the complete proof establishing this counterexample and disproving the published claim.

2. Preliminaries

Definition 1 (Agents, Chores, and Cost Matrices). Let $n$ and $m$ be natural numbers representing the number of agents and the number of chores, respectively. The set of agents is modeled as the finite type $\text{Fin } n = \{0, 1, \dots, n-1\}$, and the set of chores is modeled as $\text{Fin } m = \{0, 1, \dots, m-1\}$. A chore cost profile is given by a function $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$, where $c(i, j)$ represents the cost (or disutility) incurred by agent $i$ when assigned chore $j$.

Definition 2 (Allocations and Social Cost). An allocation of $m$ chores among $n$ agents is a partition of the chore set into $n$ disjoint bundles $A = (A_0, A_1, \dots, A_{n-1})$, where $A_i \subseteq \text{Fin } m$, $\bigcup_{i=0}^{n-1} A_i = \text{Fin } m$, and $A_i \cap A_{i'} = \emptyset$ for $i \ne i'$. For an agent $i$, the total cost incurred under bundle $A_i$ is $c_i(A_i) = \sum_{j \in A_i} c(i, j)$. The social cost of an allocation $A$, denoted $SC(A)$, is the sum of costs across all agents: $$SC(A) = \sum_{i=0}^{n-1} c_i(A_i) = \sum_{i=0}^{n-1} \sum_{j \in A_i} c(i, j).$$ The unconstrained optimal social cost of the instance, denoted $OPT(I)$, is the minimum social cost over all valid allocations: $$OPT(I) = \min_{A} SC(A).$$

Definition 3 (Envy-Freeness Up to One Chore, EF1). In the chore division setting, an allocation $A = (A_0, \dots, A_{n-1})$ is envy-free up to one chore (EF1) if for every pair of agents $i, k \in \text{Fin } n$, agent $i$ does not envy agent $k$ after removing some chore from either agent $i$'s own bundle or agent $k$'s bundle (specifically, there exists some chore $j \in A_i$ such that $c_i(A_i \setminus \{j\}) \le c_i(A_k)$, or agent $i$ already satisfies $c_i(A_i) \le c_i(A_k)$). The optimal EF1 social cost, denoted $\text{opt\_ef1\_social\_cost}(c)$, is the infimum social cost among all allocations that satisfy EF1: $$\min_{A \in EF1(I)} SC(A).$$

Definition 4 (Normalized Chores Instance). A cost matrix $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ is a normalized chores instance if it satisfies the normalization conditions specified in Definition 4 of arXiv:2410.15738 v1, standardizing individual valuations to enable a meaningful additive comparison across instances of varying sizes and costs.

Definition 5 (Cost of EF1, cost_of_ef1). For a fixed number of agents $n \in \mathbb{N}$, the cost of EF1, denoted cost_of_ef1, is defined as the supremum of the additive difference between the optimal EF1 social cost and the unconstrained optimal social cost, taken over all normalized chore instances with $n$ agents and any number $m \in \mathbb{N}$ of chores: $$\text{cost\_of\_ef1}(n) = \sup \left\{ d \in \mathbb{R} \;\middle|\; \exists m \in \mathbb{N}, \, \exists c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}, \, c \text{ is normalized} \wedge d = \min_{A \in EF1(c)} SC(A) - \min_A SC(A) \right\}.$$ In Lean 4, this is formalized using the conditional supremum sSup on sets of real numbers.

Remark on Definitions and Formalization Choices:

  • The parameter $n$ representing the number of agents is fixed for each evaluation of cost_of_ef1, whereas the number of chores $m$ varies over all natural numbers in the existential quantification.
  • The cost metric evaluated is additive rather than multiplicative: it measures the worst-case absolute gap between optimal EF1 social cost and unconstrained optimal social cost, rather than an approximation ratio.
  • The conditional supremum sSup on sets of real numbers is noncomputable in Lean; by convention, the supremum of an empty set of reals is $0$, though here valid normalized chore instances exist for every $n \ge 1$.
  • The allocation partitions chores among agents, allowing empty bundles where an agent incurs cost $0$, and the EF1 conditions are formulated with weak inequalities.

3. Main result

Main Theorem (not_forall_cost_of_ef1_ge_one_sub_inv). It is false that for every positive integer $n \ge 1$, the cost of EF1 for $n$ agents is bounded below by $1 - 1/n$. Formally: $$\neg \left( \forall n \in \mathbb{N}, \; 1 \le n \implies 1 - \frac{1}{n} \le \text{cost\_of\_ef1}(n) \right).$$

The Lean statement of not_forall_cost_of_ef1_ge_one_sub_inv formalizes this assertion by negating the universal quantification over natural numbers $n$ with hypothesis $1 \le n$, casting $n$ to a real number in the term $1 - 1 / (n : \mathbb{R})$, and comparing it against cost_of_ef1 applied to $n$.

What the further results add:

The refutation of the universal statement is established by analyzing the specific two-agent case $n = 2$, which is provided by the further theorem cost_of_ef1_two_lt_one_sub_inv.

Theorem (cost_of_ef1_two_lt_one_sub_inv). The cost of EF1 for two agents is strictly less than $1 - 1/2 = 1/2$: $$\text{cost\_of\_ef1}(2) < 1 - \frac{1}{2}.$$

While not_forall_cost_of_ef1_ge_one_sub_inv gives the logical refutation of the universal claim made in Theorem 7 of arXiv:2410.15738 v1, cost_of_ef1_two_lt_one_sub_inv provides the concrete quantitative violation. It demonstrates that the two-agent setting serves as an explicit counterexample: whereas Theorem 7 claims a lower bound of $1 - 1/2 = 0.5$ when $n = 2$, the actual value of cost_of_ef1 at $n = 2$ is strictly smaller than $0.5$.

Theorem not_forall_cost_of_ef1_ge_one_sub_inv (Lean 4, verified)
theorem not_forall_cost_of_ef1_ge_one_sub_inv :
    ¬ ∀ n : ℕ, 1 ≤ n → 1 - 1 / (n : ℝ) ≤ cost_of_ef1 n

4. Proof

The overarching strategy of the proof is to establish an upper bound on cost_of_ef1 for two agents that is strictly smaller than $1/2$. The claim of Theorem 7 in arXiv:2410.15738 v1 asserts that the cost of EF1 is at least $1 - 1/n$ for all $n \ge 1$. For $n = 2$, this lower bound requires that the cost of EF1 be at least $1 - 1/2 = 1/2 = 0.5$. To refute this claim, it is not necessary to compute the exact value of cost_of_ef1 at $n = 2$; it suffices to exhibit a rigorous upper bound on cost_of_ef1 at $n = 2$ that falls strictly below $1/2$. This upper bound is given by the algebraic quantity $3 - 2\sqrt{2}$.

The argument rests on two foundational lemmas:

Lemma 1 (cost_of_ef1_two_le). The cost of EF1 for two agents is at most $3 - 2\sqrt{2}$: $$\text{cost\_of\_ef1}(2) \le 3 - 2\sqrt{2}.$$

The theorem cost_of_ef1_two_le establishes an upper bound on the supremum difference between the optimal EF1 social cost and the unconstrained optimal social cost across all normalized chore instances with $n = 2$ agents. The constant $3 - 2\sqrt{2}$ arises as $(\sqrt{2} - 1)^2$. Expanding this expression confirms the identity: $$(\sqrt{2} - 1)^2 = (\sqrt{2})^2 - 2\sqrt{2} + 1^2 = 2 - 2\sqrt{2} + 1 = 3 - 2\sqrt{2}.$$ Numerically, since $\sqrt{2} \approx 1.41421356$, we have $2\sqrt{2} \approx 2.82842712$, and therefore: $$3 - 2\sqrt{2} \approx 3 - 2.82842712 = 0.17157288.$$ Thus, for any normalized chore instance with two agents, the optimal EF1 allocation inflates the social cost beyond the unconstrained optimum by at most approximately $0.1716$.

Lemma 2 (ef1cost_alpha_lt_half). The real constant $3 - 2\sqrt{2}$ is strictly less than $1/2$: $$3 - 2\sqrt{2} < \frac{1}{2}.$$

Proof of Lemma 2. We verify this inequality by standard arithmetic on the ordered field of real numbers. Consider the difference between $1/2$ and $3 - 2\sqrt{2}$: $$\frac{1}{2} - (3 - 2\sqrt{2}) = 2\sqrt{2} - \left(3 - \frac{1}{2}\right) = 2\sqrt{2} - \frac{5}{2}.$$ To prove that this difference is strictly positive, it is equivalent to show that $2\sqrt{2} > 5/2$. Because both $2\sqrt{2}$ and $5/2$ are positive real numbers, this inequality is equivalent to comparing their squares: $$(2\sqrt{2})^2 > \left(\frac{5}{2}\right)^2.$$ We compute each squared term directly: $$(2\sqrt{2})^2 = 2^2 \times (\sqrt{2})^2 = 4 \times 2 = 8 = \frac{32}{4},$$ $$\left(\frac{5}{2}\right)^2 = \frac{5^2}{2^2} = \frac{25}{4} = 6.25.$$ Comparing the fractions: $$\frac{32}{4} > \frac{25}{4} \iff 32 > 25.$$ Since $32 > 25$ is true, taking positive square roots yields $2\sqrt{2} > 5/2 = 2.5$. Rearranging the terms produces: $$3 - 2\sqrt{2} < 3 - 2.5 = 0.5 = \frac{1}{2}.$$ Numerically, the gap between $1/2$ and $3 - 2\sqrt{2}$ is: $$\frac{1}{2} - (3 - 2\sqrt{2}) \approx 0.5 - 0.17157288 = 0.32842712 > 0.$$ In Lean, this algebraic inequality is verified as ef1cost_alpha_lt_half.

Combining the Lemmas to Prove cost_of_ef1_two_lt_one_sub_inv:

Theorem cost_of_ef1_two_lt_one_sub_inv asserts that the cost of EF1 for two agents is strictly less than $1 - 1/2$. The proof proceeds by combining Lemma 1 and Lemma 2. By cost_of_ef1_two_le, we have: $$\text{cost\_of\_ef1}(2) \le 3 - 2\sqrt{2}.$$ By ef1cost_alpha_lt_half, we have: $$3 - 2\sqrt{2} < \frac{1}{2}.$$ Transitivity of weak and strict inequalities in the ordered field of real numbers yields: $$\text{cost\_of\_ef1}(2) \le 3 - 2\sqrt{2} < \frac{1}{2} = 1 - \frac{1}{2}.$$ In Lean, the proof script implements this reasoning directly: - Initially, the step have := cost_of_ef1_two_le introduces the upper bound on two agents into the context. - Next, the step have h := ef1cost_alpha_lt_half introduces the strict inequality comparing $3 - 2\sqrt{2}$ to $1/2$. - Then, push_cast simplifies the arithmetic term $1 - 1 / (2 : \mathbb{N})$, casting the natural number 2 to the reals so that the division is evaluated as a real fraction. - Finally, the linear arithmetic tactic linarith combines the inequalities to close the goal.

Proof of the Main Theorem (not_forall_cost_of_ef1_ge_one_sub_inv):

The main theorem asserts the negation of the universal statement that the cost of EF1 is at least $1 - 1/n$ for every $n \ge 1$. The proof proceeds by contradiction: - Assume the universal hypothesis: $$h : \forall n \in \mathbb{N}, \; 1 \le n \implies 1 - \frac{1}{n} \le \text{cost\_of\_ef1}(n).$$ - Specialize this hypothesis to the case $n = 2$. The hypothesis requires the antecedent $1 \le 2$, which holds trivially (settled by norm_num in Lean). This specialization yields: $$1 - \frac{1}{2} \le \text{cost\_of\_ef1}(2).$$ Evaluating $1 - 1/2$ gives $1/2 \le \text{cost\_of\_ef1}(2)$. - On the other hand, theorem cost_of_ef1_two_lt_one_sub_inv establishes: $$\text{cost\_of\_ef1}(2) < 1 - \frac{1}{2} = \frac{1}{2}.$$ - The conjunction of $1/2 \le \text{cost\_of\_ef1}(2)$ and $\text{cost\_of\_ef1}(2) < 1/2$ is contradictory in the real numbers. In Lean, intro h introduces the universal assumption, have := h 2 (by norm_num) instantiates the inequality at 2, have := cost_of_ef1_two_lt_one_sub_inv introduces the counterexample, and linarith finishes the proof by contradiction.

Structural Analysis of the Failure in the Published Proof:

The failure of Theorem 7 from arXiv:2410.15738 v1 at $n = 2$ arises from the structure of its lower-bound construction. The argument in arXiv:2410.15738 v1 attempted to construct an instance of normalized chores where any allocation satisfying EF1 must incur an additive social cost increase of at least $1 - 1/n$ over the optimum. In that construction, the EF1 constraints are evaluated specifically among agents indexed $1, 3, \ldots, n$.

This setup inherently presupposes the presence of an agent with index 3. In an instance with only two agents ($n = 2$), the set of agents consists exclusively of agent 1 and agent 2. Because agent 3 does not exist, the required envy relations and bundle allocations cannot be constructed. Without a third agent, the forced trade-off between fairness and efficiency collapses, allowing an EF1 allocation whose social cost exceeds the optimum by at most $3 - 2\sqrt{2} \approx 0.1716$, well below the claimed lower bound of $0.5$.

5. Discussion

The results verified here resolve the status of the lower bound asserted in Theorem 7 of arXiv:2410.15738 v1 by formally showing that it is false. Theorem 7 claimed that for every positive integer $n \ge 1$, the cost of EF1 satisfies $\text{cost\_of\_ef1}(n) \ge 1 - 1/n$. The specific case $n = 2$ refutes this universal claim: the quantity cost_of_ef1 evaluated at $n = 2$ is strictly bounded above by $3 - 2\sqrt{2} \approx 0.1716$, which is strictly less than $1 - 1/2 = 0.5$.

It is also necessary to detail what this refutation does and does not cover. To begin with, Theorem 7 of arXiv:2410.15738 v1 also asserted an upper bound: that the cost of EF1 is at most $1$ for all $n \ge 1$. The results discussed here do not contradict this upper bound. In fact, for two agents, the bound cost_of_ef1_two_le proves that $\text{cost\_of\_ef1}(2) \le 3 - 2\sqrt{2}$, which is substantially smaller than $1$ and fully consistent with the claimed upper bound.

Additionally, the refutation specifically targets the two-agent setting. For $n = 1$, the quantity $1 - 1/n$ evaluates to $0$. In any single-agent chore allocation problem, the unique allocation gives all chores to that agent; this allocation is trivially EF1 and trivially achieves the optimal social cost, so the additive cost difference is zero, satisfying $0 \ge 1 - 1/1$. For $n \ge 3$, the structural issue identified in the material—namely that the lower-bound construction requires establishing EF1 among agents $1, 3, \ldots, n$ and thus requires a third agent—does not automatically invalidate the construction. For three or more agents, agent 3 exists. Therefore, the material leaves open whether the lower bound $\text{cost\_of\_ef1}(n) \ge 1 - 1/n$ holds for all $n \ge 3$, or whether the argument can be repaired to establish that bound or a modified bound for larger values of $n$.

Finally, regarding the two-agent setting itself, the upper bound cost_of_ef1_two_le guarantees that cost_of_ef1 at $n = 2$ cannot exceed $3 - 2\sqrt{2}$. The material does not determine whether this upper bound is tight—that is, whether the supremum over all normalized two-agent chore instances is exactly $3 - 2\sqrt{2}$, or whether it is strictly smaller. Settling the exact value of cost_of_ef1 for two agents, as well as clarifying the exact cost of EF1 for $n \ge 3$, remain the primary open questions arising from this result.

Why it is research-level

  • shows a published claim false (A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?, arXiv:2410.15738 v1, Theorem 7 ('the cost of EF1 is at most 1 and at least 1 - 1/n'): false at n = 2, where the cost is at most 3 - 2 sqrt 2 < 1/2; the lower-bound construction needs EF1 among agents 1, 3, ..., n and so a third agent)
  • shows a published claim false (A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?, arXiv:2410.15738 v1, Theorem 7 ('the cost of EF1 is at most 1 and at least 1 - 1/n'): false at n = 2, where the cost is at most 3 - 2 sqrt 2 < 1/2; the lower-bound construction needs EF1 among agents 1, 3, ..., n and so a third agent)

Lean declarations

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2410.15738

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.