Envy-graph procedure

The envy-graph procedure (also called the envy-cycles procedure) is a procedure for <a href="/facts/Fair_item_allocation/Hvx2XrG9">fair item allocation</a>. It can be used by several people who want to divide among them several discrete items, such as heirlooms, sweets, or seats in a class.
Ideally, we would like the allocation to be <a href="/facts/Envy-free/LbsxvkUR">envy-free</a> (EF). i.e., to give each agent a bundle that he/she prefers over the bundles of all other agents. However, the items are discrete and cannot be cut, so an envy-free assignment might be impossible (for example, consider a single item and two agents). The envy-graph procedure aims to achieve the "next-best" option -- envy-freeness up to at most a single good (EF1): it finds an allocation in which the envy of every person towards every other person is bounded by the maximum <a href="/facts/Marginal_utility/ElXNboxy">marginal utility</a> it derives from a single item. In other words, for every two people i and j, there exists an item such that, if that item is removed, i does not envy j.
The procedure was presented by Lipton and Markakis and Mossel and Saberi and it is also described in .: 300–301

Envy-graph procedure open-in-new

Envy-graph procedure