# Fair Division in Theory and Practice [CSE/Poli Sci 245A (Spring 2015)]

## Overview

In lecture, we studied the Divde and Choose algorithm. In this lab you will program the technique, apply it to some data, and write a short report about your results.
You are encouraged to work in groups of up to 3 people on this project. Your group submits just one report, coauthored by all group members.

## Procedure

The program you write should simulate a divide and choose situation. For each of the above data sets, run your program under each of the following conditions:
• P1 cuts, P2 chooses
• P2 cuts, P1 chooses

## Report (due Jan 28, start of class)

Write between 2-5 pages describing the results you have seen. In your report, include the following:
• The names of the people in your group
• For each of the cakes:
• Homogeneous
• chocolate/vanilla
• Random
• Israel
describe the results of your divide-and-choose procedure:
• How did the cutter try to find 1/2 value in the cake?
• For example, by column?
• By row?
• Diagonally
• ???
• What value did the cutter receive?
• What value did the chooser receive?
• Gedankenexperiment (thought exercise)
Suppose the cutter wants to find a collection of cells in the cake (spreadsheet) whose sum is closest to 1/2. Those cells need not be compact or contiguous. How hard is this problem in general?