op819_single_high_efx_one_good
For any number of agents $n \ge 1$, $m = 1$ good, and parameter $R \ge 0$, there exists a deterministic online algorithm that achieves a $1$-EFX allocation for all single-high valuation profiles with parameter $R$.
Statement
theorem op819_single_high_efx_one_good (n : ℕ) (R : ℝ) (hR : 0 ≤ R) :
has_online_single_high_alpha_efx (n + 1) 1 R 1- Source
- arXiv:2610.34625
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- has_online_single_high_alpha_efxThere exists a deterministic online allocation algorithm for n agents and m goods that guarantees an alpha-EFX allocation for every…
- is_alpha_efx_goodsAn allocation of m indivisible goods to n agents is alpha-EFX under additive valuations u if for every pair of distinct agents i and j,…
- is_single_high_profileA valuation profile of n agents on m goods is a single-high profile with ratio R if every agent has a single-high valuation with ratio R.
- is_single_high_valuationAn agent's additive valuation vector on m goods is a single-high valuation with ratio R if there exists a good of value R such that all…
- 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.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- is_online_allocatorAn allocation algorithm on m goods for n agents is online if the allocation of each arriving good t depends only on the valuation vectors…
Read back from the Lean
Given a natural number $n$ and a real number $R \ge 0$, there exists an online allocation algorithm for allocating $1$ good among $n + 1$ agents such that for every valuation profile in which each agent has a single-high valuation with parameter $R$, the resulting allocation is $1$-EFX (exact EFX for goods).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that 1-EFX is achievable online with a single good ($m = 1$), the proof exhibits a constant allocation algorithm that assigns the single good to agent 0 regardless of the reported valuations. This algorithm is trivially online. Because there is only one good in total, removing that good from any bundle leaves the empty set, which simplifies the EFX threshold to $1 \cdot v_i(\emptyset) = 0$. Since single-high valuations with parameter $R \ge 0$ are non-negative everywhere, agent $i$'s bundle valuation is at least 0, satisfying the 1-EFX condition.
We propose the constant algorithm that always allocates the good to agent 0, reducing the goal to verifying online admissibility and the 1-EFX property.
We instantiate the existential quantifier with the deterministic allocator that assigns the single good to agent 0 regardless of the valuation profile. Splitting the conjunction with `constructor` produces two goals: showing that this allocator is an online algorithm, and verifying that the resulting allocation satisfies 1-EFX for every single-high profile with parameter $R$.
use fun _ _ => 0 constructor
The proposed algorithm is an online allocator.
At the single time step $t$, the allocation decision must depend only on valuations up to step $t$. Because the algorithm constantly outputs agent 0 without reading any valuation profile, the outputs on any two agreeing profiles are identical by definition (`rfl`).
· intros v v' t ht rfl
For any distinct agents $i \ne j$ and any good $g$ in agent $j$'s bundle, removing $g$ from that bundle yields the empty set.
We introduce an arbitrary single-high profile $v$, distinct agents $i \ne j$, and a good $g$ belonging to agent $j$'s bundle. Because there is only one good in total (the space of goods is $\text{Fin } 1$, a subsingleton type), any element $x$ must equal $g$ by `Subsingleton.elim`. Hence the condition $x \ne g$ required by `Finset.mem_erase` cannot hold, which by `iff_false` and `Finset.notMem_empty` proves that the bundle with $g$ removed is empty (`herase`).
uses
Finset.mem_erase,Finset.notMem_empty,iff_false,Subsingleton.elim· intros v hv i j hij g hg have herase : (bundle_of (fun _ => (0 : Fin (n + 1))) j).erase g = ∅ := by ext x simp only [Finset.mem_erase, Finset.notMem_empty, iff_false] intro ⟨hne, _⟩ exact hne (Subsingleton.elim x g)
The 1-EFX inequality reduces to showing that agent $i$'s valuation for each item in their bundle is non-negative.
Substituting $\emptyset$ for the erased bundle via `herase`, the required 1-EFX inequality becomes $1 \cdot v_i(\emptyset) \le v_i(\text{bundle}_i)$. By definition of additive valuation, the valuation of the empty bundle is 0, and $1 \cdot 0 = 0$ by `mul_zero`. Thus the left-hand side is 0. By `Finset.sum_nonneg`, the right-hand sum $\sum_{x \in \text{bundle}_i} v_i(x)$ is at least 0 provided every item in the bundle has a non-negative valuation.
uses
mul_zero,Finset.sum_nonnegrw [herase] dsimp [additive_valuation] rw [mul_zero] apply Finset.sum_nonneg
Agent $i$'s valuation for any good is non-negative, concluding the proof.
For any good $x$, the single-high assumption gives an item $g_0$ such that $v_i(g_0) = R$ and $v_i(g') = 1$ for all $g' \ne g_0$. Case analysis on $x = g_0$ shows that if $x = g_0$, then $v_i(x) = R \ge 0$ by the hypothesis $0 \le R$; otherwise $x \ne g_0$, so $v_i(x) = 1 \ge 0$ by linear arithmetic. Hence every term in the sum is non-negative.
intro x _ rcases hv i with ⟨g0, hg0, hrest⟩ by_cases hx : x = g0 · rw [hx, hg0]; exact hR · rw [hrest x hx]; linarith
Finset.mem_erase- An element belongs to a finset with a specified item removed if and only if it is distinct from that item and belongs to the original finset.
Finset.notMem_empty- The empty finset contains no elements.
iff_false- A proposition is equivalent to False if and only if its negation holds.
Subsingleton.elim- Any two elements of a subsingleton type are equal.
mul_zero- Multiplying any element by zero gives zero.
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- For a single good, 1-EFX is trivially achievable online for any number of agents and any ratio R >= 0. -/theorem op819_single_high_efx_one_good (n : ℕ) (R : ℝ) (hR : 0 ≤ R) : has_online_single_high_alpha_efx (n + 1) 1 R 1 := by use fun _ _ => 0 constructor · intros v v' t ht rfl · intros v hv i j hij g hg have herase : (bundle_of (fun _ => (0 : Fin (n + 1))) j).erase g = ∅ := by ext x simp only [Finset.mem_erase, Finset.notMem_empty, iff_false] intro ⟨hne, _⟩ exact hne (Subsingleton.elim x g) rw [herase] dsimp [additive_valuation] rw [mul_zero] apply Finset.sum_nonneg intro x _ rcases hv i with ⟨g0, hg0, hrest⟩ by_cases hx : x = g0 · rw [hx, hg0]; exact hR · rw [hrest x hx]; linarith