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.
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.
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
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