Documents

Cake Cutting

Categories
Published
of 47
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Related Documents
Share
Description
Cake cutting paper
Transcript
  University of Auckland Department of Computer ScienceDepartment of Philosophy Cake Cutting Mechanisms Author: Egor Ianovski Supervisor: Dr. Mark C. WilsonSubmitted in partial fulfilment of the requirements of the degree of BSc(Hons) inLogic and Computation, 19 October 2011. Last updated 2 March 2012.   a  r   X   i  v  :   1   2   0   3 .   0   1   0   0  v   1   [  c  s .   G   T   ]   1   M  a  r   2   0   1   2  Abstract We examine the history of cake cutting mechanisms and discuss the efficiency of theirallocations. In the case of piecewise uniform preferences, we define a game that in thepresence of strategic agents has equilibria that are not dominated by the allocations of any mechanism. We identify that the equilibria of this game coincide with the allocationsof an existing cake cutting mechanism.  Contents 1 Introduction 1 1.1 To Cut a Cake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Outline of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2.1 Our Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 A Framework for Cake Cutting 3 2.1 The Cake Cutting Situation . . . . . . . . . . . . . . . . . . . . . . . . . . 32.1.1 Restricted Preferences . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Properties of Allocations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3.1 Moving Knife Protocols . . . . . . . . . . . . . . . . . . . . . . . . 82.3.2 Robertson-Webb Protocols . . . . . . . . . . . . . . . . . . . . . . 82.3.3 Revelation Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . 92.3.4 Behavioural Assumptions . . . . . . . . . . . . . . . . . . . . . . . 10 3 Literature Review 12 3.1 Origins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.2 Envy Free Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.3 Query Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.4 Cutting Pies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.5 The Price of Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.6 Truthful Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Efficiency of Allocations 22 4.1 Utilitarian Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.1.1 Non-Existence of Mechanisms . . . . . . . . . . . . . . . . . . . . . 244.2 Egalitarian Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.2.1 Non-Existence of Mechanisms . . . . . . . . . . . . . . . . . . . . . 26 5 Strategic Cake Cutting 28 5.1 Two Non-Wasteful Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . 285.2 Length Game and its Equilibria . . . . . . . . . . . . . . . . . . . . . . . . 295.3 Characterisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34i  6 Conclusion 36A Table of Mechanisms 37B Robertson-Webb Formulations 38 ii
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks