ToolBox

The algorithm works as follows:

Initialise all agents' allocations as empty i.e. no items are assigned yet.

Then, for each item:

Allocate it to any agent,

$i$

, who no one is envious of. Visually, this is any node in the envy graph that has no incoming edges.

This new item assignment may cause rise in new envy towards agent

$i$

, or it could cause agent

$i$

to no longer be envious of some agents. Update the envy graph accordingly. Visually, the direction of any edge on the envy graph indicates the direction of envy, for example, an edge pointing from

$a$

to

$b$

would indicate that agent

$a$

is envious of agent

$b.$

Then analyse the envy graph to look for any cycles, if there exists any such cycle e.g.

$a\rightarrow b \rightarrow \ c \rightarrow a$

, remove this cycle by exchanging those agents' bundles along the cycle. This means that each agent gets the bundle of whoever they are envious of in the cycle. Using the example cycle, this means that

$a$

gets

$b$

's bundle,

$b$

gets

$c$

's bundle, and

$c$

gets

$a$

's bundle. Visually, detected cycles will be highlighted in

red

.

Repeat step 3 until there are no more cycles in the envy graph.

Once all items are allocated and all cycles are removed, the resulting allocation will satisfy EF1.