Simultaneous eating algorithm
The probabilistic serial (PS) procedure is a procedure for fair random assignment. It yields a randomized allocation of indivisible items among several agents that is both envy-free and Pareto efficient. It was suggested by Hervé Moulin and Anna Bogomolnaia.[1]
Description
For each item, we create 1 loaf of bread (or other food). Initially, each agent goes to the loaf of his favorite item and starts eating it. It is possible that several agents eat the same loaf at the same time.
Whenever a loaf is fully eaten, each of the agents who ate it goes to the loaf of his best remaining item and starts eating it in the same way, until all loaves are consumed.
We record, for each item, what fraction of that item was eaten by each agent. These fractions define a probability distribution; we draw one of the agents at random according to this distribution, and give him the item.
Example
See also
- Random priority - an alternative mechanism with different properties.
- ^ Bogomolnaia, Anna; Moulin, Hervé (2001). "A New Solution to the Random Assignment Problem". Journal of Economic Theory. 100 (2): 295. doi:10.1006/jeth.2000.2710.