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.
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 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 The envy-graph procedure assumes that each person has a cardinal utility function on bundles of items.
The agents do not have to actually report their cardinal utility: it is sufficient that they know how to rank bundles.
There are six different ways to allocate the objects: In the beginning because no one has anything then all of them are unenvied agents and this is the same in all the cases.
There are six different ways to allocate the objects: In the beginning because no one has anything then all of them are unenvied agents and this is the same in all the cases.
There are six different ways to allocate the objects: In the beginning because no one has anything then all of them are unenvied agents and this is the same in all the cases.
An adaptation called generalized envy-graph guarantees EF1 even with a mixture of goods and chores.
[3] When agents have cardinality constraints (i.e., for each category of items, there is an upper bound on the number of items each agent an get from this category), the envy-graph algorithm might fail.
However, combining it with the round-robin protocol gives an algorithm that finds allocations that are both EF1 and satisfy the cardinality constraints.
[4] When the agents have assignment valuations (aka OXS valuations), there is an extension of the envy-graph algorithm called "Algorithm H", in which the next allocation to an unenvied agent is selected such that agent-item utility is maximized.
There is no formal proof to the properties of this algorithm, but it fares well on realistic data.