draft_alloc
Given a preference profile assigning each agent a linear order on objects, a list of agents representing the turn order, and a finite set of remaining objects, draft_alloc recursively computes the allocation assigning each agent a finite set of objects by having the designated picker at each step choose her maximal remaining object.
Statement
def draft_alloc {Agent Object : Type*} [DecidableEq Agent] [DecidableEq Object] (succ : Agent → LinearOrder Object) (l : List Agent) (rem : Finset Object) : Agent → Finset Object
- Defined in
- arXiv:2611.09685 Section 4.1
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Used by 3
- draft_ruleGiven types Agent and Object with decidable equality and finite Object, an implicit natural number T, a picking sequence s : Fin T ->…
- draft_pick_listThe list of objects chosen by the draft, turn by turn: at each turn the picker takes her favourite (= greatest, for the order attached to…
- two_agent_welfare_regret_nonnegFor any number of goods m : ℕ, any drafting schedule s : Fin m → Fin 2 of length m, and any nonnegative valuation profile v : Fin 2 → Fin…
Read back from the Lean
draft_alloc defines a function that, given types Agent and Object with decidable equality, a family of linear orders succ : Agent → LinearOrder Object (representing each agent's preferences over objects), a list l : List Agent (representing the sequence of drafting turns), and a finite set rem : Finset Object of remaining available objects, produces an allocation function Agent → Finset Object defined by structural recursion on l:
- If l is empty ([]), every agent is allocated the empty set ∅ (fun _ => ∅).
- If l is a :: rest:
- If rem is nonempty, let pick be the maximum element of rem according to the linear order succ a. The draft proceeds recursively on rest with the remaining objects rem.erase pick, yielding an allocation rest_alloc. The returned allocation updates rest_alloc by assigning agent a the set insert pick (rest_alloc a), while leaving all other agents' allocations unchanged.
- If rem is empty, every agent is allocated the empty set ∅ (fun _ => ∅).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Sequential draft allocation by recursive greedy choice from remaining objects. -/ def draft_alloc {Agent Object : Type*} [DecidableEq Agent] [DecidableEq Object] (succ : Agent → LinearOrder Object) (l : List Agent) (rem : Finset Object) : Agent → Finset Object := match l with | [] => fun _ => ∅ | a :: rest => if h : rem.Nonempty then let pick := @Finset.max' Object (succ a) rem h let rest_alloc := draft_alloc succ rest (rem.erase pick) Function.update rest_alloc a (insert pick (rest_alloc a)) else fun _ => ∅