Shan Shan

Assistant Professor
Centre of Quantum Mathematics
Dept of Math and Computer Science
University of Southern Denmark

email: shan-qm at imada dot sdu dot dk
github: sshanshans
website: https://sshanshans.github.io

SWIM 2017
An introduction to fair division and cake-cutting algorithms
Summer Workshop in Mathematics
June 20-30, 2017

Course Description and Objectives

How many times did you share a cake with your family and friends while envying someone who got a better piece than yours? Is there a way to cut cake fairly so that everyone is satisfied? Mathematicians and computer scientists have been intrigued by this fair division problem and proposing algorithms to solve it. However, other real life problems can be more complicated than cutting a cake. How to share apartment rent with your roommate? How to split a taxi fare among riders heading to different locations? We will look at different aspects of sharing by case study and introduce the corresponding basic math concepts and their applications.

We will focus on problem solving skills with tools from graph theory, number theory, complexity, and combinatorial topology. But the most important thing is to have fun playing with mathematics!

Course Materials

For all course materials, please go to the git repository: swim2017

Agenda

I. Simple fair sharing: existence, algorithm and complexity
Day 1 - What is (simple) fair division
Day 2 - How many cuts are needed
Day 3 - Applying graph theory to simple fair division

II. Some variations on the themes of fair division
Day 4 - Unequal share
Day 5 - Envy-free fair division
Day 6 - Sperner’s lemma in fair division