Cake-cutting with low envy

Supervisor

Suitable for

Abstract

Description: I-cut-you-choose is the classical way for two people to share a divisible good. For three people, there exists a sequence of operations using 5 cuts, that is also envy-free, but for 4 or more people, it is unknown whether you can share in an envy-free manner, using a finite number of cuts. (This is with respect to a well-known class of procedures that can be represented using a tree whose nodes are labelled with basic "cut" and "choose" operations.) The general idea of this project is to generate and test large numbers of potential cake-cutting procedures, and measure the "extent of envy" in the case where they are not envy-free. (See wikipedia's page on "cake-cutting problem".) It is of interest to find out the amount of envy that must exist in relatively simple procedures.

Prerequisites: competance and enthusiasm for program design and implementation; mathematical analysis and proofs.