Envy minimization explained

In computer science and operations research, the envy minimization problem is the problem of allocating discrete items among agents with different valuations over the items, such that the amount of envy is as small as possible.

Ideally, from a fairness perspective, one would like to find an envy-free item allocation - an allocation in which no agent envies another agent. That is: no agent prefers the bundle allocated to another agent. However, with indivisible items this might be impossible. One approach for coping with this impossibility is to turn the problem to an optimization problem, in which the loss function is a function describing the amount of envy. In general, this optimization problem is NP-hard, since even deciding whether an envy-free allocation exists is equivalent to the partition problem. However, there are optimization algorithms that can yield good results in practice.

Defining the amount of envy

There are several ways to define the objective function (the amount of envy) for minimization. Some of them are:

• The number of envious agents;
• The number of envy relations (- edges in the envy graph);
• The maximum envy-ratio, where the envy ratio of i in j in allocation X is defined as:

EnvyRatio (X,i,j) : = max \left( 1 , {u _{i(X} _{j)\over} u _{i(X} _{i)}\right)} ; so the ratio is 1 if i does not envy j, and it is larger when i envies j.

• • Similarly, one can consider the sum of envy-ratios, or their product.
• The maximum, the sum or the product of the envy-difference.

Minimizing the envy-ratio

With general valuations, any deterministic algorithm that minimizes the maximum envy-ratio requires a number of queries which is exponential in the number of goods in the worst case.^[1]

With additive and identical valuations:

• The following greedy algorithm finds an allocation whose maximum envy-ratio is at most 1.4 times the optimum:^[2]
  1. Order the items by descending value;
  2. While there are more items, give the next item to an agent with the smallest total value.
• There is a PTAS for max-envy-ratio minimization. Furthermore, when the number of players is constant, there is an FPTAS.

With additive and different valuations:^[3]

• When the number of agents is part of the input, it is impossible to obtain in polynomial time an approximation factor better than 1.5, unless P=NP.
• When the number of agents is constant (not a part of the input), there is an FPTAS for minimizing the maximum envy-ratio, and the product of envy-ratios.
• When the number of agents equals the number of items, there is a polynomial-time algorithm.

Distributed envy minimization

In some cases, it is required to compute an envy-minimizing allocation in a distributed manner, i.e., each agent should compute his/her own allocation, in a way that guarantees that the resulting allocation is consistent. This problem can be solved by presenting it as an Asymmetric distributed constraint optimization problem (ADCOP) as follows.

• Add a binary variable v_ij for each agent i and item j. The variable value is "1" if the agent gets the item, and "0" otherwise. The variable is owned by agent i.
• To express the constraint that each item is given to at most one agent, add binary constraints for each two different variables related to the same item, with an infinite cost if the two variables are simultaneously "1", and a zero cost otherwise.
• To express the constraint that all items must be allocated, add an n-ary constraint for each item (where n is the number of agents), with an infinite cost if no variable related to this item is "1".

The problem can be solved using the following local search algorithm.^[4]

• All agents are ordered lexicographically (e.g. by their name or index).
• Each agent also orders its variables lexicographically.
• Each agent, in turn, claims any item that was not allocated to an agent with a higher priority ("claims" means that the agent assigns "1" to the corresponding variable).
• After an agent has assigned all its variables (either 1 or 0), it sends the resulting assignment to the next agent in the lexicographic order.
• The agents send to each other messages with their envy evaluation of the current assignment.
• After receiving envy evaluations from other agents, the agent may decide to backtrack on a variable; if there are no more variables to backtrack, the agent may backtrack to a previous agent. Once the first agent backtracks its first variable, the search has ended and the optimal allocation has been found.

Online minimization of the envy-difference

Sometimes, the items to allocate are not available all at once, but rather arrive over time in an online fashion. Each arriving item must be allocated immediately. An example application is the problem of a food bank, which accepts food donations and must allocate them immediately to charities.

Benade, Kazachkov, Procaccia and Psomas^[5] consider the problem of minimizing the maximum envy-difference, where the valuations are normalized such that the value of each item is in [0,1]. Note that in the offline variant of this setting, it is easy to find an allocation in which the maximum envy-difference is 1 (such an allocation is called EF1; see envy-free item allocation for more details). However, in the online variant the envy-difference increases with the number of items. They show an algorithm in which the envy after T items is in

O(\sqrt{T/n}) . Jiang, Kulkarni and Singla^[6] improve their envy bound using an algorithm for online two-dimensional discrepancy minimization.

Other settings

Other settings in which envy minimization was studied are:

• Optimal tax.^[7]
• School choice.^[8]

References

1. Lipton. R. J.. Markakis. E.. Mossel. E.. Saberi. A.. 2004. Proceedings of the 5th ACM conference on Electronic commerce - EC '04. 125. 10.1145/988772.988792. 1-58113-771-0. On approximately fair allocations of indivisible goods.
2. Graham. R. L.. 1969. Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics. 17. 2. 416–429. 10.1.1.90.8131. 10.1137/0117039.
3. Nguyen. Trung Thanh. Rothe. Jörg. 2014. Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods. Discrete Applied Mathematics. 179. 54–68. 10.1016/j.dam.2014.09.010. free.
4. Netzer. Arnon. Meisels. Amnon. Zivan. Roie. 2016-03-01. Distributed envy minimization for resource allocation. Autonomous Agents and Multi-Agent Systems. 30. 2. 364–402. 10.1007/s10458-015-9291-7. 13834856. 1387-2532.
5. Book: Benade. Gerdus. Kazachkov. Aleksandr M.. Procaccia. Ariel D.. Psomas. Christos-Alexandros. Proceedings of the 2018 ACM Conference on Economics and Computation . How to Make Envy Vanish over Time . 2018-06-11. https://doi.org/10.1145/3219166.3219179. EC '18. Ithaca, NY, USA. Association for Computing Machinery. 593–610. 10.1145/3219166.3219179. 978-1-4503-5829-3. 3340196.
6. Jiang. Haotian. Kulkarni. Janardhan. Singla. Sahil. 2019-10-02. Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization. cs.DS. 1910.01073.
7. Yukihiro. Nishimura. 2008. Envy Minimization in the Optimal Tax Context. AgEcon Search. Working Paper No. 1178 . en. 10.22004/ag.econ.273655.
8. Abdulkadiroglu. Atila. Che. Yeon-Koo. Pathak. Parag A.. Roth. Alvin E.. Tercieux. Olivier. 2017-03-27. Minimizing Justified Envy in School Choice: The Design of New Orleans' OneApp. Working Paper Series . 10.3386/w23265 . 9497845 . en.