2015/08/20 by Haris Aziz, Simon Mackenzie, Aziz, Haris +1 · 2 citations
Computer Science · Decision Sciences · #68Q15 #91A12 #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #J.4 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1508.05143
openalex publication_date 2015/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the well-studied cake cutting problem in which the goal is to identify a fair allocation based on a minimal number of queries from the agents. The problem has attracted considerable attention within various branches of computer science, mathematics, and economics. Although, the elegant Selfridge-Conway envy-free protocol for three agents has been known since 1960, it has been a major open problem for the last fifty years to obtain a bounded envy-free protocol for more than three agents. We propose a discrete and bounded envy-free protocol for four agents.