Envy minimization

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: ${\displaystyle {\text{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.

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.

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.

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 ${\displaystyle O({\sqrt {T/n}})}$. Jiang, Kulkarni and Singla[6] improve their envy bound using an algorithm for online two-dimensional discrepancy minimization.

Other settings in which envy minimization was studied are:

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