probabilistic_serial_phase
def
One phase of the simultaneous-eating (probabilistic serial) procedure for n agents and n items. Agent i's ranking is the permutation pref i, with pref i k its k-th favourite item. Given remaining capacities r_j and consumed amounts X_ij, agent i eats item j in this phase iff r_j > 0 and j has the smallest rank (pref i)^{-1}(j) among items with positive remaining capacity. With c_j the number of agents eating j, the phase lasts t = min over items with c_j > 0 of r_j / c_j (t = 0 if no item is eaten); then r_j becomes r_j - t c_j and X_ij increases by t if agent i eats j.
Statement
noncomputable def probabilistic_serial_phase (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) : (Fin n → ℝ) × (Fin n → Fin n → ℝ)
- Source
- 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; one phase of the eating procedure, helper for probabilistic_serial_fractional_assignment
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 17
- 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_fractional_assignment_two_same_oneTwo agents who both rank item 1 first each get half of each item under probabilistic serial.
- 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_fractional_assignment_two_split_swapTwo agents whose first choices are item 1 (agent 0) and item 0 (agent 1) each get their first choice entirely under probabilistic serial.
- probabilistic_serial_phase_stateThe state of the probabilistic serial (simultaneous eating) procedure for n agents and n unit-capacity items with rankings pref after its…
- 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_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_assignment_two_splitTwo agents whose first choices are item 0 (agent 0) and item 1 (agent 1) each get their first choice entirely under probabilistic serial.
- probabilistic_serial_fractional_assignment_row_sumUnder probabilistic serial each agent consumes exactly one unit in total: the row sums of the probabilistic serial assignment are 1.
- 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_fractional_assignmentThe probabilistic serial rule for n agents and n unit-capacity items with strict rankings pref: starting from capacities 1 and nothing…
- probabilistic_serial_fractional_assignment_col_sumEvery item is fully eaten under probabilistic serial: the column sums of the probabilistic serial assignment are 1.
- probabilistic_serial_line_item_wait_exists_eq_zeroFor n >= 1 items, some item has waiting cost 0 in the probabilistic serial procedure: an item still unfinished at the start of the last…
- 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…
Lean source view module on GitHub
/-- One phase of probabilistic serial (simultaneous eating). `pref i k` is agent `i`'s `k`-th favourite item; the state `s` is (remaining capacity of each item, amount of each item eaten so far by each agent). Every agent eats her favourite item with positive remaining capacity, at unit speed, until the first such item runs out. -/ noncomputable def probabilistic_serial_phase (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (s : (Fin n → ℝ) × (Fin n → Fin n → ℝ)) : (Fin n → ℝ) × (Fin n → Fin n → ℝ) := open Classical in let eats : Fin n → Fin n → Prop := fun i j => 0 < s.1 j ∧ ∀ j', 0 < s.1 j' → (pref i).symm j ≤ (pref i).symm j' let cnt : Fin n → ℕ := fun j => (Finset.univ.filter (fun i => eats i j)).card let S := Finset.univ.filter (fun j => 0 < cnt j) let t : ℝ := if h : S.Nonempty then S.inf' h (fun j => s.1 j / cnt j) else 0 (fun j => s.1 j - t * cnt j, fun i j => s.2 i j + if eats i j then t else 0)