{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T01:12:39Z","timestamp":1787706759956,"version":"build-2784847793"},"reference-count":55,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>We consider a multiround 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 \u201cbest\u201d 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 deterministic 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.<\/jats:p>","DOI":"10.1137\/120878768","type":"journal-article","created":{"date-parts":[[2014,2,6]],"date-time":"2014-02-06T10:55:33Z","timestamp":1391684133000},"page":"194-230","source":"Crossref","is-referenced-by-count":24,"title":["Characterizing Truthful Multi-armed Bandit Mechanisms"],"prefix":"10.1137","volume":"43","author":[{"given":"Moshe","family":"Babaioff","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yogeshwer","family":"Sharma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksandrs","family":"Slivkins","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,2,6]]},"reference":[{"key":"atypb1","first-page":"1","author":"Aggarwal G.","year":"2006","journal-title":"New York"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"G. Aggarwal and S. Muthukrishnan,\n                      Tutorial on theory of sponsored search auctions\n                      , in IEEE Symposium on Foundations of Computer Science (FOCS), Philadelphia, PA, 2008.","DOI":"10.1109\/FOCS.2008.88"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"A. Archer and \u00c9. Tardos,\n                      Truthful mechanisms for one-parameter agents\n                      , in IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2001, pp. 482-491.","DOI":"10.1109\/SFCS.2001.959924"},{"key":"atypb4","unstructured":"S. Athey and I. Segal,\n                      An Efficient Dynamic Mechanism\n                      , http:\/\/www.stanford. edu\/\u02dcisegal\/agv.pdf (Mar. 2007)."},{"key":"atypb5","first-page":"2785","volume":"11","author":"Audibert J.Y.","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.016"},{"key":"atypb9","first-page":"43","author":"Babaioff M.","year":"2010","journal-title":"New York"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.08.002"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. Ben-Or and A. Hassidim,\n                      The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)\n                      , in IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2008, pp. 221-230.","DOI":"10.1109\/FOCS.2008.58"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"D. Bergemann and J. V\u00e4lim\u00e4ki,\n                      Bandit problems\n                      , in The New Palgrave Dictionary of Economics, 2nd ed., S. Durlauf and L. Blume, eds., Macmillan, Basingstoke, England, 2008.","DOI":"10.1057\/978-1-349-95121-5_2386-1"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"D. Bergemann and J. V\u00e4lim\u00e4ki,\n                      Efficient Dynamic Auctions\n                      , cowles.econ.yale.edu\/P\/cd\/d15b\/d1584.pdf (Oct. 2006).","DOI":"10.2139\/ssrn.936633"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"N. Cesa-Bianchi and G. Lugosi,\n                      Prediction, Learning, and Games\n                      , Cambridge University Press, Cambridge, 2006.","DOI":"10.1017\/CBO9780511546921"},{"key":"atypb15","unstructured":"T.M. Cover and J.A. Thomas,\n                      Elements of Information Theory\n                      , Wiley, New York, 1991."},{"key":"atypb16","first-page":"937","author":"Dani V.","year":"2006","journal-title":"Philadelphia"},{"key":"atypb17","first-page":"99","author":"Devanur N.","year":"2009","journal-title":"New York"},{"key":"atypb18","first-page":"38","author":"Dobzinski S.","year":"2008","journal-title":"New York"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1257\/aer.97.1.242"},{"key":"atypb20","first-page":"385","author":"Flaxman A.","year":"2005","journal-title":"Philadelphia"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.2307\/1402748"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"N. Gatti, A. Lazaric, and F. Trovo,\n                      A truthful learning mechanism for contextual multi-slot sponsored search auctions with externalities\n                      , in 13th ACM Conference on Electronic Commerce (EC), ACM, New York, 2012.","DOI":"10.1145\/2229012.2229057"},{"key":"atypb23","first-page":"38","author":"Hazan E.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb24","first-page":"34","author":"Immorlica N.","year":"2005","journal-title":"Berlin"},{"key":"atypb25","first-page":"1782211","author":"Kakade Sh.M.","year":"2011","journal-title":"SSRN"},{"key":"atypb26","first-page":"881","author":"Karp R.","year":"2007","journal-title":"Philadelphia"},{"key":"atypb27","first-page":"681","author":"Kleinberg R.","year":"2008","journal-title":"New York"},{"key":"atypb28","unstructured":"R. Kleinberg,\n                      Online Decision Problems with Large Strategy Sets\n                      , Ph.D. thesis, MIT, Cambridge, MA, 2005."},{"key":"atypb29","unstructured":"R. Kleinberg,\n                      Lecture Notes:CS683:Learning, Games, and Electronic Markets (Week 8)\n                      , http:\/\/www.cs.cornell.edu\/courses\/cs683\/2007sp\/lecnotes\/week8.pdf (Spring, 2007)."},{"key":"atypb30","unstructured":"R. Kleinberg,\n                      Lecture Notes:CS683:Learning, Games, and Electronic Markets (Week 9)\n                      , http:\/\/www.cs.cornell.edu\/courses\/cs683\/2007sp\/lecnotes\/week9.pdf (Spring, 2007)."},{"key":"atypb31","first-page":"699","author":"Lahaie S.","year":"2007","journal-title":"Cambridge"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(85)90002-8"},{"key":"atypb33","first-page":"817","author":"Langford J.","year":"2008","journal-title":"MA"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"R. Lavi, A. Mu'alem, and N. Nisan,\n                      Towards a characterization of truthful combinatorial auctions\n                      , in IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Angeles, CA, 2003, pp. 574-583.","DOI":"10.1109\/SFCS.2003.1238230"},{"key":"atypb35","first-page":"1146","author":"Lavi R.","year":"2005","journal-title":"Philadelphia"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.03.008"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"H. Nazerzadeh, A. Saberi, and R. Vohra,\n                      Dynamic cost-per-action mechanisms and applications to online advertising\n                      , in 17th International World Wide Web Conference (WWW), ACM, New York, 2008.","DOI":"10.1145\/1367497.1367522"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, eds.\n                      Algorithmic Game Theory\n                      , Cambridge University Press, Cambridge, 2007.","DOI":"10.1017\/CBO9780511800481"},{"key":"atypb42","first-page":"721","author":"Pandey S.","year":"2007","journal-title":"New York"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou, M. Schapira, and Y. Singer,\n                      On the hardness of being truthful\n                      , in IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2008, pp. 250-259.","DOI":"10.1109\/FOCS.2008.54"},{"key":"atypb45","first-page":"784","author":"Radlinski F.","year":"2008","journal-title":"Philadelphia"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90066-0"},{"key":"atypb47","unstructured":"T. Roughgarden,\n                      An algorithmic game theory primer\n                      , in IFIP International Conference on Theoretical Computer Science (TCS), Milan, Italy, 2008."},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"V. Shnayder, J. Hoon, D. Parkes, and V. Kawadia,\n                      Truthful prioritization schemes for spectrum sharing\n                      , in 7th Workshop on the Economics of Networks, Systems and Computation (NetEcon), Orlando, FL, 2012.","DOI":"10.1109\/INFCOMW.2012.6193489"},{"key":"atypb49","first-page":"343","author":"Slivkins A.","year":"2008","journal-title":"Finland"},{"key":"atypb50","unstructured":"A. Slivkins,\n                      Contextual bandits with similarity information\n                      , in 24th Conference on Learning Theory (COLT), Budapest, Hungary, 2011."},{"key":"atypb51","unstructured":"A. Slivkins,\n                      Monotone multi-armed bandit allocations\n                      , in 24th Conference on Learning Theory (COLT), Budapest, Hungary, 2011."},{"key":"atypb52","first-page":"1015","author":"Srinivas N.","year":"2010","journal-title":"New York"},{"key":"atypb53","first-page":"1577","author":"Streeter M.","year":"2008","journal-title":"Adv. Neural Inform. Process. Systems"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/25.3-4.285"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijindorg.2006.10.002"},{"key":"atypb56","first-page":"946","author":"Wilkens C.","year":"2012","journal-title":"New York"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120878768","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:59:58Z","timestamp":1787338798000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120878768"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/120878768"],"URL":"https:\/\/doi.org\/10.1137\/120878768","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}