Abstract
I construct a class of strategy-proof and Pareto efficient mechanisms of cake cutting in the context of offline interval scheduling. Motivating applications include the circulation of the single copy of a book owned by a public library among all self-interested and rational potential players with piecewise uniform value densities over continuous time intervals. This class of mechanisms accommodate both anonymous and non-anonymous configurations and can serve as a flexible platform to implement allocations of heterogeneous goods according to distributional objectives such as arbitrary guaranteed shares of reported demand.
The cake-cutting literature has recently made significant progress toward a better understanding of strategy-proofness. Two-person incentive compatible cake-cutting problems were studied by Maya and Nisan in [1], while Mossel and Tamuz in [2] and Chen et al. in [3] proposed solutions to such problems with any arbitrary number of players, with the former focusing on stochastic mechanisms. A more recent paper [4] by Aziz and Ye discussed various cake-cutting algorithms for piecewise constant and piecewise uniform value densities and examined the compatibility of Pareto efficiency, strategy-proofness, and fairness. Procaccia [5] contains a great introduction to the cake-cutting literature including the issue of strategy-proofness. A wonderful review of classical cake-cutting algorithms focusing on fairness issues can be found in Procaccia [6].
This paper proposes a class of mechanisms generalizing the strategy-proof, Pareto efficient, and envy-free mechanism developed in [3] by temporarily compromising on fairness. Representing the mechanism design problem as a constrained optimization problem, I manage to characterize all feasible cuts of the cake with a collection of linear constraints regarding the maximum total payoffs of any subset of players by slightly generalizing the network-flow proof in [3]. More importantly, I demonstrate that strategy-proofness can be obtained from the additivity and concavity of the social planner’s (in this case, the library’s) utility in terms of the payoffs of the players (the readers). The essential result in constructing strategy-proofness is a non-inferiority condition that roughly states the following: when a player increases her demand to a superset of her original demand, a specific group—depending on the identity of the player changing her report—of players will all be allocated (weakly) larger pieces.
Partially relaxing the fairness requirement suggests some interesting and potentially positive extensions of the current literature. In the context of scheduling, maintaining piecewise uniform valuations, the allocation of a certain resource (the book, in this case) at an early instant should not depend on the report of players who arrive at a later time, suggesting a type of dynamic consistency as a necessity in the design of online cake-cutting mechanisms. Such dynamic consistencies may be incompatible with fairness. In addition, under piecewise constant valuations, the incompatibility of strategy-proofness and even weaker notions of fairness than envy-freeness, such as equal-treatment-of-equals, has been widely documented in both computer science (see [4]) and economics (see Zhou [9]) literature. Earlier works including [10] by Bogomolnaia and Moulin focus on maintaining fairness by mildly yielding on strategy-proofness. The mechanisms developed in this paper provide an adaptable potential platform upon which strategy-proof and Pareto efficient mechanisms, while unable to achieve envy-freeness, can be developed to perform better on fairness than simple mechanisms such as random serial dictatorship.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Maya, A., Nisan, N.: Incentive compatible two player cake cutting. In: Goldberg, P.W. (ed.) WINE 2012. LNCS, vol. 7695, pp. 170–183. Springer, Heidelberg (2012)
Mossel, E., Tamuz, O.: Truthful fair division. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 288–299. Springer, Heidelberg (2010)
Chen, Y., Lai, J.K., Parkes, D.C., Procaccia, A.D.: Truth, justice, and cake cutting. Games and Economic Behavior 77(1), 284–297 (2013)
Aziz, H., Ye, C.: Cake cutting algorithms for piecewise constant and piecewise uniform valuations. ArXiv E-Prints (September 2013)
Procaccia, A.D.: Cake cutting: Not just child’s play. Communications of the ACM 56(7), 78–87 (2013)
Procaccia, A.D.: 13. Cake Cutting Algorithms. In: Handbook of Computational Social Choice. Cambridge University Press (2014)
Quah, J.K.H.: The comparative statics of constrained optimization problems. Econometrica 75(2), 401–431 (2007)
Walsh, T.: Online cake cutting. In: Algorithmic Decision Theory, pp. 292–305. Springer (2011)
Zhou, L.: On a conjecture by gale about one-sided matching problems. Journal of Economic Theory 52(1), 123–135 (1990)
Bogomolnaia, A., Moulin, H.: A new solution to the random assignment problem. Journal of Economic Theory 100(2), 295–328 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tian, Y. (2013). Strategy-Proof and Efficient Offline Interval Scheduling and Cake Cutting. In: Chen, Y., Immorlica, N. (eds) Web and Internet Economics. WINE 2013. Lecture Notes in Computer Science, vol 8289. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45046-4_36
Download citation
DOI: https://doi.org/10.1007/978-3-642-45046-4_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45045-7
Online ISBN: 978-3-642-45046-4
eBook Packages: Computer ScienceComputer Science (R0)