Cake Cutting Algorithms

Abstract

Introduction Imagine a cake that must be divided between a group of gluttonous children. To complicate matters, the cake is heterogeneous : two pieces of cake may differ in terms of their toppings, so the children have different preferences over the pieces (one may prefer a larger proportion of chocolate curls, while another may single-mindedly desire the piece with the cherry). In this chapter we discuss the surprisingly intricate problem of fairly dividing the cake—which serves as a metaphor for heterogeneous divisible resources such as land or time. The cake cutting problem has a long and storied history described, for example, in the books by Brams and Taylor (1996) and Robertson and Webb (1998). The early research on the problem has two main themes: existence results showing that certain fairness guarantees can be achieved; and algorithmic results showing how such guarantees can be achieved. The focus of this chapter is on the latter theme, which has a more computational flavor. From a computer scientist's point of view, the cake cutting problem provides a sandbox in which we can explore the role of computational thinking in the allocation of divisible goods. Indeed, the elegant cake cutting model (Section 13.2) distills many of the issues we care about when studying divisible goods more broadly; for example, how to reason about computational complexity in the face of continuous inputs, and how to quantify the trade-offs between individual fairness and global welfare. The Model Our setting includes a set of agents denoted N = {1 , …, n }, and a heterogeneous divisible good—the cake —represented by the interval [0, 1]. We assume that each agent i ∈ N is endowed with a valuation function V i , which maps a given subinterval I ⊆ [0, 1] to the value assigned to it by agent i , V i ( I ). We also write V i ( x, y ) as a shorthand for V i ([ x, y ]). These valuation functions are assumed to satisfy several conditions, for every i ∈ N : • Normalization: V i (0, 1) = 1. • Divisibility: For every subinterval [ x, y ] and 0 ≤ λ ≤ 1 there exists a point z ∈ [ x, y ] such that V i ( x, z ) = λV i ( x, y ). • Nonnegativity: For every subinterval I , V i ( I ) ≥ 0.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 127 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.