recursively_balanced_alpha_le_round_robin_universal_alpha
The universal EF1 approximation factor for recursively balanced sequences recursively_balanced_alpha is at most the universal factor for Round-Robin sequences round_robin_universal_alpha.
Statement
theorem recursively_balanced_alpha_le_round_robin_universal_alpha :
recursively_balanced_alpha ≤ round_robin_universal_alpha- Formalizes
- arXiv:2610.23686, Sec. 6
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 14
- recursively_balanced_alphaThe universal EF1 approximation factor α_RB for recursively balanced picking sequences is the infimum over all recursively balanced…
- round_robin_universal_alphaThe universal EF1 approximation factor α_RR for Round-Robin picking sequences is the infimum over all Round-Robin sequences with at least…
- round_robin_sequence_is_recursively_balancedEvery Round-Robin picking sequence of length m for n agents is recursively balanced.
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i g. - picking_sequence_alphaThe best EF1 approximation factor guaranteed for a picking sequence mechanism seq with n agents is the supremum of factors α that are…
- is_picking_sequence_pneA profile of reported strict rankings is a pure Nash equilibrium of the picking-sequence mechanism if no agent can obtain a bundle of…
- is_recursively_balancedA picking sequence of length m for n agents is recursively balanced if each complete round of n turns contains every agent exactly once…
- is_round_robin_sequenceA picking sequence seq of type List (Fin n) is a Round-Robin sequence if there exists an instance of NeZero n such that seq equals…
- SocialChoice.FairDivision.Indivisible.AdditiveValuationAn additive valuation is determined by per-item weights.
weight i gis the value agentiassigns to goodgindividually. The bundle… - is_guaranteed_sequence_ef1_factorA factor α is guaranteed for a picking sequence mechanism seq with n agents if for every nonnegative additive valuation profile and every…
- picking_sequence_outcomeThe allocation returned by the picking-sequence mechanism PS_π: agents act in the order seq, and at each turn the active agent takes its…
- round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- SocialChoice.FairDivision.Indivisible.ValuationAn abstract valuation assigns a real value to each agent-bundle pair.
val i Sis the value agentiassigns to bundleS. Lives in… - g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
The theorem asserts that recursively_balanced_alpha ≤ round_robin_universal_alpha, where:
1. recursively_balanced_alpha is the infimum (sInf) in ℝ of the set of all y : ℝ for which there exist a natural number n ≥ 2 and a list seq : List (Fin n) such that seq is recursively balanced (for every s : ℕ, the slice of seq of length n starting at index s * n has no duplicates) and y = picking_sequence_alpha n seq.
2. round_robin_universal_alpha is the infimum (sInf) in ℝ of the set of all y : ℝ for which there exist a natural number n ≥ 2 and a list seq : List (Fin n) such that seq is a round-robin sequence (NeZero n and seq equals the round-robin sequence of length seq.length whose t-th element is t % n) and y = picking_sequence_alpha n seq.
3. For any n and seq : List (Fin n), picking_sequence_alpha n seq is the supremum (sSup) in ℝ of all α : ℝ such that α is guaranteed to be an EF1 factor for seq: namely, for every non-negative additive valuation weighting w : Fin n → Fin seq.length → ℝ (with 0 ≤ w i g for all i, g) and every ranking profile rank : Fin n → Fin seq.length ≃ Fin seq.length, if rank is a pure Nash equilibrium of the picking sequence for the additive valuation induced by w on seq, then the resulting allocation outcome satisfies α-EF1.
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
The universal EF1 approximation factors for recursively balanced sequences and round-robin sequences are defined as the infima of their guaranteed factors over all sequences with at least two agents. Because every round-robin sequence is recursively balanced, the set of round-robin sequences is a subclass of the recursively balanced sequences, so the infimum for round-robin is taken over a subset. Since all guaranteed factors are non-negative and the round-robin class is nonempty, taking the infimum over the larger class yields a value at most that over round-robin.
For any number of agents $n$ and picking sequence seq, the approximation factor $\alpha = 0$ is guaranteed to satisfy the EF1 property.
Given non-negative item weights $w \ge 0$, any pure Nash equilibrium ranking, and any pair of distinct agents $i \ne j$ where agent $j$'s allocation $A_j$ is nonempty, we select an arbitrary item $g \in A_j$. The required EF1 condition is $0 \cdot v_i(A_j \setminus \{g\}) \le v_i(A_i)$. By `zero_mul`, the left-hand side is $0$, while the right-hand side is the sum $\sum_{x \in A_i} w_i(x)$, which is non-negative by `Finset.sum_nonneg` because each item weight is non-negative.
uses
zero_mul,Finset.sum_nonnegintro w hw rank hpne i j hij hAj rcases hAj with ⟨g, hg⟩ refine ⟨g, hg, ?_⟩ dsimp [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] rw [zero_mul] exact Finset.sum_nonneg fun x _ => hw i x
If the set of guaranteed EF1 factors for a sequence is bounded above, its supremum is at least $0$.
The guaranteed factor $\mathrm{picking\_sequence\_alpha}(n, \mathrm{seq})$ is defined as the supremum of all factors $\alpha$ guaranteed by the sequence. Since $0$ belongs to this set by `recursively_balanced_alpha_le_round_robin_universal_alpha_zero_is_guaranteed`, the supremum is at least $0$ by `le_csSup` whenever the set is bounded above.
uses
le_csSup,recursively_balanced_alpha_le_round_robin_universal_alpha_zero_is_guaranteeddsimp [picking_sequence_alpha] by_cases h : BddAbove {α | is_guaranteed_sequence_ef1_factor n seq α} · exact le_csSup h (recursively_balanced_alpha_le_round_robin_universal_alpha_zero_is_guaranteed n seq)
If the set of guaranteed EF1 factors is not bounded above, its supremum is $0$ by definition, so the factor remains at least $0$.
By the definition of the supremum on real numbers (`Real.sSup_def`), the supremum of an unbounded set defaults to $0$. Assuming the set is bounded leads to a contradiction via `False.elim`, leaving the equality $0 = 0$. Thus in all cases, the guaranteed factor is at least $0$.
uses
Real.sSup_def,False.elim· have h0 : sSup {α | is_guaranteed_sequence_ef1_factor n seq α} = 0 := by rw [Real.sSup_def] split_ifs with h' · exact False.elim (h h'.2) · rfl rw [h0]
To show $\mathrm{recursively\_balanced\_alpha} \le \mathrm{round\_robin\_universal\_alpha}$, it suffices to show that the set of recursively balanced factors is bounded below, the set of round-robin factors is nonempty, and the latter is a subset of the former.
Both universal factors are defined as infima over sets of picking-sequence guarantees: $T$ over all recursively balanced sequences with $n \ge 2$, and $S$ over all round-robin sequences with $n \ge 2$. By `csInf_le_csInf`, proving $\inf T \le \inf S$ reduces to showing that $T$ is bounded below, $S$ is nonempty, and $S \subseteq T$.
uses
csInf_le_csInfdsimp [recursively_balanced_alpha, round_robin_universal_alpha] apply csInf_le_csInf
The set of guaranteed factors for recursively balanced sequences is bounded below by $0$.
Every element of this set is of the form $\mathrm{picking\_sequence\_alpha}(n, \mathrm{seq})$, which was shown to be non-negative in `recursively_balanced_alpha_le_round_robin_universal_alpha_zero_le_alpha`.
uses
recursively_balanced_alpha_le_round_robin_universal_alpha_zero_le_alpha· use 0 rintro x ⟨n, seq, hseq, hn, rfl⟩ exact recursively_balanced_alpha_le_round_robin_universal_alpha_zero_le_alpha n seq
The set of round-robin sequence factors is nonempty.
We witness nonemptiness with $n = 2$ and the round-robin sequence of length $0$ (`round_robin_sequence 2 0`). The condition $2 \le 2$ holds by reflexivity (`le_rfl`), and the assumption $2 \ne 0$ is inferred by typeclass resolution (`inferInstance`).
uses
inferInstance,le_rfl· use picking_sequence_alpha 2 (round_robin_sequence 2 0) refine ⟨2, round_robin_sequence 2 0, ⟨inferInstance, rfl⟩, le_rfl, rfl⟩
Every round-robin sequence factor is also the factor of a recursively balanced sequence, establishing $S \subseteq T$.
Given an element of $S$, it arises from a round-robin sequence $\mathrm{seq}$ for $n \ge 2$, meaning $\mathrm{seq} = \mathrm{round\_robin\_sequence}(n, \mathrm{seq.length})$. By `round_robin_sequence_is_recursively_balanced`, every round-robin sequence is recursively balanced, so this sequence witnesses that the same factor belongs to $T$.
uses
round_robin_sequence_is_recursively_balanced· rintro y ⟨n, seq, ⟨inst, heq⟩, hn, rfl⟩ refine ⟨n, seq, ?_, hn, rfl⟩ rw [heq] exact round_robin_sequence_is_recursively_balanced n seq.length
zero_mul- Multiplying zero by any element yields zero ($0 \cdot a = 0$).
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative.
le_csSup- Any element of a set bounded above in a conditionally complete lattice is at most the supremum of that set.
recursively_balanced_alpha_le_round_robin_universal_alpha_zero_is_guaranteed- For any number of agents $n$ and picking sequence seq, the factor $\alpha = 0$ is a guaranteed EF1 factor.
Real.sSup_def- The supremum of a set of real numbers is its least upper bound if the set is nonempty and bounded above, and $0$ otherwise.
False.elim- From a contradiction (False), any conclusion can be deduced.
csInf_le_csInf- If $t$ is bounded below, $s$ is nonempty, and $s \subseteq t$, then $\inf t \le \inf s$ in a conditionally complete lattice.
recursively_balanced_alpha_le_round_robin_universal_alpha_zero_le_alpha- For any number of agents $n$ and picking sequence seq, the guaranteed approximation factor is at least $0$.
inferInstance- Derives a typeclass instance from the ambient context (here, that $2 \ne 0$).
le_rfl- The inequality relation is reflexive ($a \le a$).
round_robin_sequence_is_recursively_balanced- Every round-robin sequence is recursively balanced.
- In Lean's definition of the real supremum (`Real.sSup_def`), when a set of real numbers is not bounded above, its supremum defaults to $0$. On paper, one would simply observe that EF1 approximation factors are bounded above by $1$, but the formal proof handles the unbounded case via this default junk value.
- The nonemptiness of the set of round-robin sequence factors is witnessed by the empty sequence of length $0$ on $n = 2$ agents (`round_robin_sequence 2 0`).
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.
lemma recursively_balanced_alpha_le_round_robin_universal_alpha_zero_is_guaranteed (n : ℕ) (seq : List (Fin n)) : is_guaranteed_sequence_ef1_factor n seq 0 := by intro w hw rank hpne i j hij hAj rcases hAj with ⟨g, hg⟩ refine ⟨g, hg, ?_⟩ dsimp [SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation] rw [zero_mul] exact Finset.sum_nonneg fun x _ => hw i xlemma recursively_balanced_alpha_le_round_robin_universal_alpha_zero_le_alpha (n : ℕ) (seq : List (Fin n)) : 0 ≤ picking_sequence_alpha n seq := by dsimp [picking_sequence_alpha] by_cases h : BddAbove {α | is_guaranteed_sequence_ef1_factor n seq α} · exact le_csSup h (recursively_balanced_alpha_le_round_robin_universal_alpha_zero_is_guaranteed n seq) · have h0 : sSup {α | is_guaranteed_sequence_ef1_factor n seq α} = 0 := by rw [Real.sSup_def] split_ifs with h' · exact False.elim (h h'.2) · rfl rw [h0]/-- The universal EF1 approximation factor for recursively balanced sequences is at most that of Round-Robin. -/theorem recursively_balanced_alpha_le_round_robin_universal_alpha : recursively_balanced_alpha ≤ round_robin_universal_alpha := by dsimp [recursively_balanced_alpha, round_robin_universal_alpha] apply csInf_le_csInf · use 0 rintro x ⟨n, seq, hseq, hn, rfl⟩ exact recursively_balanced_alpha_le_round_robin_universal_alpha_zero_le_alpha n seq · use picking_sequence_alpha 2 (round_robin_sequence 2 0) refine ⟨2, round_robin_sequence 2 0, ⟨inferInstance, rfl⟩, le_rfl, rfl⟩ · rintro y ⟨n, seq, ⟨inst, heq⟩, hn, rfl⟩ refine ⟨n, seq, ?_, hn, rfl⟩ rw [heq] exact round_robin_sequence_is_recursively_balanced n seq.length