A simultaneous eating algorithm (SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings). SE is parametrized by the "eating speed" of each agent. If all agents are given the same eating speed, then the SE allocation satisfies SD-envy-freeness - a strong ordinal variant of envy-freeness (it means that the allocation is envy-free for all vectors of additive utility functions consistent with the agents' item rankings). This particular variant of SE is called the Probabilistic Serial rule (PS). SE was developed by Hervé Moulin and Anna Bogomolnaia as a solution for the fair random assignment problem, where the fraction that each agent receives of each item is interpreted as a probability. If the integral of the eating speed of all agents is 1, then the sum of fractions assigned to each agent is 1, so the matrix of fractions can be decomposed into a lottery over assignments in which each agent gets exactly one item. With equal eating speeds, the lottery is envy-free in expectation (ex-ante) for all vectors of utility functions consistent with the agents' item rankings. A variant of SE was applied also to cake-cutting, where the allocation is deterministic (not random).
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. In the context of random assignments, 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 n2-2n+2. An important parameter to SE 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. The important thing is that the integral of the eating speed of each agent equals the total number of items that the agent should receive (in the assignment setting, each agent should get exactly 1 item, so the integral of all eating-speed functions should be 1).
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. Carol and Dana prefer x to w to z to y. The agents have equal rights so we apply SE with equal and uniform eating speed of 1 unit per minute. Initially, Alice and Bob go to w and Carol 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 Carol and Dana each have 1/2 of x. Then, Alice and Bob go to y (their favourite remaining item) and Carol and Dana go to z (their favourite remaining item). After 1/2 minute, Alice and Bob each have 1/2 of y and Carol and Dana each have 1/2 of z. The matrix of fractions is now:
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 Carol 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:
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 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.
Efficiency SE with any vector of eating speeds satisfies an efficiency property called 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. In the context of random assignments, SD-efficiency implies ex-post efficiency: every deterministic assignment selected by the lottery is Pareto-efficient. A fractional assignment is SD-efficient if-and-only-if it is the outcome of SE for some vector of eating-speed functions.
Fairness SE with equal eating speeds (called PS) satisfies a fairness property called ex-ante stochastic-dominance 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:
… excerpt ends here. Continue reading the full article.
