2 hours ago
Envy-free cake-cutting
Summary
Envy-free cake-cutting is a classical problem in fair division and game theory that seeks to partition a heterogeneous resource (the "cake") among $n$ participants such that every individual considers their assigned portion to be at least as valuable as anyone else's, eliminating any subjective envy. While two-player divisions are easily resolved using the ancient "divide and choose" method, the problem becomes significantly more complex for three or more participants.
Research splits into two main variants: connected pieces, where each person receives a single continuous slice, and general pieces, where shares can consist of multiple disjoint fragments. Although an envy-free division with connected pieces is mathematically guaranteed to exist under mild conditions, provably no finite protocol exists to compute it for three or more partners; in contrast, for general pieces, finite bounded algorithms do exist—such as the landmark discrete protocol developed by Haris Aziz and Simon Mackenzie—though determining the exact runtime complexity remains an open question in computer science.
ARTICLE
Summary
Envy-free cake-cutting is a classical problem in fair division and game theory that seeks to partition a heterogeneous resource (the "cake") among $n$ participants such that every individual considers their assigned portion to be at least as valuable as anyone else's, eliminating any subjective envy. While two-player divisions are easily resolved using the ancient "divide and choose" method, the problem becomes significantly more complex for three or more participants.
Research splits into two main variants: connected pieces, where each person receives a single continuous slice, and general pieces, where shares can consist of multiple disjoint fragments. Although an envy-free division with connected pieces is mathematically guaranteed to exist under mild conditions, provably no finite protocol exists to compute it for three or more partners; in contrast, for general pieces, finite bounded algorithms do exist—such as the landmark discrete protocol developed by Haris Aziz and Simon Mackenzie—though determining the exact runtime complexity remains an open question in computer science.
ARTICLE
┌────────────────────────────────┐
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘