A simultaneous eating algorithm(SE) [1] 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). [1]
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). [2]
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:
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).
There are four agents and four items (denoted w, x, y, z). The preferences of the agents are:
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 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 fractions 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.
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.
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. [1] : Thm.1
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:
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.
PS satisfies another fairness property, in addition to envy-freeness. Given any fractional allocation, for any agent i and positive integer k, define t(i,k) as the total fraction that agent i receives from his k topmost indifference classes. This t is a vector of size at most n*m, where n is the number of agents and m is the number of items. An ordinally-egalitarian allocation is one that maximizes the vector t in the leximin order. PS is the unique rule that returns an ordinally-egalitarian allocation. [3]
SE 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:
Note that the random priority rule, which solves the same problem as PS, is truthful.
The SE algorithm has been extended in many ways.
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 [14] show:
Aziz [15] shows:
Babaioff, Ezra and Feige [16] show:
Hoefer, Schmalhofer and Varricchio [17] extend the notion of "Best-of-Both-Worlds" lottery to agents with different entitlements.
The page on fair random assignment compares PS to other procedures for solving the same problem, such as the random priority rule.
In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single pre-determined person's preferences, without consideration of the other voters. Dictatorship by itself is not considered a good mechanism in practice, but it is theoretically important: by Arrow's impossibility theorem, when there are at least three alternatives, dictatorship is the only ranked voting electoral system that satisfies unrestricted domain, Pareto efficiency, and independence of irrelevant alternatives. Similarly, by Gibbard's theorem, when there are at least three alternatives, dictatorship is the only strategyproof rule.
Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:
Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.
Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.
Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.
The envy-graph procedure is a procedure for fair item allocation. It can be used by several people who want to divide among them several discrete items, such as heirlooms, sweets, or seats in a class.
Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.
Fair random assignment is a kind of a fair division problem.
Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.
Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the 1-out-of-n maximin-share is the maximum value that can be gained by partitioning the items into parts and taking the part with the minimum value. An allocation of items among agents with different valuations is called MMS-fair if each agent gets a bundle that is at least as good as his/her 1-out-of-n maximin-share. MMS fairness is a relaxation of the criterion of proportionality - each agent gets a bundle that is at least as good as the equal split ( of every resource). Proportionality can be guaranteed when the items are divisible, but not when they are indivisible, even if all agents have identical valuations. In contrast, MMS fairness can always be guaranteed to identical agents, so it is a natural alternative to proportionality even when the agents are different.
Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as the bundle of any other agent, when at most one item is removed from the other bundle. In sports, the round-robin procedure is called a draft.
When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.
Birkhoff's algorithm is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations.
Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.
Proportional item allocation is a fair item allocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/n of the entire allocation, where n is the number of agents.
In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called discrete if each item is wholly allocated to a single agent; it is called fractional if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete or fractional allocation. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.
Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:
In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.
Fair division among groups is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:
Ordinal Pareto efficiency refers to several adaptations of the concept of Pareto-efficiency to settings in which the agents only express ordinal utilities over items, but not over bundles. That is, agents rank the items from best to worst, but they do not rank the subsets of items. In particular, they do not specify a numeric value for each item. This may cause an ambiguity regarding whether certain allocations are Pareto-efficient or not. As an example, consider an economy with three items and two agents, with the following rankings: