Cake Cutting Algorithms: Truth, Justice, and Fairness
Discover the intricate world of cake cutting algorithms, exploring concepts such as truthfulness, envy-freeness, and proportionality. Delve into deterministic and randomized algorithms designed to achieve fair and efficient cake divisions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
1 TRUTH, JUSTICE, AND CAKE CUTTING Yiling Chen, John K. Lai, David C. Parkes, Ariel D. Procaccia (Harvard SEAS)
Truth, justice, and cake cutting 2 Division of a heterogeneous divisible good The cake is the interval [0,1] Set of agents N={1,...,n} Each agent has a valuation function Vi over pieces of cake Additive: if X Y= then Vi(X)+Vi(Y) = Vi(X Y) i N, Vi(0,1) = 1 Find an allocation A1,...,An
Truth, justice, and cake cutting 3 Proportionality: i N, Vi(Ai) 1/n Envy-freeness: i,j N, Vi(Ai) Vi(Aj) Assuming free disposal the two properties are incomparable Envy-free but not proportional: throw away cake Proportional but not envy-free 1/3 1/2 1 1/6 1
Truth, justice, and cake cutting 4 Previous work considered strategyproof cake cutting [Brams, Jones & Klamler 2006, 2008] Their notion: agents report the truth if there exist valuations for others s.t. agent does not gain by lying Truthful algorithm = truthfulness is a dominant strategy
Deterministic algorithms 5 Goal: design truthful, envy free, proportional, and tractable cake cutting algorithms Requires restricting the valuation functions Lower bounds for envy-free cake cutting [Procaccia, 2009] Valuation Vi is piecewise uniform if agent i is uniformly interested in a piece of cake Theorem: assume that the agents have piecewise uniform valuations, then there is a deterministic alg that is truthful, proportional, envy-free, and polynomial-time Related to work in econ on the random assignment problem [Bogomolnaia & Moulin 2004]
Randomized algorithms 6 A randomized alg is universally envy-free (resp., universally proportional) if it always returns an envy-free (resp., proportional) allocation A randomized alg is truthful in expectation if an agent cannot gain in expectation by lying Looking for universal fairness and truthfulness in expectation Does it make sense to look for fairness in expectation and universal truthfulness?
Nobodys perfect 7 A partition X1,...,Xn is perfect if for every i,k, Vi(Xk)=1/n Algorithm: Find a perfect partition X1,...,Xn Give each player a random piece Observation (see also [Mossel&Tamuz 2010]): alg is truthful in expectation, universally EF and universally proportional Proof: if agent i lies it may lead to a partition Y1,...,Yn, but k (1/n)Vi(Yk) = (1/n) k Vi(Yk) = 1/n It is known that a perfect partition always exists [Alon 1987] Lemma: if agents have piecewise linear valuations then a perfect partition can be found in poly time 1. 2.
Discussion 8 Conceptual contributions Truthful cake cutting Restricted valuation functions and tractable algorithms Current work with Ioannis Caragiannis and John Lai: piecewise uniform with a minimum Envy freeness and system performance? Cake cutting is awesome!
