probabilistic_serial_phase_state
def
The state of the probabilistic serial (simultaneous eating) procedure for n agents and n unit-capacity items with rankings pref after its first k phases, started from full capacities and nothing eaten: the pair (remaining capacity of each item, amount of each item eaten so far by each agent). After n phases it is the probabilistic serial assignment.
Statement
noncomputable def probabilistic_serial_phase_state (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) : (Fin n → ℝ) × (Fin n → Fin n → ℝ)
- Source
- Helper for the item-waiting-time reduction of OP-1158 (probabilistic serial on the line, PS <= n*OPT); reduction found 2026-11-07 for IN-608, experiments 17916, 17917
- Verified
- 07 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 6
- 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_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_phase_lengthThe duration of phase k of the probabilistic serial procedure (k = 0, 1, ...): the total remaining item capacity before the phase minus…
- 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_item_waitThe waiting cost of item j in the probabilistic serial procedure, items at real positions b: the integral, over the times t in [0,1] after…
Lean source view module on GitHub
noncomputable def probabilistic_serial_phase_state (n : ℕ) (pref : Fin n → Equiv.Perm (Fin n)) (k : ℕ) : (Fin n → ℝ) × (Fin n → Fin n → ℝ) := (probabilistic_serial_phase n pref)^[k] (fun _ => 1, fun _ _ => 0)