No, Cake Cutting Really is a Piece of Cake

Jul 16, 2026

Designs and analyzes a deterministic cake cutting algorithm that guarantees proportional fairness while using a linear number of cuts. Compares prior deterministic guarantees, where the best known upper bound is O(n log n) cuts from the Even–Paz divide-and-conquer approach. Addresses the long-standing conjecture that O(n log n) is optimal for deterministic algorithms, and develops the formal problem model and query framework used to prove cut-efficiency results.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages13

Reading Time33 min

Introduction

Problem Statement

Essential Background

No, Cake Cutting Really is a Piece of Cake Stephen Arndt∗ Benjamin Moseley† Sungjin Im‡ Kirk Pruhs§ July 13, 2026 arXiv :2606 .07238v2 [ cs .GT] 9 Jul 2026 Abstract We design and analyze a deterministic cake cutting algorithm that achieves proportional fairness using a linear number of cuts. The best previous upper bound on the number of cuts for a deterministic algorithm was O (nlog n), which was obtained by a natural divide-and-conquer algorithm due to Even and Paz. It has long been conjectured that O (nlog n) cuts was optimal for a deterministic algorithm. 1 Introduction 1.1 Problem Statement Intuitively cake cutting problems involve n self-interested players who want to divide a divisible resource, such as a cake. Here we consider achieving the objective of proportional fairness in the standard RobertsonWebb model [RW98, WS07] . So formally an instance of the cake cutting problem consists of n value functions µ 1 ,...,µn , where each µp is from the unit interval (0 , 1) to the nonnegative reals, and where R1x=0 µp (x)dx = 1 . Intuitively the unit interval is the cake, and Vp (a, b) =Rbx=a µp (x)dx is how much player p values the portion (a, b) of the cake. A feasible solution is a partition of the cake, and a proportionally fair assignment of the pieces to the players, that is each player must be assigned a part of the cake that is of value at least ~~1~~n to them. Each part in the standard algorithms is a subinterval, but this is not a requirement of the problem, and more generally a part could be the union of subintervals. The algorithm does not initially know the value functions, and can only learn information about the value functions by querying the players. The most important type of query is the Cut query, which is of the form Cutp (α), where p is a player and α ∈ [0 , 1] is a value. The expected response from p is the cut point y such that Vp (0, y) = α . The second type of query isan evaluation query Ep (y), which consists of a player p and a point y that was some player’s (not necessarily player p) response to a prior cut query, and the expected response from player p is Vp (0, y) . Initially it will be convenient to assume that all players always answer truthfully, and that for all players p and positions a and b it is the case that Vp (a, b) > 0. 1.2 Essential Background The cake cutting literature is quite large, including several books and surveys dedicated to the topic [RW98, Pro16 , BT96] . Here we just cover the results that are most essential for our purposes, starting with the standard algorithms for proportional fairness. In the 1940s Banach and Knaster designed a deterministic algorithm, sometimes called the Last Diminisher algorithm, that uses O (n2 ) cuts, and this algorithm was communicated by Steinhaus in 1948 [Ste48] . This algorithm uses n cuts to find the player p that most values the left portion of the cake, more precisely p = arg minq Cutq ( ~~1~~n) . Player p is then assigned the piece 􀀀0, Cutp 􀀀 ~~1~~n􀀁􀀁 of the cake. The algorithm then recurses on the rest of the players and the remaining unassigned portion of the cake. Steinhaus [Ste48] noted that: ∗ Carnegie Mellon University, Tepper School of Business. †Carnegie Mellon University, Tepper School of Business. ‡University of California, Santa Cruz. Supported in part by NSF grant CCF-2423106 . § University of Pittsburgh. Supported in part by NSF grant CCF-2209654 . “Interesting mathematics arise if we are to determine the minimal number of cuts necessary for fair division.” In 1984 Even and Paz designed a deterministic divide-and-conquer algorithm that uses O(nlog n) cuts [EP84] . Even and Paz’s algorithm uses n cuts to determine a split position y, and the n/2 players L that will appear in the first half in the left-to-right order of the pieces, and the n/2 players R that will appear in the second half of the left-to-right order of the pieces. The algorithm then recurses to determine how the players in L divi

FAQs

What fairness goal does the proposed cake cutting algorithm achieve?

It achieves proportional fairness, ensuring each player receives a piece they value at least 1/n.

What is the standard model and how does the algorithm learn player preferences?

The algorithm uses the Robertson–Webb model and learns information by querying players, primarily through Cut queries that return cut points for specified value levels.

How many cuts does the new deterministic algorithm use compared with earlier work?

The algorithm uses a linear number of cuts, improving on the best previous deterministic upper bound of O(n log n) derived from Even and Paz’s approach.

Jul 16, 2026

Upload by Olivia Brown