CME305: Discrete Mathematics and Algorithms

The problem of "fair division", that is, fairly dividing resources or costs among a collection of people, is one of the most basic problems that any society has to address. A Google search on the phrase "fair allocation" returns over 100K links, referring to the division of sports tickets, health resources, computer networking resources, voting power, intellectual property licenses, costs for environmental improvements, etc. Many of these situations demand formal protocols for division. For example, the 1982 Convention of the Law of the Sea, which was signed by 159 countries, specifies a simple cut-and-choose protocol for dividing seabed mining tracts. As more of the business and society interactions migrate to the Internet, it will become even more critical to have formal, well-studied, protocols for fair division.

There is wide literature on fair division within the fields of economics, political science, mathematics, operations research, and computer science. In the recent years there have been five academic books published on the subject (Young, 1994; Brams and Taylor, 1996; Robertson and Webb, 1998; Moulin, 2003; Barbanel, 2004) and one popular book (Brams and Taylor, 1999b) providing overviews. The general setting for most the academic research seems simple: you have a collection of resources (or costs) that you want to fairly divide among a known collection of entities. But there are many variations. For example, the situation with divisible resources (goods or sometimes "bads," like chores or other burdens) is quite different from the the situation with indivisible resources, and problems involving the division of money can be quite different from those involving the division of resources. But most of the variation comes from the fact that there are many reasonable way to formalize "fairness", including max-min fairness, proportional fairness, envy-free fairness, etc. which may or may not lead to stable allocations in the sense of say Nash Equilibrium, or strong Nash Equilibrium.

Predictably, researchers in the different disciplines studied different aspects of fair division. For example, many economists analyze and compare various axioms of fairness. A main contributions of computer scientists and mathematicians is to determine the complexity of achieving various goals. For example, a proof that a certainly property of fairness requires a very complex protocol may make an economist reconsider whether this property of fairness is sufficiently important to justify the increased complexity. Another contribution of mathematicians and computer scientists is to specify rules that guarantee players minimum payoffs whatever choices other players make, and to search for rules that induce players to be truthful ("incentive compatibility" to economists). Some mathematicians are especially interested in the measurability of fair division-for example, whether players' measures are atomic or nonatomic, countably additive or finitely additive, etc.