Envy-graph procedure

<h2 id="assumptions">Assumptions</h2>
<p>The envy-graph procedure assumes that each person has a <a href="/facts/Cardinal_utility/5jeuW4Iw">cardinal utility</a> function on bundles of items. This utility function has to be <a href="/facts/Monotonic_function/MjQK0YL2">monotone</a> (the utility of a set is at least as large as the utility of its subsets). However, it does <i>not</i> have to be additive. I.e, the items are <i>not</i> assumed to be <a href="/facts/Independent_goods/6FDMlQGT">independent goods</a>.
</p><p>The agents do not have to actually report their cardinal utility: it is sufficient that they know how to rank bundles.
</p>
<h2 id="the-procedure">The procedure</h2>
<ol><li>Order the items arbitrarily.</li>
<li>While there are unassigned items:
<ul><li>Ensure that there is an <i>unenvied agent</i> - an agent that no other agent envies.</li>
<li>Give the next item to the unenvied agent.</li></ul></li></ol>
<p>In step 2, if there is no unenvied agent, it means that there is a <a href="/facts/Directed_cycle/Is44edrv">directed cycle</a> in the <i>envy graph</i>  - a <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> in which each agent points to all agents he envies. Cycles can be removed by cyclic exchange of bundles. After all cycles are removed, the envy-graph must have a node with no incoming edges; this node represents an unenvied agent.
</p><p>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.
</p>
<h2 id="run-time-analysis">Run-time analysis</h2>
<p>Suppose there are <i>m</i> items. Each allocation of an item adds to the envy-graph at most <i>n</i>-1 edges. Hence, at most 
  
    
      
        (
        n
        −
        1
        )
        m
      
    
    {\displaystyle (n-1)m}
  
 edges are added overall. Each cycle-removal removes at least two edges. Hence, we need to run the cycle-removal step at most 
  
    
      
        (
        n
        −
        1
        )
        m
        
          /
        
        2
      
    
    {\displaystyle (n-1)m/2}
  
 times. Finding a cycle can be done in time  
  
    
      
        O
        (
        
          n
          
            2
          
        
        )
      
    
    {\displaystyle O(n^{2})}
  
 using e.g. <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a>. All in all, the run-time is 
  
    
      
        O
        (
        
          n
          
            3
          
        
        m
        )
      
    
    {\displaystyle O(n^{3}m)}
  
.
</p>
<h2 id="examples">Examples</h2>
<p>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.
</p><p>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. There are six different ways to allocate the objects:
</p>
6 Different Results<table><tbody><tr><th></th><th>X</th><th>Y</th><th>Z</th></tr><tr><td>a</td><td>3</td><td>2</td><td>1</td></tr><tr><td>b</td><td>3</td><td>2</td><td>1</td></tr><tr><td>c</td><td>3</td><td>2</td><td>1</td></tr></tbody></table>
<p>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.
</p>
<ol><li>Let's start off by giving the X object to a. After that both b and c are 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.</li>
<li>Let's start off by giving the X object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Y object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Y object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Z object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Z object to a.  After that both b and c are 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.</li></ol>
<p>2) With 3 people and 3 objects, every possible allocation will be the same result. This case happens when each of the three people have completely different preferences, because each person has something else they prefer no matter what they will get what they want.
</p>
Same Result<table><tbody><tr><th></th><th>X</th><th>Y</th><th>Z</th></tr><tr><td>a</td><td>3</td><td>2</td><td>1</td></tr><tr><td>b</td><td>1</td><td>3</td><td>2</td></tr><tr><td>c</td><td>2</td><td>1</td><td>3</td></tr></tbody></table>
<p>There are six different ways to allocate the objects:
</p><p>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.
</p>
<ol><li>Let's start off by giving the X object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the X object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Y object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Y object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Z object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Z object to a.  After that both b and c are 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.</li></ol>
<p>3) With 3 people and 3 objects, any other situation then the first and second example will give between 1 and 6 results. So for that to happen you just need at least two people to have same preference on one object or at most for two people to have different preferences on the same object.
</p>
3 Different Results<table><tbody><tr><th></th><th>X</th><th>Y</th><th>Z</th></tr><tr><td>a</td><td>3</td><td>2</td><td>1</td></tr><tr><td>b</td><td>3</td><td>1</td><td>2</td></tr><tr><td>c</td><td>1</td><td>2</td><td>3</td></tr></tbody></table>
<p>There are six different ways to allocate the objects:
</p><p>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.
</p>
<ol><li>Let's start off by giving the X object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the X object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Y object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Y object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Z object to a.  After that both b and c are 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.</li>
<li>Let's start off by giving the Z object to a.  After that both b and c are 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.</li></ol>
<h2 id="extensions">Extensions</h2>
<p>The envy-graph algorithm guarantees EF1 when the items are <i>goods</i> (- the marginal value of each item is positive for all agents). However, when there are both goods and chores, it does not guarantee EF1. An adaptation called <i>generalized envy-graph</i> guarantees EF1 even with a mixture of goods and chores. It works whenever the valuations are <i>doubly-monotonic</i>, that is: each agent can partition the items into two subsets: one subset contains goods (- items whose marginal utility is always positive) and the other contains chores (- items whose marginal utility is always negative).<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p><p>When agents have cardinality constraints (i.e., for each category of items, there is an upper bound on the number of items each agent an get from this category), the envy-graph algorithm might fail. However, combining it with the <a href="/facts/Round-robin_item_allocation/xXM6Tvua">round-robin protocol</a> gives an algorithm that finds allocations that are both EF1 and satisfy the cardinality constraints.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p><p>When the agents have <a href="/facts/Assignment_valuation/mUs5lvGk">assignment valuations</a> (aka OXS valuations), there is an extension of the envy-graph algorithm called "Algorithm H", in which the next allocation to an unenvied agent is selected such that agent-item utility is maximized. There is no formal proof to the properties of this algorithm, but it fares well on realistic data.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Envy-free_item_allocation/3HA9azrr">Envy-free item allocation</a></li>
<li><a href="/facts/Greedy_number_partitioning/EuDV9gm8">Greedy number partitioning</a> - can be viewed a special case of the envy-graph algorithm for the case when all agents have identical valuations.</li>
<li><a href="/facts/Decreasing_Demand_procedure/uYkcClCl">Decreasing Demand procedure</a> and <a href="/facts/Undercut_procedure/TE6UJN0F">undercut procedure</a> - two additional procedures based on the ordinal ranking of bundles.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Lipton, R. J.; Markakis, E.; Mossel, E.; Saberi, A. (2004). "On approximately fair allocations of indivisible goods". Proceedings of the 5th ACM conference on Electronic commerce - EC '04. p. 125. CiteSeerX 10.1.1.400.1762. doi:10.1145/988772.988792. ISBN 1-58113-771-0. <a href="1-58113-771-0" target="_blank">1-58113-771-0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. <a href="9781107060432" target="_blank">9781107060432</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, Toby Walsh (2019). "Fair Allocation of Indivisible Goods and Chores" (PDF). IJCAI 2019 conference.{{cite web}}:  CS1 maint: multiple names: authors list (link) <a href="https://www.ijcai.org/Proceedings/2019/0008.pdf" target="_blank">https://www.ijcai.org/Proceedings/2019/0008.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Biswas, Arpita; Barman, Siddharth (2018-07-13). "Fair division under cardinality constraints". Proceedings of the 27th International Joint Conference on Artificial Intelligence. IJCAI'18. Stockholm, Sweden: AAAI Press: 91–97. arXiv:1804.09521. ISBN 978-0-9992411-2-7. <a href="978-0-9992411-2-7" target="_blank">978-0-9992411-2-7</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Benabbou, Nawal; Chakraborty, Mithun; Elkind, Edith; Zick, Yair (2019-08-10). "Fairness Towards Groups of Agents in the Allocation of Indivisible Items". {{cite journal}}: Cite journal requires |journal= (help) <a href="https://hal.sorbonne-universite.fr/hal-02155024" target="_blank">https://hal.sorbonne-universite.fr/hal-02155024</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Envy-graph procedure open-in-new

Envy-graph procedure