picking_sequence_outcome
def
The allocation returned by the picking-sequence mechanism PS_π: agents act in the order seq, and at each turn the active agent takes its highest-ranked remaining good, where rank i k is the good agent i reports in position k (position 0 is its top good).
Statement
def picking_sequence_outcome {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) : N → Finset G
- 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
- Built on 1
- picking_turnOne turn of a picking-sequence mechanism: the active agent i receives the first good of its reported ranking l (best first) that is not…
- Used by 32
- 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…
- irr_step_neAn iterated best-response step always changes the bid profile, since the moving agent strictly improves.
- irr_stepOne step of iterated picking sequences restricted to admissible bids adm: some agent i that has a strictly profitable admissible…
- picking_sequence_outcome_update_mem_of_first_freeIn a picking-sequence run, if agent i's first turn is turn t and the good g that i's new report r ranks first is still unallocated after…
- 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…
- irr_step_changed_agent_strictEvery irr_step is carried out by a single agent i: her new bid b' i is an admissible bid for her at b, nothing but her own bid changes (b'…
- picking_prefix_two_named_first_dev_bundleIn a picking sequence with at most as many turns as goods, suppose agent i acts at turns t1 < t2 and nowhere in between, x is unallocated…
- picking_sequence_outcome_update_memWhatever ranking r agent i reports, its bundle is the bundle of agent i in one of the runs of picking_runs_any: a finite set of candidate…
- 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}…
- is_item_preserving_swap_bidBid r of agent i is obtained from b i by an item-preserving swap: a swap of the goods in positions k < l that demotes the good g = b i k,…
- 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…
- picking_sequence_outcome_pairwise_disjointDistinct agents never receive the same good under a picking sequence: the bundles are pairwise disjoint.
- 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…
- 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…
- 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…
- 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_sequence_alpha_nil_eq_zeroFor the empty picking sequence every EF1 factor alpha is guaranteed (all bundles are empty), so picking_sequence_alpha, defined as a real…
- 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…
- 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…
- independent_rank_trajectories_single_goodFor n ≥ 2 agents and m = 1 good, under any length-1 picking sequence, the agents' received rank vectors are mutually independent under…
- 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…
- 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_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_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_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…
Lean source view module on GitHub
/-- The allocation of the picking-sequence mechanism `PS_π`: agents act in the order `seq`, and at each turn the active agent takes its highest-ranked available good; `rank i k` is the good agent `i` reports in position `k` (position `0` best). -/ def picking_sequence_outcome {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) : N → Finset G := (seq.foldl (fun st i => picking_turn (List.ofFn (rank i)) i st) (fun _ => ∅, ∅)).1