Characterizing truthful multi-armed bandit mechanisms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Characterizing truthful multi-armed bandit mechanisms: extended abstract

Full text

Pdf (493 KB)

Source

Electronic Commerce archive
Proceedings of the tenth ACM conference on Electronic commerce table of contents

Stanford, California, USA

SESSION: Session 3 table of contents

Pages 79-88

Year of Publication: 2009

ISBN:978-1-60558-458-4

Authors

Moshe Babaioff	Microsoft Research, Mountain View, CA, USA
Yogeshwer Sharma	Cornell University, Ithaca, NY, USA
Aleksandrs Slivkins	Microsoft Research, Mountain View, CA, USA

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 33, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1566374.1566386 What is a DOI?

ABSTRACT

We consider a multi-round auction setting motivated by pay-per-click auctions for Internet advertising. In each round the auctioneer selects an advertiser and shows her ad, which is then either clicked or not. An advertiser derives value from clicks; the value of a click is her private information. Initially, neither the auctioneer nor the advertisers have any information about the likelihood of clicks on the advertisements. The auctioneer's goal is to design a (dominant strategies) truthful mechanism that (approximately) maximizes the social welfare.

If the advertisers bid their true private values, our problem is equivalent to the multi-armed bandit problem, and thus can be viewed as a strategic version of the latter. In particular, for both problems the quality of an algorithm can be characterized by regret, the difference in social welfare between the algorithm and the benchmark which always selects the same "best" advertisement. We investigate how the design of multi-armed bandit algorithms is affected by the restriction that the resulting mechanism must be truthful. We find that truthful mechanisms have certain strong structural properties -- essentially, they must separate exploration from exploitation -- and they incur much higher regret than the optimal multi-armed bandit algorithms. Moreover, we provide a truthful mechanism which (essentially) matches our lower bound on regret.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Conf. on Learning Theory (COLT), pages 263--274, 2008.
	2	Gagan Aggarwal , Ashish Goel , Rajeev Motwani, Truthful auctions for pricing search keywords, Proceedings of the 7th ACM conference on Electronic commerce, p.1-7, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134708]
	3	Gagan Aggarwal , S. Muthukrishnan, Theory of Sponsored Search Auctions, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.7, October 25-28, 2008 [doi>10.1109/FOCS.2008.88]
	4	A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
	5	Susan Athey and Ilya Segal. An efficient dynamic mechanism. Available from http://www.stanford.edu/~isegal/agv.pdf, March 2007.
	6	Peter Auer , Nicolò Cesa-Bianchi , Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning, v.47 n.2-3, p.235-256, May-June 2002 [doi>10.1023/A:1013689704352]
	7	Peter Auer , Nicolò Cesa-Bianchi , Yoav Freund , Robert E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing, v.32 n.1, p.48-77, 2003 [doi>10.1137/S0097539701398375]
	8	Moshe Babaioff, Yogeshwer Sharma, and Aleksandrs Slivkins. Characterizing Truthful Multi-Armed Bandit Mechanisms. Technical Report http://arxiv.org/abs/0812.2291, December 2008. Minor revision February 2009.
	9	Peter L. Bartlett, Varsha Dani, Thomas Hayes, Sham Kakade, Alexander Rakhlin, and Ambuj Tewari. High-probability regret bounds for bandit online linear optimization. In Conf. on Learning Theory (COLT), pages 335--342, 2008.
	10	Michael Ben-Or , Avinatan Hassidim, The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well), Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.221-230, October 25-28, 2008 [doi>10.1109/FOCS.2008.58]
	11	Dirk Bergemann and Juuso Välimäki. Efficient dynamic auctions. Available from cowles.econ.yale.edu/P/cd/d15b/d1584.pdf, October 2006.
	12	Donald Berry and Bert Fristedt. Bandit problems: sequential allocation of experiments. Chapman&Hall, 1985.
	13	Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
	14	Varsha Dani , Thomas P. Hayes, Robbing the bandit: less regret in online geometric optimization against an adaptive adversary, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.937-943, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109660]
	15	Nikhil R. Devanur , Sham M. Kakade, The price of truthfulness for pay-per-click auctions, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA [doi>10.1145/1566374.1566388]
	16	Shahar Dobzinski , Mukund Sundararajan, On characterizations of truthful mechanisms for combinatorial auctions and scheduling, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386798]
	17	Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242--259, March 2007.
	18	J.C. Gittins. Multi-Armed Bandit Allocation Indices. John Wiley&Sons, 1989.
	19	Rica Gonen , Elan Pavlov, An incentive-compatible multi-armed bandit mechanism, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281174]
	20	Nicole Immorlica, Kamal Jain, Mohammad Mahdian, and Kunal Talwar. Click fraud resistant methods for learning click-through rates. In Intl. Workshop On Internet And Network Economics (WINE), pages 34--45, 2005.
	21	Richard M. Karp , Robert Kleinberg, Noisy binary search and its applications, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.881-890, January 07-09, 2007, New Orleans, Louisiana
	22	Robert Kleinberg. Lecture notes: CS683: Learning, Games, and Electronic Markets (week 8), Spring 2007. Available at http://www.cs.cornell.edu/courses/cs683/2007sp.
	23	Robert Kleinberg. Lecture notes: CS683: Learning, Games, and Electronic Markets (week 9), Spring 2007. Available at http://www.cs.cornell.edu/courses/cs683/2007sp.
	24	Robert Kleinberg , Aleksandrs Slivkins , Eli Upfal, Multi-armed bandits in metric spaces, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374475]
	25	Sebastien Lahaie, David M. Pennock, Amin Saberi, and Rakesh V. Vohra. In N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds.) Chapter 28, Sponsored search auctions. Cambridge University Press., 2007.
	26	T.L. Lai and Herbert Robbins. Asymptotically efficient Adaptive Allocation Rules. Advances in Applied Mathematics, 6:4--22, 1985.
	27	Ron Lavi , Ahuva Mu'alem , Noam Nisan, Towards a Characterization of Truthful Combinatorial Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.574, October 11-14, 2003
	28	Ron Lavi , Noam Nisan, Online ascending auctions for gradually expiring items, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	29	Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and generalized online matching, Journal of the ACM (JACM), v.54 n.5, p.22-es, October 2007 [doi>10.1145/1284320.1284321]
	30	Roger B. Myerson. Optimal Auction Design. Mathematics of Operations Research, 6:58--73, 1981.
	31	Hamid Nazerzadeh , Amin Saberi , Rakesh Vohra, Dynamic cost-per-action mechanisms and applications to online advertising, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367522]
	32	N. Nisan and A. Ronen. Algorithmic Mechanism Design. Games and Economic Behavior, 35(1-2):166--196, 2001.
	33	Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
	34	Christos Papadimitriou , Michael Schapira , Yaron Singer, On the Hardness of Being Truthful, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.250-259, October 25-28, 2008 [doi>10.1109/FOCS.2008.54]
	35	Tim Roughgarden. An algorithmic game theory primer. IFIP International Conference on Theoretical Computer Science (TCS). An invited survey., 2008.
	36	Hal R. Varian. Position auctions. International Journal of Industrial Organization, 25(6):1163--1178, December 2007.