AFTD Auto-Formalizing Theoretical Domains

picking_phi_entry

def

The 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 not yet allocated; phi_s is the 0-based position of that item in her bid (value 0 if turn s does not exist).

Statement

def picking_phi_entry {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ}
    (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) : ℕ
Source
step towards round_robin_item_preserving_swaps_polynomial_convergence
Verified
20 Oct 2026
Axioms
none listed
Built on 2
  • 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…
  • 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 2
  • 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_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))…

Lean source view module on GitHub

/-- Paper's potential coordinate phi_s: the 0-based rank, in the acting agent's bid, of the item she takes at turn s. -/
def picking_phi_entry {N G : Type*} [DecidableEq N] [DecidableEq G] {m : ℕ}
    (seq : List N) (rank : N → Fin m ≃ G) (s : ℕ) : ℕ := match seq[s]? with
  | none => 0
  | some a =>
      match (List.ofFn ⇑(rank a)).find? (fun g => decide (g ∉ (picking_prefix_state seq rank s).2)) with
      | none => 0
      | some g => ((rank a).symm g).val
See it in the graphDiscuss this resultChallenge it