Polevy's “scratch work” while trying to construct a function showing that a fair division must exist.
University Scholars have the opportunity to apply for a Scholars Independent Research Fellowship (SIRF), which provides training and funding to carry out independent research projects. Continuing our series of blog posts by SIRF recipients, University Scholar Maxwell Polevy, CCIS ’17, discusses the mathematics informing his project entitled, The Topology of Fair Division.
Suppose we have a cake, and N hungry people. The question is this: no matter the tastes of the people, can we always partition the cake into N pieces, one for each person, such that no one would prefer anyone else’s slice? Does there always exist a fair division?
The answer is yes, and the mathematics behind it is surprising. The fundamental idea behind one proof of the existence of such a division comes from the field of topology. Roughly, topology deals with properties of objects that are invariant under continuous deformation. For example, if we continuously deform a donut, we expect that the hole will not go away.
Topology tells us that it would be impossible for there to exist no intersection between all the people’s preferences, meaning it would be impossible for there to be no fair division. Technically speaking, we construct a function consisting of measures on each person’s preference sets (which cover the (N - 1)-simplex, an abstraction of the notion of a point, line, triangle, tetrahedron, etc., for n = 1, 2, 3, and 4 respectively), and note that this function maps sub-simplices to themselves. (The sub-simplices of a tetrahedron are the triangles, lines, and points that make up its boundary; so if you give this map a line from the simplex, it will map all points on that line to other points on that same line.) From this, topology therefore tells us that the map has a "degree" of one. (The degree of a map is a generalization of the notion of how many times a map "wraps around" a space; think of a map wrapping a line around a circle twice: this map would have degree 2.) Finally, due to a topological theorem, we conclude that the map is surjective, meaning it maps onto every point on the (N - 1)-simplex, and thus that there must exist such an intersection point. (This argument is due to D. Gale, 1984; see the lemma.)
We tried many different technical approaches to achieve this same result, mostly by constructing different functions whose images we could reason about in some way to conclude that there could not exist a nonempty intersection (by violating the known properties of maps from the (N - 1)-simplex to itself via a degree argument similar to the above). Checking whether the different functions we came up with satisfied our criteria proved difficult and time-consuming, so I wrote a program, which did the work of trying to generate counterexamples for us (unfortunately, none of our functions ended up working).
Ultimately we found this proof—which happens to not even be ostensibly related to fair division—rather by chance. It does not even use particular functions to achieve the result; it simply invokes the existence of some “partitions of unity,” measures on an open set whose sum total is always 1. Because of its generality, the proof idea can be extended to apply to probably quite a few variations on fair division (e.g., we can always let the first person pick their piece first). Since there are constructive proofs of fair division as well (i.e. those giving actual divisions; see The New York Times' rent division calculator), one can imagine practical applications, where the “cake” may be any reasonable, divisible object of interest.