probabilistic_serial_fractional_assignment
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
- 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_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_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_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_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_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_fractional_assignment_col_sumEvery item is fully eaten under probabilistic serial: the column sums of the probabilistic serial assignment are 1.
- 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_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…
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