round_robin_sequence
def
The Round-Robin picking sequence (1, 2, ..., n, 1, 2, ...) of length m, with agents numbered 0, ..., n-1.
Statement
def round_robin_sequence (n m : ℕ) [NeZero n] : List (Fin n)- Defined in
- arXiv:2610.23040 (On the Convergence of Iterated Round Robin), Sec. 2; also arXiv:2610.23686 Sec. 2
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Used by 30
- iterated_round_robin_item_preserving_swaps_zero_of_card_leWhen the number of goods m is at most the number of agents n, for any initial preference profile pref : Fin n → Fin m ≃ Fin m and…
- round_robin_sequence_count_eqThe number of times agent a appears in the Round-Robin sequence of n agents and m goods is (m + (n - 1 - a)) / n.
- round_robin_three_agents_pne_not_alpha_ef1_of_three_quarters_ltWith three agents and eight goods, there is an instance with nonnegative additive valuations and a pure Nash equilibrium of Round-Robin…
- is_guaranteed_round_robin_ef1_factorA factor α is guaranteed for n agents under Round-Robin if for every number of goods m, every nonnegative additive valuation profile w,…
- picking_sequence_outcome_round_robin_two_agents_four_itemsExample 3.8 of arXiv:2610.23040: with two agents reporting a > b > c > d and b > c > d > a, Round-Robin gives {a, c} to agent 1 and {b, d}…
- round_robin_u_truthIn the alternating Round-Robin picking sequence ABAB...AB of m goods, agent A's truthful Borda utility U_truth when both agents A and B…
- round_robin_runs_coincide_bundle_eqIf two Round-Robin executions have the same set of allocated items at each turn s <= m, then both executions produce identical final…
- round_robin_borda_manipulation_gain_nonnegFor every number of goods m and all rankings rA and rB, the real-valued normalized manipulation gain round_robin_borda_manipulation_gain m…
- picking_phi_entry_leFor the Round-Robin sequence of n agents and m goods, the 0-based rank phi_s of the item selected at turn s is at most s (the paper's 1 <=…
- round_robin_pne_ef1_pair_of_count_le_twoIn a pure Nash equilibrium of Round-Robin (nonnegative additive valuations), every agent i is EF1 towards every other agent j that appears…
- round_robin_two_mul_add_one_deviation_certificateRound-Robin with n agents and 2n+1 goods, any reports, agent i ≠ 0: for some good g of agent 0's bundle B_0 (its first pick a1), either…
- round_robin_three_agents_seven_goods_pne_ef1With three agents and seven goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1; so the eight-good…
- round_robin_sequence_getElem?_eqThe t-th turn (for t < m) of the Round-Robin sequence of n agents is agent t mod n.
- 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_pne_ef1_of_card_le_two_mulWith n agents and at most 2n goods (every agent picks at most twice), every pure Nash equilibrium of Round-Robin, for nonnegative additive…
- 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…
- round_robin_pne_envy_zero_ef1_of_deviation_certificateIf the deviation certificate of round_robin_two_mul_add_one_deviation_certificate holds for agent i ≠ 0, then at a pure Nash equilibrium…
- round_robin_phi_vectorThe potential of arXiv:2610.23040 (Thm 3.13) for Round Robin with n agents and m goods: the vector Phi(r) = (phi_0(r), ..., phi_{m-1}(r))…
- recursively_balanced_alpha_le_round_robin_universal_alphaThe universal EF1 approximation factor for recursively balanced sequences recursively_balanced_alpha is at most the universal factor for…
- round_robin_sequence_three_eightThe Round-Robin sequence for 3 agents and 8 goods is (1,2,3,1,2,3,1,2).
- round_robin_two_mul_add_one_outcome_structureRound-Robin with n agents and 2n+1 goods, any reports: there are goods a2, a3 (agent 0's picks at turns n and 2n) and b1, b2 (agent i's…
- round_robin_two_mul_add_one_cover_pairsRound-Robin with n agents and 2n+1 goods, agent i ≠ 0: let a1 be agent 0's top-ranked good, a2 and a3 the goods it picks at turns n and…
- round_robin_pne_ef1_of_card_le_two_mul_add_oneWith n agents and at most 2n + 1 goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1. For three…
- round_robin_divergence_turn_actorIf only agent i deviates and the executions have identical allocated sets up to turn t but diverge at turn t + 1, then the agent acting at…
- round_robin_pne_not_ef1_three_agents_eight_goodsThere is an instance with 3 agents, 8 goods and strictly positive additive valuations, and a pure Nash equilibrium of the Round-Robin…
- round_robin_two_mul_add_one_window_traceRound-Robin with n agents and 2n+1 goods: change only agent i's report to r. Then at every time s between i's first turn and i's second…
- round_robin_u_bestIn the alternating Round-Robin picking sequence ABAB...AB of m goods, agent A's best-response Borda utility U_best is the maximum of A's…
- round_robin_pne_envy_zero_ef1_of_two_mul_add_oneWith n agents and 2n + 1 goods, in every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) every agent i ≠ 0 is EF1…
- round_robin_sequence_count_le_two_of_ne_zeroIn the Round-Robin sequence of n agents and 2n + 1 goods, every agent other than agent 0 picks at most twice.
- round_robin_sequence_is_recursively_balancedEvery Round-Robin picking sequence of length m for n agents is recursively balanced.
Lean source view module on GitHub
/-- The Round-Robin picking sequence `(0, 1, ..., n-1, 0, 1, ...)` of length `m`. -/ def round_robin_sequence (n m : ℕ) [NeZero n] : List (Fin n) := List.ofFn (fun t : Fin m => (⟨t.val % n, Nat.mod_lt _ (Nat.pos_of_neZero n)⟩ : Fin n))