AFTD Auto-Formalizing Theoretical Domains

probabilistic_serial_line_cost

def

The cost of the probabilistic serial assignment X for agents at a and items at b on the real line: PS = sum over agents i and items j of X_ij |a_i - b_j|.

Statement

noncomputable def probabilistic_serial_line_cost {n : ℕ} (a b : Fin n → ℝ)
    (pref : Fin n → Equiv.Perm (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 (cost of a fractional matching)
Verified
05 Nov 2026
Axioms
none listed
Built on 1
Used by 15

Read back from the Lean

The definition probabilistic_serial_line_cost takes an implicit natural number n, two functions a, b : Fin n → ℝ (representing the positions of n agents and n items on the real line, respectively), and a preference profile pref : Fin n → Equiv.Perm (Fin n) (where agent i ranks item j by (pref i).symm j, with smaller values preferred). It returns the real number: $$\sum_{i \in \text{Fin } n} \sum_{j \in \text{Fin } n} P(i, j) \cdot |a(i) - b(j)|$$ where $P(i, j)$ is the fractional assignment of item $j$ to agent $i$ obtained from the Probabilistic Serial mechanism after n phases.

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

/-- Expected cost on the line of the probabilistic serial assignment: `∑ i j, X i j * |a i - b j|`. -/
noncomputable def probabilistic_serial_line_cost {n : ℕ} (a b : Fin n → ℝ)
    (pref : Fin n → Equiv.Perm (Fin n)) : ℝ :=
  ∑ i, ∑ j, probabilistic_serial_fractional_assignment n pref i j * |a i - b j|
See it in the graphDiscuss this resultChallenge it