A simultaneous eating algorithm (SE) is an algorithm for allocating divisible objects among agents with
ordinal preferences
In economics, an ordinal utility function is a function representing the preferences of an agent on an ordinal scale. Ordinal utility theory claims that it is only meaningful to ask which option is better than the other, but it is meaningless to as ...
.
"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
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 th ...
- 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
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 ...
(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
Hervé Moulin (born 1950 in Paris) is a French mathematician who is the Donald J. Robertson Chair of Economics at the Adam Smith Business School at the University of Glasgow. He is known for his research contributions in mathematical economics ...
and Anna Bogomolnaia
Anna Vladimirovna Bogomolnaia () is a Russian economist specializing in microeconomics and game theory. She is a professor in economics at the Adam Smith Business School of the University of Glasgow,, and was until 2022 chief research fellow of the ...
as a solution for the fair random assignment Fair random assignment (also called probabilistic one-sided matching) is a kind of a fair division problem.
In an ''assignment problem'' (also called '' house-allocation problem'' or '' one-sided matching''), there are ''m'' objects and they have t ...
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
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 ...
in expectation (ex-ante
The term (sometimes written or ) is a New Latin phrase meaning "before the event".
In economics, ''ex-ante'' or notional demand refers to the desire for goods and services that is not backed by the ability to pay for those goods and servic ...
) for all vectors of utility functions consistent with the agents' item rankings.
A variant of SE was applied also to cake-cutting Cake-cutting may refer to:
* Fair cake-cutting
Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possib ...
, 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
In convex geometry and Vector space, vector algebra, a convex combination is a linear combination of point (geometry), points (which can be vector (geometric), vectors, scalar (mathematics), scalars, or more generally points in an affine sp ...
of permutation matrices
In mathematics, particularly in Matrix (mathematics), matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column with all other entries 0. An permutation matrix can represent a permu ...
. This can be done by the Birkhoff algorithm Birkhoff's algorithm (also called Birkhoff-von-Neumann 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 s ...
. It is guaranteed to find a combination in which the number of permutation matrices is at most ''n''2-2''n''+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.
* Chana 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 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 th
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
In probability theory, the expected value (also called expectation, expectancy, expectation operator, mathematical expectation, mean, expectation value, or first Moment (mathematics), moment) is a generalization of the weighted average. Informa ...
of their utility from the outcomes.
Efficiency
SE with any vector of eating speeds satisfies an efficiency property called SD-efficiency
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 th ...
(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
In welfare economics, a Pareto improvement formalizes the idea of an outcome being "better in every possible way". A change is called a Pareto improvement if it leaves at least one person in society better off without leaving anyone else worse ...
.
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
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 ...
(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
The term (sometimes written or ) is a New Latin phrase meaning "before the event".
In economics, ''ex-ante'' or notional demand refers to the desire for goods and services that is not backed by the ability to pay for those goods and servic ...
: it is fair only before the lottery takes place. The algorithm is of course not ex-post
References
Notes
References
Further reading
*
*
External links
*
{{Latin phrases
E ...
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.
Strategy
SE is not a truthful mechanism
In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly- dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have privat ...
: 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:
* PS is truthful when agents compare bundles using the downward lexicographic relation.[
* 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.][.
Older technical report: https://arxiv.org/abs/1401.6523.]
*Best responses w.r.t. expected utility can cycle. However, a pure Nash equilibrium
In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...
exists for any number of agents and items. 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
In economics and finance, risk aversion is the tendency of people to prefer outcomes with low uncertainty to those outcomes with high uncertainty, even if the average outcome of the latter is equal to or higher in monetary value than the more c ...
and has no information about the other agents' strategies, his maximin strategy
In game theory, a simultaneous game or static game is a game where each player chooses their action without knowledge of the actions chosen by other players. Simultaneous games contrast with sequential games, which are played by the players taki ...
is to be truthful.[
*A manipulating agent can increase his utility by a factor of at most 3/2. This was first observed empirically on random instances, and then proved formally.
Note that the random priority rule, which solves the same problem as PS, is truthful.
]
Extensions
The SE algorithm has been extended in many ways.
* Katta and Sethuraman present ''Extended PS (EPS),'' which allows weak ordinal preferences (rankings with indifferences). The algorithm is based on repeatedly solving instances of parametric network flow.
* Bogomolnaia[ presented a simpler definition of the PS rule for weak preferences, based on the ]leximin order
In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division.
Definition
A vec ...
.
* Yilmaz allows both indifferences and endowments.
* Athanassoglout and Sethuraman present the ''controlled consuming (CC)'' rule, which allows indifferences and fractional endowments of any quantity.
* Budish, Che, Kojima and Milgrom present ''Generalized PS'', which allows multiple units per item, more items than agents, each agent can get several units, upper quotas, and bi-hierarchical constraints on the feasible allocations.
* Ashlagi, Saberi and Shameli present another ''Generalized PS'', which allows lower and upper quotas, and distributional constraints (constraints on the probability distribution and not only the final allocation).
* Aziz and Stursberg present ''Egalitarian Simultaneous Reservation (ESR)'', which allows not only fair item allocation but also general social choice
Social choice theory is a branch of welfare economics that extends the theory of rational choice to collective decision-making. Social choice studies the behavior of different mathematical procedures ( social welfare functions) used to combine i ...
problems, with possible indifferences.
* Aziz and Brandl present ''Vigilant Eating (VE)'', which allows even more general constraints.
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 oracle
A separation oracle (also called a cutting-plane oracle) is a concept in the mathematical theory of convex optimization. It is a method to describe a convex set that is given as an input to an optimization algorithm. Separation oracles are used as ...
s.
* A different algorithm, based on an ex-ante max-product allocation, which attains ex-ante group envy-freeness Group envy-freeness (also called: coalition fairness) is a criterion for fair division. A group-envy-free division is a division of a resource among several partners such that every group of partners feel that their allocated share is at least as go ...
(GEF; it implies both EF and PO), and ex-post PROP1+EF11. 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 Birkhoff's algorithm (also called Birkhoff-von-Neumann 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 s ...
. 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
In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly-dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private ...
, 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
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 n parts and taking the part with the m ...
(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''/(2''n''-1) truncated-proportional share ex-post.
Hoefer, Schmalhofer and Varricchio extend the notion of "Best-of-Both-Worlds" lottery to agents with different entitlements
An entitlement is a government program guaranteeing access to some benefit by members of a specific group and based on established rights or by legislation. A "right" is itself an entitlement associated with a moral or social principle, while an ...
.
See also
The page on fair random assignment Fair random assignment (also called probabilistic one-sided matching) is a kind of a fair division problem.
In an ''assignment problem'' (also called '' house-allocation problem'' or '' one-sided matching''), there are ''m'' objects and they have t ...
compares PS to other procedures for solving the same problem, such as the random priority rule.
References
{{reflist
Fair division protocols