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.

When envy-freeness is impossible, one may try to minimize the total amount of envy. This minimization can be defined in several ways:

• Minimize the number of envious agents;
• Minimize the number of envy relations (- the number of edges in the envy graph);
• Minimize the maximum envy-ratio, where the envy ratio of i in j in allocation X is defined as: $EnvyRatio(X,i,j):=\max(1,{u_{i}(X_{j}) \over u_{i}(X_{i})})$ so the ratio is 1 if i does not envy j, and it is larger when i envies j.
• Minimize the sum of envy-ratios, or their product.
• Minimize the maximum or the sum of envy-differences.

Minimizing the maximum 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:

• The following greedy algorithm finds an allocation whose maximum envy-ratio is at most 1.4 times the optimum:
  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:

• 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).