Envy minimization
Envy minimization
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: <math>\text{EnvyRatio}(X,i,j) := \max\left(1, {u_i(X_j)\over u_i(X_i)}\right)</math>; 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.
With additive and identical valuations: # Order the items by descending value; # 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:
- 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.
- 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 consider the problem of minimizing the maximum envy-difference, where the incoming items are indivisible and the valuations are normalized such that the value of each item for each agent 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 <math>\tilde{O}(\sqrt{T/n})</math>, against an adaptive adversary, who chooses the values of the incoming items adversarially. Jiang, Kulkarni, and Singla improved their envy bound using an algorithm for online two-dimensional discrepancy minimization under the assumption of stochastic values. The problem of minimizing the maximum envy-difference for indivisible items is known to reduce to the problem of minimizing discrepancy; this reduction holds in both the online and offline settings. The reduction has been used to obtain bounds for minimizing the envy-difference in various works including Jiang, Kulkarni, and Singla. * School choice.