acm-header
Sign In

Communications of the ACM

Research highlights

A Bounded and Envy-Free Cake Cutting Algorithm


slices of cake

Credit: Getty Images

We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation of a divisible resource based on queries from agents. The problem has received attention in mathematics, economics, and computer science. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We report on our algorithm that resolved the open problem.

Back to Top

1. Introduction

The cake cutting problem is a fundamental mathematical problem in which the 'cake' is a metaphor for a heterogeneous divisible resource represented by the unit interval [0, 1].4 The resource could represent time, land, or some computational resources. The goal is to allocate the cake among n entities that are referred to as 'agents.' Each agent's allocation consists of a collection of subintervals. Each of the agents is assumed to have additive and nonnegative valuations over segments of the interval. A cake-cutting algorithm/protocol interacts with the agents in order to identify a fair allocation.

One of the most important criteria for fairness is envy-freeness. An agent envies another if she would have preferred to receive the other's piece rather than hers. A cake cutting protocol/algorithm is called envy-free if each agent is guaranteed to be nonenvious if she reports her real valuations. If a protocol is envy-free, then an honest agent will not be envious even if other agents misreport their valuations.


Comments


Nandakumar Ramanathan

References to relevant publications on at least two of the following related problems may please be included and also their relationships to the current context included possibly as annexures. 1. Optimal packing of tiles/packets in a given area/volume (Graph Theory applications) and 2. Minimising the areas of sliver polygons in a Geographical Information System. - Dr. R. Nandakumar (r_nand) aka Nandakumar Ramanathan


Nandakumar Ramanathan

To add to the footnotes point 'a', in my opinion, if there are a few cream-swirls and/or cherries on top of the cake; and their total number is less than the number of agents aspiring to get a piece, there will not be any viable envy-free solution to the problem. - Dr. R. Nandakumar (r_nand) aka Nandakumar Ramanathan


Displaying all 2 comments

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.
  

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account