is_guaranteed_round_robin_ef1_factor
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
- 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…
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i g. - round_robin_sequenceThe Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
- is_alpha_ef1For α in [0,1], an allocation is α-EF1 if for every pair of agents i ≠ j with A_j nonempty there is a good g in A_j with v_i(A_i) ≥ α ·…
- 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…
- SocialChoice.FairDivision.Indivisible.AdditiveValuationAn additive valuation is determined by per-item weights.
weight i gis the value agentiassigns to goodgindividually. The bundle…
- Used by 4
- not_is_guaranteed_round_robin_ef1_factor_three_fifteen_sixteenths15/16 is not a guaranteed EF1 factor for Round-Robin pure Nash equilibria with three agents: there exists an 8-good additive instance…
- round_robin_alphaThe best guaranteed EF1 factor α_RR(n) for n agents under Round-Robin is the supremum of factors α that are guaranteed for n agents under…
- not_is_guaranteed_round_robin_ef1_factor_three_of_three_quarters_ltFor three agents, no factor strictly greater than 3/4 is guaranteed for Round-Robin pure Nash equilibria.
- round_robin_alpha_three_eq_of_two_directionsIf 2/3 is a guaranteed EF1 factor for three agents and no factor above 2/3 is guaranteed, then the best guaranteed factor for three agents…
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)