Unenvied-agent procedure
The unenvied-agent procedure is a procedure for fair item assignment among any number of people. It finds an "almost" envy-free item assignment of all items. Specifically, it finds an allocation in which the envy of every person is bounded by the maximum marginal utility it derives from a single item.
The procedure was presented by Lipton and Markakis and Mossel and Saberi[1] and it is also described in .[2]:300–301
Assumptions
The unenvied-agent procedure assumes that each person has a cardinal utility function on bundles of items. This utility function does not have to be additive. I.e, the items are not assumed to be independent goods.
The agents do not have to actually report their cardinal utility: it is sufficient that they know how to rank bundles.
The procedure
- Order the items arbitrarily.
- While there are unassigned items:
- Ensure that there is an unenvied agent - an agent that no other agent envies.
- Give the next item to the unenvied agent.
In step 2, if there is no unenvied agent, it means that there is a directed cycle in the envy graph - a directed graph in which each agent points to all agents he envies. Cycles can be removed by cyclic exchange of bundles. After all cycles are removed, the envy-graph must have a node with no incoming edges; this node represents an unenvied agent.
The resulting allocation is not necessarily EF, but it is envy-free except maximal-marginal-utility (EFM). The maximal-marginal-utility is the largest marginal utility of a single item.
Rerefences
- ↑ Lipton, R. J.; Markakis, E.; Mossel, E.; Saberi, A. (2004). "On approximately fair allocations of indivisible goods". Proceedings of the 5th ACM conference on Electronic commerce - EC '04. p. 125. doi:10.1145/988772.988792. ISBN 1-58113-771-0.
- ↑ Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. (free online version)