← Gallery

About

The Probabilistic Serial (PS) mechanism uses an elegant "eating" metaphor: each school has 1 unit of probability mass, and students simultaneously eat their top remaining choice at rate 1. The result is a fractional (lottery) assignment that is ordinally efficient and envy-free.

The Eating Algorithm 
Time runs continuously from 0 to 1:
- Each school starts with mass 1
- All students simultaneously "eat"
  their most-preferred available
  school at rate 1
- When a school's mass reaches 0,
  it is depleted
- Students eating that school move
  to their next preference
- Continue until time = 1

Result: student i gets fraction
p(i,j) of school j = amount eaten.

Controls

Preferences

s1: A > B > C > D
s2: A > C > B > D
s3: B > A > C > D
s4: B > C > A > D

Properties

✓ Ordinally efficient (no stochastic dominance improvement)
✓ Envy-free (symmetric treatment)
✗ Not strategy-proof (can sometimes gain by misreporting)
Bogomolnaia & Moulin (2001) showed no mechanism can be both ordinally efficient and strategy-proof. PS vs RSD is a fundamental trade-off: PS gives better expected welfare but can be manipulated; RSD is manipulation-proof but less efficient.
Bogomolnaia, A. and Moulin, H. (2001). "A New Solution to the Random Assignment Problem." Journal of Economic Theory, 100(2): 295-328.

Event Log

Probabilistic Serial Mechanism

Bogomolnaia & Moulin (2001) — The "Eating Algorithm" for Fair Random Assignment

School Probability Mass (Food Portions)

Time: 0.000

Students (Eaters)