Auctioning a cake: truthful auctions of heterogeneous divisible goods
Pages 1045 - 1052
Abstract
We consider the problem of auctioning a one-dimensional continuously-divisible heterogeneous good (a.k.a.~``the cake'') among multiple agents. Applications include auctioning of time intervals, e.g.~auctioning time for usage of a shared device, auctioning TV commercial slots, and more. Different agents may have different valuations for the different possible intervals, and the goal is to maximize the aggregate utility. Agents are self-interested and may misrepresent their true valuation functions, if this benefits them. Thus, we seek auctions that are truthful. Considering the case that each agent may obtain a single interval, the challenge is twofold, as we need to determine both where to slice the interval, and who gets which slice. The associated computational problem is NP-hard even under very restrictive assumptions. We consider two settings: discrete and continuous. In the discrete setting we are given a sequence of m indivisible elements (e1, ldots, e m), and the auction must allocate each agent a consecutive subsequence of the elements. For this setting we provide a truthful auctioning mechanism that approximates the optimal welfare to within a log m factor. The mechanism works for arbitrary monotone valuations. In the continuous setting we are given a continuous, infinitely divisible interval, and the auction must allocate each agent a sub-interval. The agents' valuations are non-atomic measures on the interval. For this setting we provide a truthful auctioning mechanism that approximates the optimal welfare to within a O(log n) factor (where n is the number of agents). Additionally, we provide a truthful 2-approximation mechanism for the case that all slices must be of some fixed size.
References
[1]
D. Abreu and H. Matsushima. Virtual implementation in iteratively undominated strategies: complete information. Econometrica: Journal of the Econometric Society, pages 993--1008, 1992.
[2]
Y. Aumann, Y. Dombb, and A. Hassidim. Computing socially-efficient cake divisions. In AAMAS, pages 343--350, 2013.
[3]
X. Bei, N. Chen, X. Hua, B. Tao, and E. Yang. Optimal proportional cake cutting with connected pieces. In AAAI, 2012.
[4]
S. J. Brams and A. D. Taylor. Fair Division: From cake cutting to dispute resolution. Cambridge University Press, New York, NY, USA, 1996.
[5]
J. Chen, A. Hassidim, and S. Micali. Robust perfect revenue from perfectly informed players. In ICS, pages 94--105, 2010.
[6]
Y. Chen, J. Lai, D. C. Parkes, and A. D. Procaccia. Truth, justice, and cake cutting. In AAAI, 2010.
[7]
Y. Chevaleyre, P. E. Dunne, U. Endriss, J. Lang, M. Lemaitre, N. Maudet, J. Padget, S. Phelps, J. A. Rodriguez-Aguilar, and P. Sousa. Issues in multiagent resource allocation. Informatica (Slovenia), 30(1):3--31, 2006.
[8]
P. Cramton. The fcc spectrum auctions: An early assessment. Journal of Economics & Management Strategy, 6(3):431--495, 1997.
[9]
P. Cramton, Y. Shoham, and R. Steinberg. Combinatorial auctions. MIT Press, 2006.
[10]
S. Dobzinski and N. Nisan. Limitations of vcg-based mechanisms. In STOC, pages 338--344, 2007.
[11]
J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, 19(2):248--264, Apr. 1972.
[12]
R. J. Gibbens and F. P. Kelly. Resource pricing and the evolution of congestion control. Automatica, 35(12):1969--1985, 1999.
[13]
M. Guo and V. Conitzer. Strategy-proof allocation of multiple items between two agents without payments or priors. In AAMAS, pages 881--888, 2010.
[14]
L. Han, C. Su, L. Tang, and H. Zhang. On strategy-proof allocation without payments or priors. In WINE, volume 7090 of Lecture Notes in Computer Science, pages 182--193, 2011.
[15]
R. Johari and J. N. Tsitsiklis. Efficiency of scalar-parameterized mechanisms. Operations Research, 57:823--839, July-August 2009.
[16]
I. Kremer and K. G. Nyborg. Divisible-good auctions: The role of allocation rules. RAND Journal of Economics, pages 147--159, 2004.
[17]
B. Lehmann, D. J. Lehmann, and N. Nisan. Combinatorial auctions with decreasing marginal utilities. In ACM Conference on Electronic Commerce, pages 18--28. ACM, 2001.
[18]
R. T. Maheswaran and T. Basar. Nash equilibrium and decentralized negotiation in auctioning divisible resources. Group Decision and Negotiation, 13:2003, 2003.
[19]
A. Maya and N. Nisan. Incentive compatible two player cake cutting. In WINE, volume 7695 of Lecture Notes in Computer Science, pages 170--183. Springer, 2012.
[20]
E. Mossel and O. Tamuz. Truthful fair division. In Algorithmic Game Theory, pages 288--299. Springer, 2010.
[21]
N. Nisan. Bidding and allocation in combinatorial auctions. In ACM Conference on Electronic Commerce, pages 1--12, 2000.
[22]
N. Nisan, J. Bayer, D. Chandra, T. Franji, R. Gardner, Y. Matias, N. Rhodes, M. Seltzer, D. Tom, H. Varian, and D. Zigmond. Google's auction for tv ads. In Automata, Languages and Programming, volume 5556 of Lecture Notes in Computer Science, pages 309--327. Springer Berlin Heidelberg, 2009.
[23]
N. Nisan and A. Ronen. Algorithmic mechanism design (extended abstract). In STOC, pages 129--140, 1999.
[24]
N. Nisan and A. Ronen. Computationally feasible vcg mechanisms. In ACM Conference on Electronic Commerce, pages 242--252, 2000.
[25]
N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007.
[26]
A. D. Procaccia. Cake cutting: not just child's play. Communications of the ACM, 56(7):78--87, 2013.
[27]
J. Robertson and W. Webb. Cake-cutting algorithms: Be fair if you can. A K Peters, Ltd., Natick, MA, USA, 1998.
[28]
M. H. Rothkopf, A. Pekeč, and R. M. Harstad. Computationally manageable combinational auctions. Management Science, 44(8):1131--1147, 1998.
[29]
M. Tennenholtz. Some tractable combinatorial auctions. In AAAI/IAAI, pages 98--103, 2000.
[30]
S. Yang and B. Hajek. Vcg-kelly mechanisms for allocation of divisible goods: Adapting vcg mechanisms to one-dimensional signals. Selected Areas in Communications, IEEE Journal on, 25(6):1237--1243, 2007.
Index Terms
- Auctioning a cake: truthful auctions of heterogeneous divisible goods
Recommendations
Auctioning Time: Truthful Auctions of Heterogeneous Divisible Goods
We consider the problem of auctioning time - a one-dimensional continuously-divisible heterogeneous good - among multiple agents. Applications include auctioning time for using a shared device, auctioning TV commercial slots, and more. Different agents ...
Fairness and False-Name Manipulations in Randomized Cake Cutting
AAMAS '15: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent SystemsCake cutting has been recognized as a fundamental model in fair division and several envy-free cake cutting algorithms have been proposed Recent works from the computer science field proposed novel mechanisms for cake cutting, whose approaches are based ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2014
1774 pages
ISBN:9781450327381
- General Chairs:
- Ana Bazzan,
- Michael Huhns,
- Program Chairs:
- Alessio Lomuscio,
- Paul Scerri
Sponsors
- IFAAMAS
In-Cooperation
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 05 May 2014
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
AAMAS '14
Sponsor:
AAMAS '14: International conference on Autonomous Agents and Multi-Agent Systems
May 5 - 9, 2014
Paris, France
Acceptance Rates
AAMAS '14 Paper Acceptance Rate 169 of 709 submissions, 24%;
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 82Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in