Maximin Envy-Free Division of Indivisible Items

Assume that two players have strict rankings over an even number of indivisible items. We propose algorithms to find allocations of these items that are maximin—maximize the minimum rank of the items that the players receive—and are envy-free and Pareto-optimal if such allocations exist. We show that neither maximin nor envy-free allocations may satisfy other criteria of fairness, such as Borda maximinality. Although not strategy-proof, the algorithms would be difficult to manipulate unless a player has complete information about its opponent’s ranking. We assess the applicability of the algorithms to real-world problems, such as allocating marital property in a divorce or assigning people to committees or projects.