Simultaneous eating algorithm

The Probabilistic Serial rule (PS), also called serial eating algorithm, is a rule for fair random assignment. It yields a randomized allocation of indivisible items among several agents that is ex-ante envy-free and Pareto efficient. It was developed by Hervé Moulin and Anna Bogomolnaia.

Description

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.

Examples

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.

Other examples can be generated at the MatchU.ai website.

Properties

PS rule several desirable properties. The description below assumes that all agents have risk-neutral preferences, that is, their utility from a lottery equals the expected value of their utility from the outcomes.

Fairness

PS satisfies a fairness property called ex-ante stochastic-dominace envy-freeness (sd-envy-free). Informally it means that each agent, considering the resulting probability matrix, weakly prefers his/her own row of probabilities to the row of any other agent. Formally, for every two agents i and j:

• Agent i has a weakly-higher probability to get his best item in row i than in row j;
• Agent i has a weakly-higher probability to get one of his two best items in row i than in row j;
• ...
• For any k ≥ 1, agent i has a weakly-higher probability to get one of his k best items in row i than in row j.

Note that sd-envy-freeness is guaranteed ex-ante: it is fair only before the lottery takes place. The algorithm is of course not ex-post fair: after the lottery takes place, the unlucky agents may envy the lucky ones. This is inevitable in allocation of indivisible objects.

Efficiency

PS satisfies an efficiency property called ex-ante stochastic-dominace Pareto efficiency (sd-efficiency, also called: ordinal efficiency). Informally it means that, considering the resulting probability matrix, there is no other matrix that all agents weakly-sd-prefer and at least one agent strictly-sd-prefers.

Here, the ex-ante notion of sd-efficiency is stronger than the ex-post notion: sd-efficiency implies that every allocation selected by the lottery is sd-Pareto-efficient.

Strategy

PS is not a truthful mechanism: an agent who knows that his most preferred item is not wanted by any other agent, can manipulate the algorithm by eating his second-most preferred item, knowing that his best item will remain intact. The following is known about strategic manipulation of PS:

• An agent can compute in polynomial time a best-response w.r.t. the downward lexicographic relation. When there are two agents, each agent can compute in polynomial time a best response w.r.t. expected utility. When the number of agents can vary, computing a best response w.r.t. EU is NP-hard.
• Best responses w.r.t. expected utility can cycle. However, a pure Nash equilibrium exists for any number of agents and houses. When there are two agents, there are linear-time algorithms to compute a preference-profile that is in Nash equilibrium w.r.t. the original preferences. In some empirical settings, PS is less prone to manipulation. When an agent is risk-averse and has no information about the other agents' strategies, his maximin strategy is to be truthful.

Note that the random priority rule, which solves the same problem as PS, is truthful.

Extensions

Budish, Che, Kojima and Milgrom extend PS to multi-unit settings, where there are more objects than agents, and each agent can get several units.

Choosing a decomposition

As mentioned above, any fractional assignment can be decomposed into a lottery of discrete assignments using the Birkhoff algorithm. However, the decomposition is not unique, and some decompositions may be better than others. Budish, Che, Kojima and Milgrom present a decomposition method that minimizes the variance in the utility experienced by the agents between the different matchings.

Demeulemeester, Dries Goossens, Hermans and Roel present a polynomial-time decomposition algorithm that maximizes the worst-case number of agents who get an object (for the case n<m). Their algorithm guarantees that the worst-case number of agents equals the expected number of agents rounded down, which is the best possible. They present another decomposition algorithm that maximizes the worst-case number of assigned agents while guaranteeing that all matchings in the decomposition be ex-post PE; the second algorithm can be used only for fractional assignments outputted by PS, but not those corresponding to RSD. For general fractional assignments, the latter problem is NP-hard.

Guaranteeing ex-post approximate fairness

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: theoretically it is possible that one agent will get all the items while other agents get none. Recently, several algorithms have been suggested, that guarantee both ex-ante fairness and ex-post approximate-fairness.

Freeman, Shah and Vaish show:

• The Recursive Probabilistic Serial (RecPS) algorithm, which returns a probability distribution over allocations that are all envy-free-except-one-item (EF1). The distribution is ex-ante EF, and the allocation is ex-post EF1. A naive version of this algorithm yields a distribution over a possibly exponential number of deterministic allocations, a support size polynomial in the number of agents and goods is sufficient, and thus the algorithm runs in polynomial time. The algorithm uses separation oracles.
• A different algorithm, based on an ex-ante max-product allocation, which attains ex-ante group envy-freeness (GEF; it implies both EF and PO), and ex-post PROP1+EF₁¹_. This is the only allocation rule that achieves all these properties. It cannot be decomposed into EF1 allocations.
• These combinations of properties are best possible: it is impossible to guarantee simultaneously ex-ante EF (even PROP) and ex-ante PO together with ex-post EF1; or ex-ante EF (even PROP) together with ex-post EF1 and fractional-PO.
• The RecPS can be modified to attain similar guarantees (ex-ante EF and ex-post EF1) for bads.

Aziz shows:

• The PS-lottery algorithm, in which the allocation is ex-ante sd-EF, and the lottery is done only among deterministic allocations that are sd-EF1, i.e., the EF and EF1 guarantees hold for any cardinal utilities consistent with the ordinal ranking. Moreover, the outcome is sd-PO both ex-ante and ex-post. The algorithm uses as subroutines both the PS algorithm and the Birkhoff algorithm. The ex-ante allocation is equivalent to the one returned by PS; this shows that the outcome of PS can be decomposed into EF1 allocations.
• With binary utilities, the PS-lottery algorithm is group-strategyproof, ex-ante PO, ex-ante EF and ex-post EF1.
• These combinations of properties are best possible: it is impossible to guarantee simultaneously ex-ante sd-EF, ex-post EF1 and ex-post PO; or ex-ante PO and ex-ante sd-EF.
• Checking whether a given random allocation can be implemented by a lottery over EF1 and PO allocations is NP-hard.

Babaioff, Ezra and Feige show:

• A polynomial-time algorithm for computing allocations that are ex-ante proportional, and ex-post both PROP1 and 1/2-fraction maximin-share (and also 1/2-fraction truncated-proportional share).
• These properties are nearly optimal - it is impossible to guarantee more than PROP ex-ante, and more than n/(2n-1) truncated-proportional share ex-post.

See also

The page on fair random assignment compares PS to other procedures for solving the same problem, such as the random priority rule.