probabilistic_serial_line_cost_two_same
Sanity check: two agents at 0, items at 0 and 1, both ranking item 0 first: the probabilistic serial cost is 1.
Statement
theorem probabilistic_serial_line_cost_two_same (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 0) (h1 : pref 1 0 = 0) : probabilistic_serial_line_cost (fun _ => 0) ![0, 1] pref = 1
- Source
- sanity lemma for probabilistic_serial_line_cost (OP-1158)
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- probabilistic_serial_line_costThe 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…
- probabilistic_serial_fractional_assignment_two_sameSanity check: when both of two agents rank item 0 first, probabilistic serial gives each agent half of each item.
- 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…
The proof, explained
To verify that the probabilistic serial cost is 1 when two agents at position 0 share the top preference for item 0 on a line with items at 0 and 1, we unfold the definition of the line cost into a double sum over agents and items. Using the fact that both agents receive an equal share of 1/2 of each item under identical top preferences, expanding the sum over the two agents and two items reduces the total cost to 1/2 + 1/2 = 1.
The cost is expressed as the double sum ∑ i, ∑ j, X_{ij} |a(i) - b(j)| of fractional assignments multiplied by distances.
Unfolding the definition of probabilistic_serial_line_cost expands the goal into the double sum over agents i and items j of the fractional assignment of item j to agent i times the distance |a(i) - b(j)|, where agent locations are given by the constant function 0 and item locations by the vector ![0, 1].
unfold probabilistic_serial_line_costThe double sum evaluates to 1.
Because both agents rank item 0 first, lemma probabilistic_serial_fractional_assignment_two_same states that every agent-item assignment probability is 1/2. Rewriting with Fin.sum_univ_two expands the finite sums over the two agents and two items into explicit arithmetic: each agent incurs cost (1/2) * |0 - 0| + (1/2) * |0 - 1| = 1/2, and summing over both agents yields 1/2 + 1/2 = 1. The simplifier computes this arithmetic and closes the goal.
uses
probabilistic_serial_fractional_assignment_two_same,Fin.sum_univ_twosimp [probabilistic_serial_fractional_assignment_two_same pref h0 h1, Fin.sum_univ_two]
probabilistic_serial_fractional_assignment_two_same- When two agents both have item 0 as their top choice, the probabilistic serial mechanism assigns each agent a fraction of 1/2 of every item.
Fin.sum_univ_two- The sum of a function over the two-element type Fin 2 is the sum of its values at 0 and 1: ∑ i, f i = f 0 + f 1.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem probabilistic_serial_line_cost_two_same (pref : Fin 2 → Equiv.Perm (Fin 2)) (h0 : pref 0 0 = 0) (h1 : pref 1 0 = 0) : probabilistic_serial_line_cost (fun _ => 0) ![0, 1] pref = 1 := by unfold probabilistic_serial_line_cost simp [probabilistic_serial_fractional_assignment_two_same pref h0 h1, Fin.sum_univ_two]