AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_fractional_assignment

def

The probabilistic serial rule for n agents and n unit-capacity items with strict rankings pref: starting from capacities 1 and nothing eaten, run n phases of the simultaneous-eating procedure (each agent eats at unit speed its favourite item with positive remaining capacity; a phase ends when the first eaten item runs out). The result X_ij is the fraction of item j consumed by agent i. Each phase exhausts an item, so n phases consume all items.

Statement

noncomputable def probabilistic_serial_fractional_assignment (n : ℕ)
    (pref : Fin n → Equiv.Perm (Fin n)) : Fin n → Fin n → ℝ
Defined in
arXiv:2611.05777 (Sublinear Metric Distortion for Matching), Sec. 1 and Sec. 6: one-sided matching of n agents to n items with ordinal rankings by distance; the probabilistic serial rule (the rule as described there: agents simultaneously eat their favourite available item at the same constant rate); written as an explicit n-phase simulation
Verified
05 Nov 2026
Axioms
none listed
Built on 1
  • probabilistic_serial_phaseOne phase of the simultaneous-eating (probabilistic serial) procedure for n agents and n items. Agent i's ranking is the permutation pref…
Used by 19

Read back from the Lean

probabilistic_serial_fractional_assignment n pref is a definition that takes a natural number n and a profile of preferences pref : Fin n → Equiv.Perm (Fin n) (assigning to each agent i : Fin n a permutation of Fin n), and outputs a fractional assignment matrix of type Fin n → Fin n → ℝ (giving the fraction of item j assigned to agent i). It is computed as the second component (the allocation matrix) of the state obtained by iterating probabilistic_serial_phase n pref $n$ times, starting from the initial state where each item has remaining capacity $1$ (fun _ => 1) and every agent-item pair has initial allocation $0$ (fun _ _ => 0).

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

/-- The probabilistic serial fractional assignment: `X i j` is the amount of unit-capacity item `j` eaten by agent `i` when all agents eat at unit speed their favourite remaining item. Run as `n` phases of `probabilistic_serial_phase`, starting with all capacities 1; each phase exhausts at least one item, so after `n` phases every item is consumed. -/
noncomputable def probabilistic_serial_fractional_assignment (n : ℕ)
    (pref : Fin n → Equiv.Perm (Fin n)) : Fin n → Fin n → ℝ :=
  ((probabilistic_serial_phase n pref)^[n] (fun _ => 1, fun _ _ => 0)).2
See it in the graphDiscuss this resultChallenge it