AFTD Auto-Formalizing Theoretical Domains

recursively_balanced_alpha_le_round_robin_universal_alpha

theoremverifiedformalization

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

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.

  1. 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.

    lines 4–9

    uses zero_mul, Finset.sum_nonneg

      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 x
  2. 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.

    lines 14–16

    uses le_csSup, recursively_balanced_alpha_le_round_robin_universal_alpha_zero_is_guaranteed

      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)
  3. 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$.

    lines 17–22

    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]
  4. 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$.

    lines 27–28

    uses csInf_le_csInf

      dsimp [recursively_balanced_alpha, round_robin_universal_alpha]
      apply csInf_le_csInf
  5. 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`.

    lines 29–31

    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
  6. 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`).

    lines 32–33

    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⟩
  7. 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$.

    lines 34–37

    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.

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

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
See it in the graphDiscuss this resultChallenge it