Envy-cycles procedure
The envy-cycles procedure is a procedure for fair item assignment. 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.
Ideally, we would like the allocation to be envy-free. i.e., to give each agent a bundle that he/she prefers over the bundles of all other agents. However, the items are discrete and cannot be cut, so an envy-free assignment might be impossible. The envy-cycles procedure aims to achieve the "next-best" option -- envy-freeness up to at most a single good : it finds an allocation in which the envy of every person towards every other person is bounded by the maximum marginal utility it derives from a single item. In other words, for every two people i and j, there exists an item such that, if that item is removed, i does not envy j.
The procedure was presented by Lipton and Markakis and Mossel and Saberi and it is also described in.
Assumptions
The envy-cycles procedure assumes that each person has a cardinal utility function on bundles of items. This utility function does not have to be additive. I.e, the items are not assumed to be independent goods.The agents do not have to actually report their cardinal utility: it is sufficient that they know how to rank bundles.
The procedure
- Order the items arbitrarily.
- While there are unassigned items:
- * Ensure that there is an unenvied agent - an agent that no other agent envies.
- * Give the next item to the unenvied agent.
The resulting allocation is not necessarily EF, but it is envy-free except one item. This is true not only in the final allocation but also in each intermediate allocation: since an item is always given to an unenvied agent, the envy of all other agents after that allocation is at most a single item.
Run-time analysis
Suppose there are m items. Each allocation of an item adds to the envy-graph at most n-1 edges. Hence, at most edges are added overall. Each cycle-removal removes at least two edges. Hence, we need to run the cycle-removal step at most times. Finding a cycle can be done in time using e.g. depth-first search. All in all, the run-time is.Examples
In these examples the preferences go from 1-3 where the higher the number the higher the preference. Also a, b and c are people while X, Y and Z are objects.1) With 3 people and 3 objects, every possible allocation will be a different result. This case happens when each of the three people have the same preferences.
X | Y | Z | |
a | 3 | 2 | 1 |
b | 3 | 2 | 1 |
c | 3 | 2 | 1 |
There are six different ways to allocate the objects:
In the beginning because no one has anything then all of them are unenvied agents and this is the same in all the cases. In case of a tie, we break ties between unenvied agents in lexicographic order.
- Let's start off by giving the X object to a. After that both b and c and unenvied agents. So now let's give the Y object to b. After that c is an unenvied agent. So now let's give the last object Z to c. Now c is jealous of b and a, b is jealous of a and a is not jealous of anybody and now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Y and c gets Z.
- Let's start off by giving the X object to a. After that both b and c and unenvied agents. So now let's give the Z object to b. After that c is an unenvied agent. So now let's give the last object Y to c. Now c is jealous of a, b is jealous of a and c and a is not jealous of anybody and now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Z and c gets Y.
- Let's start off by giving the Y object to a. After that both b and c and unenvied agents. So now let's give the X object to b. After that c is an unenvied agent. So now let's give the last object Z to c. Now c is jealous of a and b, a is jealous of b and b is not jealous of anybody and now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets Y, b gets X and c gets Z.
- Let's start off by giving the Y object to a. After that both b and c and unenvied agents. So now let's give the Z object to b. After that c is an unenvied agent. So now let's give the last object X to c. Now a is jealous of c, b is jealous of a and c and c is not jealous of anybody and now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets Y, b gets Z and c gets X.
- Let's start off by giving the Z object to a. After that both b and c and unenvied agents. So now let's give the X object to b. After that c is an unenvied agent. So now let's give the last object Y to c. Now c is jealous of b, a is jealous of b and c and b is not jealous of anybody and now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets Z, b gets X and c gets Y.
- Let's start off by giving the Z object to a. After that both b and c and unenvied agents. So now let's give the Y object to b. After that c is an unenvied agent. So now let's give the last object X to c. Now b is jealous of c, a is jealous of b and c and c is not jealous of anybody and now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets Z, b gets Y and c gets X.
X | Y | Z | |
a | 3 | 2 | 1 |
b | 1 | 3 | 2 |
c | 2 | 1 | 3 |
There are six different ways to allocate the objects:
In the beginning because no one has anything then all of them are unenvied agents and this is the same in all the cases. In case of a tie, we break ties between unenvied agents in lexicographic order.
- Let's start off by giving the X object to a. After that both b and c and unenvied agents. So now let's give the Y object to b. After that c is an unenvied agent. So now let's give the last object Z to c. Now a, b and c are all not jealous of anybody and now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Y and c gets Z.
- Let's start off by giving the X object to a. After that both b and c and unenvied agents. So now let's give the Z object to b. After that c is an unenvied agent. So now let's give the last object Y to c. Now c is jealous of b, b is jealous of c and a is not jealous of anybody. Since there is an envy cycle between b and c, they will switch objects and now b gets Y and c gets Z. And now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Y and c gets Z.
- Let's start off by giving the Y object to a. After that both b and c and unenvied agents. So now let's give the X object to b. After that c is an unenvied agent. So now let's give the last object Z to c. Now b is jealous of a, a is jealous of b and c is not jealous of anybody. Since there is an envy cycle between b and c, they will switch objects and now a gets X and b gets Y. And now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Y and c gets Z.
- Let's start off by giving the Y object to a. After that both b and c and unenvied agents. So now let's give the Z object to b. After that c is an unenvied agent. So now let's give the last object X to c. Now b is jealous of a, a is jealous of c and c is jealous of b. Since there is an envy cycle between a, b and c, they will rotate objects against the direction of jealousy and now a gets X, b gets Y and c gets Z. And now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Y and c gets Z.
- Let's start off by giving the Z object to a. After that both b and c and unenvied agents. So now let's give the X object to b. After that c is an unenvied agent. So now let's give the last object Y to c. Now b is jealous of a and c, a is jealous of b and c and c is jealous of b and a. Since there is an envy cycle between a, b and c they will rotate objects against the direction of jealousy and now a gets X and b gets Y and c gets Z. And now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Y and c gets Z.
- Let's start off by giving the Z object to a. After that both b and c and unenvied agents. So now let's give the Y object to b. After that c is an unenvied agent. So now let's give the last object X to c. Now c is jealous of a, a is jealous of c and b is not jealous of anybody.Since there is an envy cycle between a and c, they will switch objects and now a gets X and c gets Z. And now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Y and c gets Z.
X | Y | Z | |
a | 3 | 2 | 1 |
b | 3 | 1 | 2 |
c | 1 | 2 | 3 |
There are six different ways to allocate the objects:
In the beginning because no one has anything then all of them are unenvied agents and this is the same in all the cases. In case of a tie, we break ties between unenvied agents in lexicographic order.
- Let's start off by giving the X object to a. After that both b and c and unenvied agents. So now let's give the Y object to b. After that c is an unenvied agent. So now let's give the last object Z to c. Now a is not jealous of anybody, b is jealous of a and c and c is not jealous of anybody, now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Y and c gets Z.
- Let's start off by giving the X object to a. After that both b and c and unenvied agents. So now let's give the Z object to b. After that c is an unenvied agent. So now let's give the last object Y to c. Now a is not jealous of anybody, b is jealous of a and c is jealous of b, now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Z and c gets Y.
- Let's start off by giving the Y object to a. After that both b and c and unenvied agents. So now let's give the X object to b. After that c is an unenvied agent. So now let's give the last object Z to c. Now b and c are not jealous of anybody and a is jealous of b, now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets Y, b gets X and c gets Z.
- Let's start off by giving the Y object to a. After that both b and c and unenvied agents. So now let's give the Z object to b. After that c is an unenvied agent. So now let's give the last object X to c. Now a is jealous of c, b is jealous of c and c is jealous of a and b so there are two envy cycles, one between a and c and another between b and c. Because the tie breaker is by lexicographic order, the procedure does the a and c envy cycle first then a and c will switch then a is not jealous of anybody, b is jealous of a and c is jealous of b and now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Z and c gets Y.
- Let's start off by giving the Z object to a. After that both b and c and unenvied agents. So now let's give the X object to b. After that c is an unenvied agent. So now let's give the last object Y to c. Now a is jealous of b and c, b is not jealous of anybody and c is jealous of a. Since there is an envy cycle between a and c they will switch objects and now a gets Y and c gets Z, now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets Y, b gets X and c gets Z.
- Let's start off by giving the Z object to a. After that both b and c and unenvied agents. So now let's give the Y object to b. After that c is an unenvied agent. So now let's give the last object X to c. Now b is jealous of a and c, a is jealous of b and c and c is jealous of b and a. Since there is an envy cycle between a, b and c they will rotate objects against the direction of jealousy. However, because there are 2 envy cycles between a, b and c there could be two options. Because the tie breaker is by lexicographic order, a gets X from c, b gets Z from a and c gets Y from b so the outcome would be a gets X, b gets Z and c gets Y. And now since there is no envy cycle and no more objects to hand out then the procedure ends and the final result is a gets X, b gets Z and c gets Y.