picking_turn
def
One turn of a picking-sequence mechanism: the active agent i receives the first good of its reported ranking l (best first) that is not yet allocated; the state is the partial allocation together with the set of allocated goods.
Statement
def picking_turn {N G : Type*} [DecidableEq N] [DecidableEq G] (l : List G) (i : N) (st : (N → Finset G) × Finset G) : (N → Finset G) × 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
- Used by 28
- 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…
- 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…
- picking_prefix_state_succ_stepTurn s of a picking sequence with s < length seq and s < m: if the active agent is a, there is a good p, not allocated after s turns, such…
- picking_prefix_state_update_of_not_mem_takeChanging agent i's ranking does not change the state of a picking sequence after the first t turns if agent i does not pick in those turns.
- picking_prefix_state_eq_of_agreeIf two bid profiles assign the same ranking to every agent that appears among the first s entries of the sequence, then the states of the…
- foldl_picking_turn_alloc_subset_of_prefixFolding the picking turn over a prefix of a list of bidders only allocates fewer goods: if L1 is a prefix of L2, the allocated set after…
- 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…
- foldl_mem_picking_runs_anyRunning the picking sequence with an arbitrary list for agent i ends in one of the states of picking_runs_any.
- picking_phi_entryThe coordinate phi_s of the potential of arXiv:2610.23040 (proof of Thm 3.13): at turn s the acting agent takes the highest-ranked item…
- picking_sequence_outcome_pairwise_disjointDistinct agents never receive the same good under a picking sequence: the bundles are pairwise disjoint.
- picking_turn_anyAll states a turn of agent i can lead to, whatever its ranking: the state unchanged, or any not yet allocated good of the list U added to…
- picking_turn_alloc_subsetOne turn never un-allocates a good: the set of goods already allocated before a picking turn is contained in the set of allocated goods…
- 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…
- picking_prefix_stateThe state of a picking-sequence run after its first s turns: the bundle map together with the set of already allocated items, obtained by…
- 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…
- picking_prefix_state_alloc_card_eqAfter s turns of a picking sequence with at most as many turns as goods, exactly min s (length seq) goods have been allocated (in…
- 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_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…
- picking_prefix_state_allocated_card_leAfter s turns of a picking sequence at most s items have been allocated: every picking_turn inserts at most one item into the allocated set.
- 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_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…
- picking_prefix_state_alloc_monoThe set of allocated goods is monotone in the number of turns: if s <= t then the goods allocated after s turns are allocated after t turns.
- 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…
- picking_runs_anyThe final states of a picking-sequence run in which agent i may take any available good at its turns while every other agent follows its…
- 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…
- picking_turn_mem_anyWhatever ranking agent i reports, its turn leads to one of the states of picking_turn_any (when U lists every good).
- 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…
Lean source view module on GitHub
/-- One turn of a picking-sequence mechanism: the active agent `i` receives the first good of its reported ranking `l` (best first) not yet allocated. The state is the partial allocation and the set of goods already allocated. -/ def picking_turn {N G : Type*} [DecidableEq N] [DecidableEq G] (l : List G) (i : N) (st : (N → Finset G) × Finset G) : (N → Finset G) × Finset G := match l.find? (fun g => decide (g ∉ st.2)) with | some g => (Function.update st.1 i (insert g (st.1 i)), insert g st.2) | none => st