Envy minimization

Last updated August 25, 2023

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: ${\text{EnvyRatio}}(X,i,j):=\max \left(1,{u_{i}(X_{j}) \over u_{i}(X_{i})}\right)$ $Envy minimization$ ; 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]^: 3

With additive and identical valuations:^[1]^: 4–6

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.^[4]

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:

Related Research Articles

Distributed constraint optimization is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is minimized.

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.

Utilitarian cake-cutting is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting.

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.

Fair random assignment is a kind of a fair division problem.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

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.

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.

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:

The multiple subset sum problem is an optimization problem in computer science and operations research. It is a generalization of the subset sum problem. The input to the problem is a multiset $of n integers and a positive integer m representing the number of subsets. The goal is to construct, from the input integers, some m subsets. The problem has several variants:$

Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J₁, J₂, ..., J_n on m different machines, such that a certain objective function is optimized. The time that machine i needs in order to process job j is denoted by p_i,j. The term unrelated emphasizes that there is no relation between values of p_i,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which p_i,j = p_i / s_j, and identical-machines scheduling - in which p_i,j = p_i.

Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.

References

1 2 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. doi:10.1145/988772.988792. ISBN 1-58113-771-0.
↑ Graham, R. L. (1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. CiteSeerX 10.1.1.90.8131 . doi:10.1137/0117039.
↑ 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. doi: 10.1016/j.dam.2014.09.010 .
1 2 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. doi:10.1007/s10458-015-9291-7. ISSN 1387-2532. S2CID 13834856.
↑ Benade, Gerdus; Kazachkov, Aleksandr M.; Procaccia, Ariel D.; Psomas, Christos-Alexandros (2018-06-11). "How to Make Envy Vanish over Time". Proceedings of the 2018 ACM Conference on Economics and Computation. EC '18. Ithaca, NY, USA: Association for Computing Machinery. pp. 593–610. doi:10.1145/3219166.3219179. ISBN 978-1-4503-5829-3. S2CID 3340196.
↑ Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2019-10-02). "Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization". arXiv: 1910.01073 [cs.DS].
↑ Yukihiro, Nishimura (2008). "Envy Minimization in the Optimal Tax Context". AgEcon Search. Working Paper No. 1178. doi:10.22004/ag.econ.273655.
↑ 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. doi:10.3386/w23265. S2CID 9497845.{{cite journal}}: Cite journal requires |journal= (help)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[lmms04-1] 1 2 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. doi:10.1145/988772.988792. ISBN 1-58113-771-0.

[g69-2] Graham, R. L. (1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics. 17 (2): 416–429. CiteSeerX 10.1.1.90.8131 . doi:10.1137/0117039.

[nr15-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. doi: 10.1016/j.dam.2014.09.010 .

[:2-4] 1 2 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. doi:10.1007/s10458-015-9291-7. ISSN 1387-2532. S2CID 13834856.

[:0-5] Benade, Gerdus; Kazachkov, Aleksandr M.; Procaccia, Ariel D.; Psomas, Christos-Alexandros (2018-06-11). "How to Make Envy Vanish over Time". Proceedings of the 2018 ACM Conference on Economics and Computation. EC '18. Ithaca, NY, USA: Association for Computing Machinery. pp. 593–610. doi:10.1145/3219166.3219179. ISBN 978-1-4503-5829-3. S2CID 3340196.

[6] Jiang, Haotian; Kulkarni, Janardhan; Singla, Sahil (2019-10-02). "Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization". arXiv: 1910.01073 [cs.DS].

[7] Yukihiro, Nishimura (2008). "Envy Minimization in the Optimal Tax Context". AgEcon Search. Working Paper No. 1178. doi: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. doi:10.3386/w23265. S2CID 9497845.{{cite journal}}: Cite journal requires |journal= (help)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]