probabilistic_serial_line_cost
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
- probabilistic_serial_fractional_assignmentThe probabilistic serial rule for n agents and n unit-capacity items with strict rankings pref: starting from capacities 1 and nothing…
- Used by 15
- probabilistic_serial_line_three_agents_le_of_first_choices_12Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 1 first and item 2 second. For three agents…
- probabilistic_serial_line_three_agents_le_of_first_choices_20Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 2 first and item 0 second. For three agents…
- probabilistic_serial_line_distortion_ge_sharpSharpness half of OP-1158: for every n >= 2 and every real c < n there are n agents and n items at real positions with positive minimum…
- probabilistic_serial_equispaced_distortion_two_agents_attainedFor n = 2 with equispaced items at 0 and 1, agents at 0 and 1/2 with ties broken toward the smaller-index item attain the harmonic…
- probabilistic_serial_equispaced_distortion_le_two_agentsFor two agents at real locations and two equispaced items at 0 and 1, the probabilistic serial cost under any distance preference profile…
- probabilistic_serial_line_distortion_le_of_item_wait_leIf on an instance (agents at a, items at b, distance rankings pref) every item's waiting cost is at most OPT, then the probabilistic…
- probabilistic_serial_line_three_agents_le_of_first_choices_21Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 2 first and item 1 second. For three agents…
- probabilistic_serial_equispaced_distortion_le_three_agentsFor three agents at real locations and three equispaced items at 0, 1, and 2, the probabilistic serial cost under any distance preference…
- probabilistic_serial_line_distortion_le_two_agentsCase n = 2 of OP-1158: for two agents at real positions a_0, a_1 and two items at real positions b_0, b_1, with each agent ranking the…
- probabilistic_serial_line_three_agents_le_of_first_choices_10Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 1 first and item 0 second. For three agents…
- probabilistic_serial_line_cost_le_add_item_waitFor n agents at real positions a and n items at real positions b, each agent ranking the items by distance (ties broken arbitrarily), the…
- probabilistic_serial_line_cost_two_sameSanity check: two agents at 0, items at 0 and 1, both ranking item 0 first: the probabilistic serial cost is 1.
- probabilistic_serial_line_three_agents_le_of_first_choices_01Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 0 first and item 1 second. For three agents…
- probabilistic_serial_line_three_agents_le_of_first_choices_02Lemma for the case n = 3 of OP-1158, for the 36 ranking profiles in which agent 0 ranks item 0 first and item 2 second. For three agents…
- probabilistic_serial_line_distortion_le_three_agentsCase n = 3 of OP-1158: for three agents at real positions a_0, a_1, a_2 and three items at real positions b_0, b_1, b_2, with each agent…
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|