Problem in computer science and operations research
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:
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":
With "additive and different valuations":
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.
The problem can be solved using the following local search algorithm.
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 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 formula_2. Jiang, Kulkarni and Singla improve their envy bound using an algorithm for "online two-dimensional discrepancy minimization".
Other settings.
Other settings in which envy minimization was studied are: