picking_prefix_state
def
The state of a picking-sequence run after its first s turns: the bundle map together with the set of already allocated items, obtained by folding picking_turn over the first s entries of the sequence with each agent's bid as her ranking.
Statement
def picking_prefix_state {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) : (N → Finset G) × Finset G
- Source
- step towards round_robin_item_preserving_swaps_polynomial_convergence
- Verified
- 20 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 17
- picking_prefix_state_card_diff_step_of_neSuppose two runs of a picking sequence (differing only in agent i's ranking) have allocated sets at time s that differ in at most one…
- 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…
- 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_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…
- 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_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_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…
- 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…
- 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.
- 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…
- 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_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…
Lean source view module on GitHub
/-- Prefix state (bundles, allocated set) after s turns of a picking sequence. -/ def picking_prefix_state {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ} (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) : (N → Finset G) × Finset G := (seq.take s).foldl (fun st a => picking_turn (List.ofFn ⇑(rank a)) a st) (fun _ => ∅, ∅)