AFTD Auto-Formalizing Theoretical Domains

is_guaranteed_round_robin_ef1_factor

def

A factor α is guaranteed for n agents under Round-Robin if for every number of goods m, every nonnegative additive valuation profile w, and every pure Nash equilibrium rank under the Round-Robin sequence, the induced allocation is α-EF1.

Statement

def is_guaranteed_round_robin_ef1_factor (n : ℕ) [NeZero n] (α : ℝ) : Prop
Defined in
arXiv:2610.23686, Sec. 6
Verified
20 Oct 2026
Axioms
none listed
Built on 6
Used by 4

Read back from the Lean

Given a number of agents $n \in \mathbb{N}$ with $n \ne 0$ and a factor $\alpha \in \mathbb{R}$, this definition asserts that for every number of items $m \in \mathbb{N}$ and every non-negative additive weight matrix $w : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ (satisfying $0 \le w(i, g)$ for all $i$ and $g$): For every ranking profile $\text{rank} : \text{Fin } n \to (\text{Fin } m \simeq \text{Fin } m)$, if $\text{rank}$ is a pure Nash equilibrium (PNE) of the picking sequence game on the round-robin sequence of length $m$ (where at step $t \in \{0, \dots, m-1\}$, agent $t \bmod n$ selects their highest-ranked unpicked item) with respect to the additive valuation induced by $w$—meaning no agent $i$ can unilaterally deviate to another permutation $r$ of $\text{Fin } m$ to strictly increase the additive value of the bundle they receive—then the resulting allocation $A$ is $\alpha$-EF1: for every pair of distinct agents $i \ne j$, if $A(j)$ is non-empty, there exists a good $g \in A(j)$ such that $\alpha \cdot v_i(A(j) \setminus \{g\}) \le v_i(A(i))$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A factor α is guaranteed for n agents under Round-Robin if every pure Nash equilibrium of every n-agent additive instance induces an α-EF1 allocation. -/
def is_guaranteed_round_robin_ef1_factor (n : ℕ) [NeZero n] (α : ℝ) : Prop :=
  ∀ (m : ℕ) (w : Fin n → Fin m → ℝ),
    (∀ i g, 0 ≤ w i g) →
    ∀ (rank : Fin n → Fin m ≃ Fin m),
      is_picking_sequence_pne
        (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)
        (round_robin_sequence n m) rank →
      is_alpha_ef1 α
        (SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation ⟨w⟩)
        (picking_sequence_outcome (round_robin_sequence n m) rank)
See it in the graphDiscuss this resultChallenge it