1000/1000

Hot
Most Recent

Submitted Successfully!

To reward your contribution, here is a gift for you: A free trial for our video production service.

Thank you for your contribution! You can also upload a video entry or images related to this topic.

Do you have a full video?

Are you sure to Delete?

Cite

If you have any further questions, please contact Encyclopedia Editorial Office.

HandWiki. Envy-Free Item Assignment. Encyclopedia. Available online: https://encyclopedia.pub/entry/36884 (accessed on 05 October 2024).

HandWiki. Envy-Free Item Assignment. Encyclopedia. Available at: https://encyclopedia.pub/entry/36884. Accessed October 05, 2024.

HandWiki. "Envy-Free Item Assignment" *Encyclopedia*, https://encyclopedia.pub/entry/36884 (accessed October 05, 2024).

HandWiki. (2022, November 28). Envy-Free Item Assignment. In *Encyclopedia*. https://encyclopedia.pub/entry/36884

HandWiki. "Envy-Free Item Assignment." *Encyclopedia*. Web. 28 November, 2022.

Copy Citation

Envy-free item assignment (EF assignment) is a fair item assignment problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that he believes to be at least as good as the bundle of any other agent. Since the items are indivisible, an EF assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will envy. Therefore, the division procedures provide various kinds of relaxations.

item assignment
envy-freeness
envy

The undercut procedure finds a complete EF allocation for two agents, if-and-only-if such allocation exists. It requires the agents to rank bundles of items, but it does not require cardinal utility information. It works whenever the agents' preference relations are strictly monotone, but does not need to assume that they are responsive preferences. In the worst case, the agents may have to rank all possible bundles, so the run-time might be exponential in the number of items.

It is usually easier for people to rank individual items than to rank bundles. Assuming all agents have responsive preferences, it is possible to lift the item-ranking to a partial bundle-ranking. For example, if the item-ranking is w>x>y>z, then responsiveness implies that {w,x}>{y,z} and {w,y}>{x,z}, but does not imply anything about the relation between {w,z} and {x,y}, between {x} and {y,z}, etc.

Given an item-ranking:

- An allocation is
**necessarily envy-free**(NEF) if it is envy-free according to*all*responsive bundle-rankings consistent with the item-ranking; - An allocation is
**possibly envy-free**(PEF) if it is envy-free according to*at least one*responsive bundle-ranking consistent with the item-ranking; - An allocation is
**necessarily Pareto-optimal**(NPE) if it is Pareto-optimal according to*all*responsive bundle-rankings consistent with the item-ranking; - An allocation is
**possibly Pareto-optimal**(PPE) if it is Pareto-optimal according to*at least one*responsive bundle-ranking consistent with the item-ranking.

Bouveret and Endriss and Lang^{[1]} study the algorithmic questions of finding a NEF/PEF allocation with an additional efficiency condition, particularly, completeness or NPE or PPE. In general, PEF is computationally easy while NEF is computationally hard.

The AL procedure finds an EF allocation for two agents. It may discard some of the items, but, the final allocation is Pareto efficient in the following sense: no other EF allocation is better for one and weakly better for the other.

The AL procedure only requires the agents to rank individual items. It assumes that the agents have responsive preferences and returns an allocation that is necessarily envy-free (NEF).

Several procedures find an allocation that is **Envy-free except one item (EF1)**: for each two agents A and B, there exists an item that can be removed from the bundle of B such that A does not envy B.^{[2]}

When all agents have weakly additive utilities, the following protocol (which is similar to Round-robin scheduling) attains a complete EF1 allocation:

- Order the agents arbitrarily.
- While there are unassigned items:
- Let each agent from 1 to [math]\displaystyle{ n }[/math] pick an item.

*Proof:*^{[3]}For every agent [math]\displaystyle{ i }[/math], divide the selections made by the agents to sub-sequences: the first subsequence starts at agent 1 and ends at agent [math]\displaystyle{ i-1 }[/math]; the latter subsequences start at [math]\displaystyle{ i }[/math] and end at [math]\displaystyle{ i-1 }[/math]. In the latter subsequences, agent [math]\displaystyle{ i }[/math] chooses first, so he can choose his best item, so he does not envy any other agent. Agent [math]\displaystyle{ i }[/math] can envy only one of the agents [math]\displaystyle{ 1,...,i-1 }[/math], and the envy comes only from an item they selected in the first subsequence. If this item is removed, agent [math]\displaystyle{ i }[/math] does not envy.

The round-robin protocol requires weak additivity, since it requires each agent to pick his "best item" without knowing what other items he is going to get. In other words, it assumes that the items are independent goods.

The unenvied-agent procedure returns a complete EF1 allocation for arbitrary preference relations. The only requirement is that the agents can rank bundles of items.

If the agents' valuations are represented by a cardinal utility function, then the EF1 guarantee has an additional interpretation: the numeric envy-level of each agent is at most the maximal-marginal-utility - the largest marginal utility of a single item for that agent.

The A-CEEI mechanism returns a partial EF1 allocation for arbitrary preference relations. The only requirement is that the agents can rank bundles of items.

A small number of items might remain unallocated; the allocation is Pareto-efficient with respect to the allocated items. Moreover, the A-CEEI mechanism is approximately strategyproof when the number of agents is large.

The Maximum-Nash-Welfare (MNW) algorithm selects a complete allocation that maximizes the product of utilities. It requires each agent to provide a numeric valuation of each item, and assumes that the agents' utilities are additive. The resulting allocation is EF1 and Pareto-efficient.^{[3]}

If the agents' utilities are not additive, the MNW solution is not necessarily EF1; but if the agents' utilities are at least submodular, the MNW solution satisfies a weaker property called *Marginal-Envy-Freeness except-1-item* (MEF1).

There is an alternative criterion called **Envy-freeness-except-cheapest (EFx)**: For each two agents A and B, if we remove from the bundle of B *any* item, then A does not envy B. EFx is strictly stronger than EF1. As of this writing, it is not known whether EFx allocations always exist.^{[3]}

Given an allocation *X*, define the envy ratio of *i* in *j* as:

- [math]\displaystyle{ EnvyRatio(X,i,j) := \max(1, {u_i(X_j)\over u_i(X_i)}) }[/math]

so the ratio is 1 if *i* does not envy *j*, and it is larger when *i* envies *j*. Define the envy ratio of an assignment as:

- [math]\displaystyle{ EnvyRatio(X) := \max_{i,j}(EnvyRatio(X,i,j) }[/math]

The **envy ratio minimization** problem is the problem of finding an allocation *X* with smallest envy ratio.

With general valuations, any deterministic algorithm that computes an alloation with minimum envy-ratio requires a number of queries which is exponential in the number of goods in the worst case.^{[4]}

With additive and identical valuations:^{[4]}

- The following greedy algorithm finds an allocation whose envy-ratio is at most 1.4 times the minimum:
^{[5]}- 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 envy-ratio minimization. Furthermore, when the number of players is constant, there is an FPTAS.

With additive and different valuations:^{[6]}

- 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, there is an FPTAS.
- When the number of agents equals the number of items, there is a polynomial-time algorithm.

The Adjusted winner procedure returns a complete and efficient EF allocation for two agents, but it might have to divide a single item. It requires the agents to report a numeric value for each item, and assumes that they have additive utilities.

The empty allocation is always EF. But if we want some efficiency in addition to EF, then the decision problem becomes computationally hard: ^{[7]}^{:300–310}

- Deciding whether an EF and
*complete*allocation exists is NP complete. This is true even when there are only two agents, and even when their utilities are additive and identical, since in this case finding an EF allocation is equivalent to solving the partition problem.^{[4]} - Deciding whether an EF and
*Pareto efficient*allocation exists is above NP: it is [math]\displaystyle{ \Sigma_{2}^{\textrm{P}} }[/math]-complete even with dichotomous preferences^{[8]}and even with additive utilities.^{[9]}

If the agents have additive utility functions that are drawn from probability distributions satisfying some independence criteria, and the number of items is sufficiently large relative to the number of agents, then an EF allocation exists with high probability. Particularly:^{[10]}

- If the number of items is sufficiently large: [math]\displaystyle{ m = \Omega(n \log n) }[/math], then w.h.p. an EF allocation exists (the probability goes to 1 as m goes to infinity).
- If the number of items is not sufficiently large, i.e., [math]\displaystyle{ m = n + o(n) }[/math], then w.h.p. an EF allocation does not exist.

- Every EF allocation is
*min-max-fair*. This follows directly from the ordinal definitions and does not depend on additivity. - If all agents have additive utility functions, then an EF allocation is also
*proportional*and*max-min-fair*. Otherwise, an EF allocation may be not proportional and even not max-min-fair. - Every allocation of a
*competitive equilibrium from equal incomes*is also envy-free. This is true regardless of additivity.^{[2]} - Every Nash-optimal allocation (allocation that maximizes the product of utilities) is EF1.
^{[3]}

See Fair item assignment for details and references.

Below, the following shorthands are used:

- [math]\displaystyle{ n }[/math] = the number of agents participating in the division;
- [math]\displaystyle{ m }[/math] = the number of items to divide;
- EF = envy-free, EF1 = envy-free except-1-item (weaker than EF), MEF1 = marginal-envy-free except-1-item (weaker than EF1).
- PE = Pareto-efficient.

Name | #partners | Input | Preferences | #queries | Fairness | Efficiency | Comments |
---|---|---|---|---|---|---|---|

Undercut | 2 | Bundle ranking | Strictly monotone | [math]\displaystyle{ 2^m }[/math] | EF | Complete | If-and-only-if a complete EF allocation exists |

AL | 2 | Item ranking | Weakly additive | [math]\displaystyle{ Poly(m) }[/math] | Necessarily-EF | Partial, but not Pareto-dominated by another NEF | |

Adjusted winner | 2 | Item valuations | Additive | [math]\displaystyle{ Poly(m) }[/math] | EF and equitable | PE | Might divide one item. |

Round-robin | [math]\displaystyle{ n }[/math] | Item ranking | Weakly additive | [math]\displaystyle{ m }[/math] | Necessarily-EF1 | Complete | |

Unenvied-agent | [math]\displaystyle{ n }[/math] | Bundle ranking | Monotone | [math]\displaystyle{ O(m n^3) }[/math] | EF1 | Complete | |

A-CEEI | [math]\displaystyle{ n }[/math] | Bundle ranking | Any | ? | EF1, and [math]\displaystyle{ (n+1) }[/math]-maximin-share | Partial, but PE w.r.t. allocated items | Also approximately strategyproof when there are many agents. |

Maximum-Nash-Welfare^{[3]} |
[math]\displaystyle{ n }[/math] | Item valuations | Additive | NP-hard (but there are approximations in special cases) | EF1, and approximately-[math]\displaystyle{ n }[/math]-maximin-share | PE |
With submodular utilities, allocation is PE and MEF1. |

- Sylvain Bouveret, Ulle Endriss, Jérôme Lang (2010). "Fair Division Under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods". ECAI 2010. pp. 387–392.
- Budish, Eric (2011). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy 119 (6): 1061. doi:10.1086/664613. https://dx.doi.org/10.1086%2F664613
- Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2016). "The Unreasonable Fairness of Maximum Nash Welfare". Proceedings of the 2016 ACM Conference on Economics and Computation - EC '16. pp. 305. doi:10.1145/2940716.2940726. ISBN 9781450339360. https://dx.doi.org/10.1145%2F2940716.2940726
- Lipton, R. J.; Markakis, E.; Mossel, E.; Saberi, A. (2004). "Proceedings of the 5th ACM conference on Electronic commerce - EC '04". pp. 125. doi:10.1145/988772.988792. ISBN 1-58113-771-0. https://dx.doi.org/10.1145%2F988772.988792
- Graham, R. L. (1969). "Bounds on Multiprocessing Timing Anomalies". SIAM Journal on Applied Mathematics 17 (2): 416. doi:10.1137/0117039. https://dx.doi.org/10.1137%2F0117039
- 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. doi:10.1016/j.dam.2014.09.010. https://dx.doi.org/10.1016%2Fj.dam.2014.09.010
- Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016) (in en). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. https://books.google.com/books?id=nMHgCwAAQBAJ. (free online version)
- Bouveret, S.; Lang, J. (2008). "Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity". JAIR 32: 525-564. doi:10.1613/jair.2467. https://dx.doi.org/10.1613%2Fjair.2467
- De Keijzer, Bart; Bouveret, Sylvain; Klos, Tomas; Zhang, Yingqian (2009). "Algorithmic Decision Theory". 5783. pp. 98. doi:10.1007/978-3-642-04428-1_9. ISBN 978-3-642-04427-4. https://dx.doi.org/10.1007%2F978-3-642-04428-1_9
- John P. Dickerson; Jonathan Goldman; Jeremy Karp; Ariel D. Procaccia; Tuomas Sandholm (2014). "The Computational Rise and Fall of Fairness". In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (2014),. pp. 1405–1411. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.703.8413&rep=rep1&type=pdf. Retrieved 26 August 2016. ACM link

More

Information

Subjects:
Others

Contributor
MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register
:

View Times:
321

Entry Collection:
HandWiki

Update Date:
28 Nov 2022