Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

You and your friends move into a house and find yourselves debating who should get what room and for what part of the total rent. Is it always possible to split the rent in such a way that everyone will choose a different room? If so, how? This is an example of a "fair division" question: how to divide an object "fairly" among N persons with different preferences. The classical cake-cutting problem of Steinhaus is another example. Fair division problems comprise a relatively new area of game theory of interest to economists, political scientists, and mathematicians. In this talk, we give a brief survey of known envy-free solutions, and then present a new approach. Ideas from combinatorial topology (such as Sperner's lemma) have been used with great success in optimization for finding fixed points of highly nonlinear functions; we demonstrate a new application of such ideas to fair division problems, which arises from the careful choice of a vertex-labelling rule for triangulated polytopes. We obtain constructive N-person procedures for the division of goods, burdens, and mixtures of goods and burdens (such as the rent problem). Stronger solution concepts are obtained from stronger combinatorial theorems; proofs exhibit interesting connections between combinatorics, analysis, topology and the social sciences. We discuss generalizations and open questions. No background in topology is assumed.