Probabilistic-serial procedure

Each item is represented as a loaf of bread (or other food). Initially, each agent goes to their favourite item and starts eating it. It is possible that several agents eat the same item at the same time.

Whenever an item is fully eaten, each of the agents who ate it goes to their favorite remaining item and starts eating it in the same way, until all items are consumed.

For each item, the fraction of that item eaten by each agent is recorded. These fractions are considered as probabilities. Based on these probabilities, a lottery is done. The type of lottery depends on the problem:

• If each agent is allowed to receive any number of items, then a separate lottery can be done for each item. Each item is given to one of the agents who ate a part of it, chosen at random according to the probability distribution for that item.
• If each agent should receive exactly one item, then there must be a single lottery that picks an assignment by some probability distribution on the set of deterministic assignments. To do this, the n-by-n matrix of probabilities should be decomposed into a convex combination of permutation matrices. This can be done by the Birkhoff algorithm. It is guaranteed to find a combination in which the number of permutation matrices is at most n²-2n+2.

An important parameter to PS is the eating speed of each agent. In the simplest case, when all agents have the same entitlements, it makes sense to let all agents eat in the same speed all the time. However, when agents have different entitlements, it is possible to give the more privileged agents a higher eating speed. Moreover, it is possible to let the eating speed change with time.

There are four agents and four items (denoted w,x,y,z). The preferences of the agents are:

• Alice and Bob prefer w to x to y to z.
• Chana and Dana prefer x to w to z to y.

The agents have equal rights so we apply PS with equal and uniform eating speed of 1 unit per minute.

Initially, Alice and Bob go to w and Chana and Dana go to x. Each pair eats their item simultaneously. After 1/2 minute, Alice and Bob each have 1/2 of w, while Chana and Dana each have 1/2 of x.

Then, Alice and Bob go to y (their favourite remaining item) and Chana and Dana go to z (their favourite remaining item). After 1/2 minute, Alice and Bob each have 1/2 of y and Chana and Dana each have 1/2 of z.

The matrix of probabilities is now:

Alice: 1/2 0 1/2 0

Bob : 1/2 0 1/2 0

Chana: 0 1/2 0 1/2

Dana: 0 1/2 0 1/2

Based on the eaten fractions, item w is given to either Alice or Bob with equal probability and the same is done with item y; item x is given to either Chana or Dana with equal probability and the same is done with item z. If it is required to give exactly 1 item per agent, then the matrix of probabilities is decomposed into the following two assignment matrices:

1 0 0 0 ||| 0 0 1 0

0 0 1 0 ||| 1 0 0 0

0 1 0 0 ||| 0 0 0 1

0 0 0 1 ||| 0 1 0 0

One of these assignments is selected at random with a probability of 1/2.

As explained above, the allocation determined by PS is fair only ex-ante but not ex-post. Moreover, when each agent may get any number of items, the ex-post unfairness might be arbitrarily bad: it is possible that one agent will get all the items while other agents get none.

The PS-lottery algorithm is an improvement of PS in which the lottery is done only among deterministic allocations that are envy-free-except-one-item (EF1). This guaratees that the ex-post allocation is "not too unfair". Moreover, the EF1 guarantee holds for any cardinal utilities consistent with the ordinal ranking, i.e., it is stochastic-dominance EF1 (sd-EF1).[2]

The algorithm uses as subroutines both the PS algorithm and the Birkhoff algorithm.

• Random priority - an alternative mechanism with different properties.