Go to course navigation

8. Cake Cutting

Your task is to analyse the following algorithm for proportional cake division between $n$ players. In order to prove the task at hand formally, we include here all the necessary definitions.

Definition 1 (Problem of Proportional Cake-Cutting)

Input
A set of players $N=\{1,\ldots,n\}$ , a homogeneous cake represented as the interval $[0,1]$ . For each player $i$ , we have a function $V_i$ which returns for every subinterval $I\subseteq[0,1]$ a value assigned by the player $i$ to this piece of cake. Additionally, the function $V_i$ must satisfy the following:
$V_i([0,1]) = 1$ ,
$V_i([x,y]) \geq 0$ for $\forall x,y\in[0,1]$
For every subinterval $[x,y]$ and $0 \leq \lambda \leq 1$ , there is a point $z\in[x,y]$ such that $V_i([x,z]) = \lambda V_i([x,y])$ .

A piece of cake is a subinterval of $[0,1]$ .

Output
Find a division of the cake between the players such that for every player $i$ and his piece $P_i$ we have $V_i(P_i) \geq \frac{1}{n}$ .

Let us recall an algorithm for this problem that we introduced in the seminar.

Algorithm 1 (Dubins and Spanier; 1961)

In the first round, each player makes a mark at a point $x_i$ such that $V_i([0,x_i]) = \frac{1}{n}$ .
The player $i^*$ with the smallest value of $x_{i^*}$ receives the piece $[0,x_{i^*}]$ .
The process continues in the same way with the rest of the cake and the remaining players.

In the seminar, we have also mentioned that analysis of cake-cutting algorithms is done in a special model of computation since standard techniques are hardly usable.

Definition 2 (Robertson-Webb model of computation; 1988)

In this computation model, we have the following two operations:

eval_i([x,y]) – returns $V_i([x,y])$ .

cut_i(x,α) – the player $i$ cuts off the piece $[x,y]$ starting at the point $x$ that he values exactly at $\alpha$ , i.e., $V_i([x,y]) = \alpha$ .

Task: Analyse Algorithm 1 in the Robertson-Webb model of computation. In particular, we are interested in how many operations are used. Your submission must contain a formal proof that your solution is correct.

Instructions

Read the task and solve it by yourself. In case of plagiarism, your homework will not be considered solved.
Then, send a scanned and hand-written solution as a single PDF file using MS Teams.
The deadline for submission is April 17, 2025, 23:59:00. The deadline is strict.