Extension of Complete EFX Allocations by Two Universally Small Goods with Arbitrary Internal Ranking While Preserving Bundles
low tier2026-11-01OP-7reviewed by Claude Code中文版
Abstract
The existence of an envy-free up to any good (EFX) allocation for four or more agents with additive valuations remains an open problem in discrete fair division. While the literature provides techniques to insert a single universally least good, extending allocations by multiple items when agents hold conflicting preferences over those items presents a difficulty. We show that any complete EFX allocation of $m$ indivisible goods among $n$ agents with nonnegative additive valuations extends to a complete EFX allocation of $m+2$ goods whenever every agent values each of the two additional goods weakly less than all of the original $m$ goods. The agents need not agree on the relative ranking between the two added goods. The construction preserves every original bundle as an intact unit, permuting the bundles across agents and giving each new good to one agent (possibly the same agent for both), so that every agent's utility weakly increases. The existence of the required permutation and recipient pair follows from an assignment principle for real utility matrices equipped with two additive vector bonuses. Iterating it gives a complete EFX allocation for any number of agents and goods whenever all agents agree on the order of consecutive pairs of goods, while possibly disagreeing within each pair. All definitions, lemmas, and the main extension theorem are formalized and verified in Lean 4.
1. Introduction
The fair division of indivisible goods among a set of agents is a standard setting in discrete fair division. In an additive valuation model, each agent $i \in \{1, \dots, n\}$ assigns a nonnegative real value $v_i(g) \ge 0$ to each good $g$, and values a subset $S$ by $v_i(S) = \sum_{g \in S} v_i(g)$. An allocation is an ordered partition $A = (A_1, \dots, A_n)$ distributing all items. The fairness property of envy-freeness up to any good (EFX) was introduced in DOI:10.1145/3355902: an allocation is EFX if for every pair of distinct agents $i \ne j$ and every good $g \in A_j$, agent $i$ satisfies $v_i(A_i) \ge v_i(A_j \setminus \{g\})$. Under EFX, no agent envies another agent's bundle after the hypothetical deletion of any single item from that bundle. While exact envy-freeness cannot always be achieved with indivisible items, EFX has become a benchmark of fairness. As surveyed in arXiv:2208.08782 (Section 4.1, Open Problem 2), whether a complete EFX allocation always exists for $n \ge 4$ agents with additive valuations is an open problem, with $n = 4$ being the smallest open case.
Previous work has mapped out the landscape of EFX existence across parameters and valuation classes. For $n = 2$ agents, EFX allocations always exist via cut-and-choose (arXiv:1707.04769). For $n = 3$ agents with additive valuations, existence was established in the literature ('EFX Exists for Three Agents'), and extended to three agents when at least one valuation is additive or MMS-feasible. When unallocated goods are permitted, an EFX allocation leaving at most one good unallocated exists for $n = 4$ agents, and an EFX allocation discarding at most $n - 2$ goods exists in general. Complete EFX allocations have also been verified for restricted numbers of goods: whenever $m \le n + 3$, and for $n = 4$ whenever $m \le 9$, using computer-assisted methods. Other settings where positive results hold include instances with up to three valuation types ('EFX Exists for Three Types of Agents', EC 2025), the relaxation EF2X for four agents, and allocations on multigraph instances. On the negative side, EFX allocations can fail for three agents with monotone submodular valuations and for four or more agents with additive chores. No additive-goods counterexample is known.
A standard constructive approach in fair division is inductive item insertion. Cycle elimination and common-order insertion are standard (arXiv:1707.04769v3, Lemma 6.1 and Appendix B): after envy cycles are removed some bundle is unenvied, and a good that every agent values weakly less than every allocated good can be added to that bundle without breaking EFX. When all agents rank the goods in the same order, inserting the goods one at a time from the most to the least valuable gives a complete EFX allocation. This one-good step cannot be applied twice in a row when agents disagree on how the two new goods compare: the second good need not be weakly smaller than the first for every agent. Furthermore, while arXiv:2504.03951 analyzes allocations with $n + 2$ goods, it does not supply an inductive preservation theorem that maintains existing bundles intact.
This post presents a verified theorem in Lean 4, efx_exists_of_two_universal_small_goods_ir, which resolves the insertion problem for two universally small goods under arbitrary within-pair rankings. Specifically, let $m$ items already be partitioned into a complete EFX allocation among $n$ agents. Suppose two additional items are introduced such that every agent values both items weakly less than all of the original $m$ items. No common ranking is assumed between the two new items: agent preferences on this pair may be completely arbitrary. We prove that there exists a complete EFX allocation of all $m + 2$ items that keeps every original bundle intact, weakly improves the utility of every agent relative to the initial allocation, and gives each new good to one agent, possibly the same agent for both.
2. Preliminaries
We consider the fair division of a finite set of indivisible goods among a finite set of agents. In the Lean formalization, the agents are indexed by the finite type $\text{Fin } n = \{0, 1, \dots, n-1\}$ for a positive integer $n$, and the goods are indexed by $\text{Fin } m = \{0, 1, \dots, m-1\}$ for an integer $m$. Valuations are represented as a function $u : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$, where $u(i, g) \ge 0$ represents the utility agent $i$ derives from good $g$.
Definition 1 (additive_valuation). Given an item utility function $u : \text{Fin } m \to \mathbb{R}$, the additive valuation induced by $u$ is the function mapping any finite subset of goods $S \subseteq \text{Fin } m$ to the sum of the utilities of its elements: $$ \text{additive\_valuation}(u)(S) = \sum_{g \in S} u(g). $$ When $S = \emptyset$, the empty sum evaluates to $0$.
Definition 2 (bundle_of). An allocation is represented as a function $\sigma : \text{Fin } m \to \text{Fin } n$, mapping each good $g$ to the agent $\sigma(g)$ who receives it. For any agent $i \in \text{Fin } n$, the bundle assigned to $i$ under $\sigma$ is the set of items mapped to $i$: $$ \text{bundle\_of}(\sigma)(i) = \{ g \in \text{Fin } m \mid \sigma(g) = i \}. $$ Under this representation, every good is assigned to exactly one agent, ensuring that the allocation is complete and that the bundles form a partition of the set of goods $\text{Fin } m$. Bundles may be empty if an agent receives no items.
Definition 3 (is_efx_goods). Given a utility profile $u : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ and an allocation $\sigma : \text{Fin } m \to \text{Fin } n$, the allocation is EFX if for every pair of distinct agents $i, j \in \text{Fin } n$ with $i \ne j$, and for every item $g \in \text{bundle\_of}(\sigma)(j)$, agent $i$ values her own bundle at least as much as agent $j$'s bundle with $g$ removed: $$ \text{is\_efx\_goods}(u, \sigma) \iff \forall i, j \in \text{Fin } n, i \ne j \implies \forall g \in \text{bundle\_of}(\sigma)(j), $$ $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(j) \setminus \{g\}) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(i)). $$
Remark on Definition Choices: The definition of is_efx_goods in the Lean formalization incorporates several specific modeling choices that are standard in discrete fair division:
- Inequality convention: The definition requires a weak inequality ($\le$). Envy towards $j$'s trimmed bundle is eliminated if $i$'s bundle value is at least that of $j$'s bundle without $g$.
- Deletion of zero-valued items: The condition quantifies over every good $g \in \text{bundle\_of}(\sigma)(j)$, regardless of whether $u(i, g) > 0$ or $u(i, g) = 0$. In some literature, EFX is formulated by quantifying only over goods with positive valuation for agent $i$; here, zero-valued goods must also satisfy the inequality when removed.
- Empty bundles: If $\text{bundle\_of}(\sigma)(j) = \emptyset$, the universal quantification over $g \in \emptyset$ holds vacuously, meaning that no agent envies an empty bundle.
- Types and indices: In the setting with $m + 2$ goods, the original $m$ goods are embedded into $\text{Fin } (m+2)$ via cast mappings, while the two new goods are represented by indices $m$ and $m+1$.
3. Main result
The primary result formalized in Lean is efx_exists_of_two_universal_small_goods_ir. It proves that any complete EFX allocation of $m$ goods can be extended to a complete EFX allocation of $m+2$ goods when the two additional goods are universally small for all agents, without requiring any agreement on how the two added goods compare to each other.
Theorem (efx_exists_of_two_universal_small_goods_ir). Let $m, n \in \mathbb{N}$ with $n > 0$. Let $u : \text{Fin } n \to \text{Fin } (m+2) \to \mathbb{R}$ be a valuation profile satisfying $u(i, g) \ge 0$ for all $i \in \text{Fin } n$ and $g \in \text{Fin } (m+2)$. Assume that the two additional goods, indexed by $m$ and $m+1$, are universally small relative to the original $m$ goods: - For every agent $i \in \text{Fin } n$ and every original good $g \in \text{Fin } m$, $$ u(i, m) \le u(i, g). $$ - For every agent $i \in \text{Fin } n$ and every original good $g \in \text{Fin } m$, $$ u(i, m+1) \le u(i, g). $$ Let $\sigma : \text{Fin } m \to \text{Fin } n$ be any complete EFX allocation of the original $m$ goods under the restricted valuations $g \mapsto u(i, g)$. Then there exists a complete allocation $\tau : \text{Fin } (m+2) \to \text{Fin } n$ of all $m+2$ goods satisfying three properties:
1. Complete EFX: $\tau$ is an EFX allocation of all $m+2$ goods under $u$, namely is_efx_goods u τ. 2. Individual Rationality: Every agent $i \in \text{Fin } n$ receives at least her original utility under $\sigma$: $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(i)) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(i)). $$ 3. Bundle Preservation: Any two original goods that were allocated to the same agent under $\sigma$ remain allocated to the same agent under $\tau$: $$ \forall g, h \in \text{Fin } m, \quad \sigma(g) = \sigma(h) \implies \tau(g) = \tau(h). $$
The Lean statement of efx_exists_of_two_universal_small_goods_ir formalizes this directly: quantified over natural numbers $m$ and $n$ with hypothesis $0 < n$, nonnegativity of $u$, the two smallness hypotheses, and an initial allocation satisfying is_efx_goods, it asserts the existence of an extended allocation $\tau$ satisfying is_efx_goods, weak utility improvement for all agents, and bundle preservation for all original items.
What This Result Adds: Beyond extending the allocation by two items, the theorem gives the following:
- Preservation of Original Bundles: Original bundles are never split or rearranged; they are merely reassigned across agents via an agent permutation. This preservation allows the extension to be applied modularly to any pre-existing EFX allocation.
- Weak Utility Improvement: No agent suffers a loss in total utility upon the introduction and distribution of the two new goods.
- Iterative EFX for Common Pairs: Starting from the empty allocation and applying the theorem pair by pair gives, as a corollary also proved in Lean, a complete EFX allocation for any number of agents $n \ge 1$ and any number of goods $m$, provided that for every agent, $\lfloor g/2 \rfloor < \lfloor h/2 \rfloor$ implies $u(i,h) \le u(i,g)$: all agents agree that every good of an earlier pair is weakly more valuable than every good of a later pair, while ranking the two goods within a pair arbitrarily. For odd $m$ the last block is a single good, added by the one-good step.
theorem efx_exists_of_two_universal_small_goods_ir {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin (m+2) → ℝ) (hu : ∀ i g, 0 ≤ u i g) (hsmall₀ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m).castSucc ≤ u i g.castSucc.castSucc) (hsmall₁ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last (m+1)) ≤ u i g.castSucc.castSucc) (σ : Fin m → Fin n) (hσ : is_efx_goods (fun i g => u i g.castSucc.castSucc) σ) : ∃ τ : Fin (m+2) → Fin n, is_efx_goods u τ ∧ (∀ i, additive_valuation (fun g : Fin m => u i g.castSucc.castSucc) (bundle_of σ i) ≤ additive_valuation (u i) (bundle_of τ i)) ∧ (∀ g h : Fin m, σ g = σ h → τ g.castSucc.castSucc = τ h.castSucc.castSucc)
4. Proof
Idea of the Proof: The proof reduces the insertion of two universally small goods to an assignment problem on a real matrix with two vector bonuses. Let $w(i, j) = \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(j))$ be the matrix of valuations under the existing allocation $\sigma$, where row $i$ represents agent $i$'s valuations of the $n$ bundles. Let $a(i) = u(i, m)$ and $b(i) = u(i, m+1)$ denote the valuations of the two new goods, which are nonnegative vectors. We seek an agent permutation $p$, which reassigns the existing bundle $\text{bundle\_of}(\sigma)(p(j))$ to agent $j$, together with two recipients $r, s \in \text{Fin } n$ (which may coincide) for goods $m$ and $m+1$ respectively. Under this plan, agent $j$'s new bundle has valuation $$ v_i(\text{bundle\_of}(\tau)(j)) = w(i, p(j)) + [j = r] a(i) + [j = s] b(i) $$ from the perspective of agent $i$. For this allocation to be EFX and individually rational:
- Every agent $i$ must weakly prefer her new bundle to her old bundle: $w(i, i) \le v_i(\text{bundle\_of}(\tau)(i))$.
- If another agent $i \ne r$ envies bundle $r$, removing good $m$ (which subtracts $a(i)$) must eliminate the envy.
- If another agent $i \ne s$ envies bundle $s$, removing good $m+1$ (which subtracts $b(i)$) must eliminate the envy.
- For any original good $g_0 \in \text{Fin } m$ belonging to bundle $j$, the smallness hypotheses guarantee that $u(i, g_0) \ge a(i)$ (if $j = r$) and $u(i, g_0) \ge b(i)$ (if $j = s$). Consequently, removing $g_0$ deducts at least as much utility as removing the bonus item, so the trimmed bundle never exceeds the own valuation.
- If $j \ne r$ and $j \ne s$, bundle $j$ contains no bonuses, and envy elimination follows from the initial EFX property of $\sigma$.
The matrix lemma finite_two_bonus_ordered_assignment guarantees the existence of a permutation $p$ and indices $r, s$ satisfying conditions (1), (2), and (3).
Supporting Lemmas: The proof relies on five lemmas from the library.
Lemma 1 (additive_valuation_erase_of_mem). Let $u : \text{Fin } m \to \mathbb{R}$ be an item valuation function, $S \subseteq \text{Fin } m$ a finite subset, and $g \in S$. Then $$ \text{additive\_valuation}(u)(S \setminus \{g\}) = \text{additive\_valuation}(u)(S) - u(g). $$ Proof in Lean: This is settled by rewriting the sum over $S$ as the sum over $S \setminus \{g\}$ plus $u(g)$ using the finite sum erase identity and subtracting $u(g)$ from both sides.
Lemma 2 (bundle_of_permute_agents). Let $\sigma : \text{Fin } m \to \text{Fin } n$ be an allocation and $p$ an agent permutation ($p \in \text{Equiv.Perm}(\text{Fin } n)$). Define the permuted allocation $\tau_0(g) = p^{-1}(\sigma(g))$. Then for every agent $i \in \text{Fin } n$, $$ \text{bundle\_of}(\tau_0)(i) = \text{bundle\_of}(\sigma)(p(i)). $$ Proof in Lean: By definition, $\text{bundle\_of}(\tau_0)(i) = \{ g \mid p^{-1}(\sigma(g)) = i \}$. Applying the permutation equivalence $p^{-1}(x) = i \iff x = p(i)$, the filtering condition becomes $\sigma(g) = p(i)$, which is the definition of $\text{bundle\_of}(\sigma)(p(i))$.
Lemma 3 (additive_valuation_bundle_last_cases). Let $u : \text{Fin } (m+1) \to \mathbb{R}$, $\sigma : \text{Fin } m \to \text{Fin } n$, and $s, j \in \text{Fin } n$. Consider the extended allocation mapping the last element to agent $s$ and restricting to $\sigma$ on the original $m$ elements. Then $$ \text{additive\_valuation}(u)(\text{bundle\_of}(\text{Fin.lastCases}(s, \sigma))(j)) = \text{additive\_valuation}(u \circ \text{Fin.castSucc})(\text{bundle\_of}(\sigma)(j)) + [s = j] u(\text{Fin.last } m). $$ Proof in Lean: Settled by splitting the finite sum into the sum over the cast elements of $\text{Fin } m$ and the single last element, using the finite sum decomposition and the definition of Fin.lastCases.
Lemma 4 (is_efx_goods_all_pairs). Let $u : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ have nonnegative values, and let $\sigma$ be an EFX allocation (is_efx_goods u σ). Then for all agents $i, j \in \text{Fin } n$ (including $i = j$) and every $g \in \text{bundle\_of}(\sigma)(j)$, $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(j) \setminus \{g\}) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(i)). $$ Proof in Lean: When $i \ne j$, the inequality is the definition of is_efx_goods. When $i = j$, erasing $g$ from $\text{bundle\_of}(\sigma)(i)$ subtracts $u(i, g) \ge 0$, so the value can only decrease weakly, satisfying the inequality.
Lemma 5 (finite_two_bonus_ordered_assignment). Let $\alpha$ be a finite, nonempty, decidable type. For any real matrix $w : \alpha \to \alpha \to \mathbb{R}$ and nonnegative vectors $a, b : \alpha \to \mathbb{R}$, there exist a permutation $p \in \text{Equiv.Perm}(\alpha)$ and two indices $r, s \in \alpha$ such that:
1. For all $i \in \alpha$, $$ w(i, i) \le w(i, p(i)) + [i = r] a(i) + [i = s] b(i). $$ 2. For all $i \in \alpha$ with $i \ne r$, $$ w(i, p(r)) + [r = s] b(i) \le w(i, p(i)) + [i = r] a(i) + [i = s] b(i). $$ 3. For all $i \in \alpha$ with $i \ne s$, $$ w(i, p(s)) + [s = r] a(i) \le w(i, p(i)) + [i = r] a(i) + [i = s] b(i). $$
Proof in Lean: Consider the states in which only one of the two bonuses has been assigned: a permutation $p$, a recipient $r$ and a choice of which bonus $r$ holds, such that every agent weakly improves on $w(i,i)$ and no agent envies the old column $p(r)$ under $r$'s bonus. Such states exist (remove envy cycles, then give the bonus to an unenvied column), and the Lean proof takes one maximizing the total own utility. If the other bonus can be given to some agent $s$ so that conditions (1)-(3) hold, we are done. Otherwise, an envy-cycle argument on the maximal state shows that every column other than $r$'s is envied and that $r$'s column is unenvied, so $r$'s column is the unique source; and some agent $i \ne r$ would envy $r$'s column if $r$ held the other bonus instead. A column-switch lemma then shows that either an envy cycle among the old columns or a cycle through $r$'s column with the bonuses switched strictly increases the total utility while staying feasible, contradicting maximality.
Combining the Steps for the Main Proof: The Lean proof of efx_exists_of_two_universal_small_goods_ir proceeds through the following steps:
Step 1 (Setup): Since $n > 0$, $\text{Fin } n$ is nonempty. We instantiate $w(i, j) = \text{additive\_valuation}(u(i) \circ \text{cast})(\text{bundle\_of}(\sigma)(j))$, $a(i) = u(i, m)$, and $b(i) = u(i, m+1)$. Since $u \ge 0$, both $a$ and $b$ are nonnegative vectors.
Step 2 (Invoking Lemma 5): Applying finite_two_bonus_ordered_assignment to $w, a, b$ yields a permutation $p$ and indices $r, s \in \text{Fin } n$ satisfying conditions (1), (2), and (3), denoted in the Lean proof by $h_I$, $h_A$, and $h_B$.
Step 3 (Constructing the Allocation):
- Initially, define $\tau_0 : \text{Fin } m \to \text{Fin } n$ by $\tau_0(g) = p^{-1}(\sigma(g))$.
- Next, define $\tau_1 : \text{Fin } (m+1) \to \text{Fin } n$ by assigning good $m$ to agent $r$: $\tau_1 = \text{Fin.lastCases}(r, \tau_0)$.
- Finally, define $\tau : \text{Fin } (m+2) \to \text{Fin } n$ by assigning good $m+1$ to agent $s$: $\tau = \text{Fin.lastCases}(s, \tau_1)$.
Step 4 (Evaluating Bundles): Applying Lemma 3 twice and Lemma 2, we obtain for all $i, j \in \text{Fin } n$: $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(j)) = w(i, p(j)) + [j = r] a(i) + [j = s] b(i). $$
Step 5 (Individual Rationality): For each agent $i$, condition (1) from Lemma 5 gives $$ w(i, i) \le w(i, p(i)) + [i = r] a(i) + [i = s] b(i) = \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(i)). $$
Step 6 (Trimming Bounds): - For $i \ne r$, by condition (2) and bundle evaluation, $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(r)) - a(i) = w(i, p(r)) + [r = s] b(i) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(i)). $$ - For $i \ne s$, by condition (3) and bundle evaluation, $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(s)) - b(i) = w(i, p(s)) + [s = r] a(i) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(i)). $$
Step 7 (EFX Verification): Let $i, j \in \text{Fin } n$ with $i \ne j$, and let $g \in \text{bundle\_of}(\tau)(j)$. By Lemma 1, erasing $g$ leaves value $\text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(j)) - u(i, g)$. We case-split on $g$:
- Case $g = m+1$ (the last good): Then $j = s$. Since $i \ne j$, $i \ne s$. The removed utility is $u(i, m+1) = b(i)$. The remaining value is bounded by Step 6.
- Case $g = m$ (the penultimate good): Then $j = r$. Since $i \ne j$, $i \ne r$. The removed utility is $u(i, m) = a(i)$. The remaining value is bounded by Step 6.
- Case $g = g_0$ for an original good $g_0 \in \text{Fin } m$:
- If $j = r$, then $i \ne r$. By hypothesis $hsmall_0$, $a(i) \le u(i, g_0)$. Thus, subtracting $u(i, g_0)$ subtracts at least $a(i)$. Since removing $a(i)$ already bounds the bundle by Step 6, removing $g_0$ preserves the inequality.
- If $j = s$, then $i \ne s$. By hypothesis $hsmall_1$, $b(i) \le u(i, g_0)$. Subtracting $u(i, g_0)$ subtracts at least $b(i)$, and Step 6 bounds the remaining value.
- If $j \ne r$ and $j \ne s$, neither bonus was assigned to $j$. The bundle of $j$ is simply $\text{bundle\_of}(\sigma)(p(j))$. By Lemma 4 applied to $\sigma$, agent $i$'s valuation for this bundle after erasing $g_0$ is at most $w(i, i)$. By Step 5, $w(i, i) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(i))$, completing the proof.
Step 8 (Bundle Preservation): For any original goods $g, h \in \text{Fin } m$ with $\sigma(g) = \sigma(h)$, $\tau(g) = p^{-1}(\sigma(g)) = p^{-1}(\sigma(h)) = \tau(h)$.
5. Discussion
The result established in efx_exists_of_two_universal_small_goods_ir extends inductive allocation methods for EFX, but does not settle the unrestricted four-agent EFX existence problem surveyed in arXiv:2208.08782.
Scope and Relationship to Open Problem: The general question asks whether an EFX allocation exists for every instance with $n \ge 4$ agents and additive goods, regardless of how item valuations are structured. The theorem presented here imposes a structural condition on the two incoming goods: they must be universally small, meaning that every agent values each of the two goods weakly less than all previously allocated items. In exchange for this restriction, the theorem yields the following structural properties:
- Arbitrary Intra-Pair Ordering: Unlike the baseline single-item insertion technique in arXiv:1707.04769v3 Appendix B, which requires a common ranking across items, the two added goods here can have completely discordant rankings across agents. One agent may strictly prefer the good with index $m$ while another strictly prefers the good with index $m+1$.
- Full Bundle Preservation: All original goods allocated together remain allocated together under $\tau$. Existing bundles are treated as rigid items and permuted among agents. The counting and existence results for $n+2$ goods in arXiv:2504.03951 (Section 3) do not start from an arbitrary EFX allocation with arbitrarily many old goods, and do not state such a preservation property.
- Weak Pareto Improvement: Every agent's utility weakly improves monotonically as pairs of goods are added.
Inductive Application to Common-Pair Instances: As a consequence of efx_exists_of_two_universal_small_goods_ir, complete EFX allocations exist for an infinite family of instances with any number of agents $n$: instances where goods can be partitioned into pairs $P_1, P_2, \dots, P_k$ such that all agents agree that every good in $P_t$ is weakly more valuable than every good in $P_{t+1}$, even though agents may rank the two items within each pair $P_t$ in opposite orders. Starting from the empty allocation (which is vacuously EFX) and repeatedly applying the theorem for $t = 1, \dots, k$ constructs a complete EFX allocation for all $2k$ goods; with an odd number of goods, the last block is a single good and the one-good step finishes. This corollary is proved in Lean as well. It contains the identical-ranking case, where no disagreement is allowed at all.
Open Directions: Several immediate questions arise from this formalization:
- Larger Bundles of Small Goods: Can the result be extended from pairs of universally small goods to triples, or to sets of $k \ge 3$ universally small goods with arbitrary internal preference profiles? A natural question is whether an analogue of
finite_two_bonus_ordered_assignmentholds for $k \ge 3$ vector bonuses. - General Four-Agent Additive EFX: Resolving the existence of EFX allocations for $n = 4$ agents with additive valuations on arbitrary instances remains open. While computer-assisted verification has settled cases up to $m \le 9$ goods and EF2X is known for $n = 4$, an existence proof or counterexample for unrestricted instances is unknown.
- Valuation Boundaries: EFX can fail for three agents with monotone submodular valuations and for four or more agents with additive chores. Delineating the precise frontier where EFX transitions from guaranteed existence to non-existence remains an open question in discrete fair division.
Why it is research-level
- Extends common least-good insertion to two universally small goods with arbitrary within-pair rankings, preserving every old bundle and weakly improving all own utilities; iteration gives complete EFX for any number of agents and goods ordered in common pairs
Lean declarations
- efx_exists_of_two_universal_small_goods_irLet m and n be natural numbers with n positive. There are m+2 goods with nonnegative real additive values for n agents. Each agent values…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
- finite_two_bonus_ordered_assignmentFor any finite nonempty real matrix w and two nonnegative agent-dependent bonuses a and b, there is a permutation of the old columns, a…
- additive_valuation_erase_of_memRemoving a good belonging to a finite bundle subtracts exactly its item value from the additive value of that bundle.
- bundle_of_permute_agentsReassigning every good by the inverse of an agent permutation makes the bundle of agent i equal to the old bundle of the permuted agent.
- additive_valuation_bundle_last_casesAssigning the additional last good to agent s adds exactly its value to the old bundle value of s and leaves every other bundle value…
- is_efx_goods_all_pairsFor nonnegative additive values, the EFX inequalities also hold when the observer and the target agent coincide.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2208.08782 — Fair Division of Indivisible Goods: Recent Progress and Open Questions
- arXiv:1707.04769
- arXiv:2504.03951
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.