{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T18:53:25Z","timestamp":1725648805489},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T00:00:00Z","timestamp":1430870400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation Fellowship","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Microsoft Research New Faculty Fellowship"},{"name":"NSF","award":["CCF-0643934 and AF-0910940"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,5,6]]},"abstract":"\n It is widely believed that computing payments needed to induce truthful bidding is somehow harder than simply computing the allocation. We show that the opposite is true: creating a randomized truthful mechanism is essentially as easy as a\n single<\/jats:italic>\n call to a monotone allocation rule. Our main result is a general procedure to take a monotone allocation rule for a single-parameter domain and transform it (via a black-box reduction) into a randomized mechanism that is truthful in expectation and individually rational for every realization. The mechanism implements the same outcome as the original allocation rule with probability arbitrarily close to 1, and requires evaluating that allocation rule only once. We also provide an extension of this result to multiparameter domains and cycle-monotone allocation rules, under mild star-convexity and nonnegativity hypotheses on the type space and allocation rule, respectively.\n <\/jats:p>\n Because our reduction is simple, versatile, and general, it has many applications to mechanism design problems in which re-evaluating the allocation rule is either burdensome or informationally impossible. Applying our result to the multiarmed bandit problem, we obtain truthful randomized mechanisms whose regret matches the information-theoretic lower bound up to logarithmic factors, even though prior work showed this is impossible for truthful deterministic mechanisms. We also present applications to offline mechanism design, showing that randomization can circumvent a communication complexity lower bound for deterministic payments computation, and that it can also be used to create truthful shortest path auctions that approximate the welfare of the VCG allocation arbitrarily well, while having the same running time complexity as Dijkstra's algorithm.<\/jats:p>","DOI":"10.1145\/2724705","type":"journal-article","created":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T16:30:57Z","timestamp":1431361857000},"page":"1-37","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Truthful Mechanisms with Implicit Payment Computation"],"prefix":"10.1145","volume":"62","author":[{"given":"Moshe","family":"Babaioff","sequence":"first","affiliation":[{"name":"Microsoft Research, Herzliya, Israel"}]},{"given":"Robert D.","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}]},{"given":"Aleksandrs","family":"Slivkins","sequence":"additional","affiliation":[{"name":"Microsoft Research, Avenue of the Americas, New York, NY"}]}],"member":"320","published-online":{"date-parts":[[2015,5,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1486877.1486882"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386796"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644144"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 482--491","author":"Aaron","unstructured":"Aaron Archer and \u00c9va Tardos. 2001. Truthful mechanisms for one-parameter agents . In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 482--491 . Aaron Archer and \u00c9va Tardos. 2001. Truthful mechanisms for one-parameter agents. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 482--491."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA8882"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA6995"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1953023"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2012.08.007"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807349"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482602"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566386"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133093"},{"key":"e_1_2_1_15_1","volume-title":"Wiley Encyclopedia of Operations Research and Management Science","author":"Bergemann Dirk","unstructured":"Dirk Bergemann and Maher Said . 2011. Dynamic auctions: A survey . In Wiley Encyclopedia of Operations Research and Management Science , vol. 2 , Wiley , New York , 1511--1522. Dirk Bergemann and Maher Said. 2011. Dynamic auctions: A survey. In Wiley Encyclopedia of Operations Research and Management Science, vol. 2, Wiley, New York, 1511--1522."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA7260"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2014.04.011"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.88"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 24nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 578--595","author":"Cai Yang","unstructured":"Yang Cai , Constantinos Daskalakis , and S. Matthew Weinberg . 2013a. Reducing revenue to welfare maximization: Approximation algorithms and other generalizations . In Proceedings of the 24nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 578--595 . Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. 2013a. Reducing revenue to welfare maximization: Approximation algorithms and other generalizations. In Proceedings of the 24nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 578--595."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.72"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214019"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Constantinos Daskalakis and S. Matthew Weinberg. 2014. Bayesian truthful Mechanisms for job scheduling from bi-criterion approximation algorithms. arXiv:1405.5940. Constantinos Daskalakis and S. Matthew Weinberg. 2014. Bayesian truthful Mechanisms for job scheduling from bi-criterion approximation algorithms. arXiv:1405.5940.","DOI":"10.1137\/1.9781611973730.130"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566388"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.42"},{"key":"e_1_2_1_25_1","volume-title":"Kleinberg","author":"Dobzinski Shahar","year":"2013","unstructured":"Shahar Dobzinski , Hu Fu , and Robert D . Kleinberg . 2013 . Approximately optimal auctions with correlated bidders. Games Econ. Behav. (Special issue on selected algorithmic game theory papers from STOC, FOCS, and SODA 2011.) Shahar Dobzinski, Hu Fu, and Robert D. Kleinberg. 2013. Approximately optimal auctions with correlated bidders. Games Econ. Behav. (Special issue on selected algorithmic game theory papers from STOC, FOCS, and SODA 2011.)"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 385--394","author":"Flaxman Abraham","year":"2005","unstructured":"Abraham Flaxman , Adam Kalai , and H. Brendan McMahan . 2005 . Online convex optimization in the bandit setting: Gradient descent without a gradient . In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 385--394 . Abraham Flaxman, Adam Kalai, and H. Brendan McMahan. 2005. Online convex optimization in the bandit setting: Gradient descent without a gradient. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 385--394."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229057"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Jason D. Hartline. 2012. Approximation in Economic Design. Draft of a forthcoming book http:\/\/jasonhartline.com\/MDnA\/. Jason D. Hartline. 2012. Approximation in Economic Design. Draft of a forthcoming book http:\/\/jasonhartline.com\/MDnA\/.","DOI":"10.1257\/aer.102.3.330"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133094"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806732"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496775"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Zhiyi Huang and Sampath Kannan. 2012. Exponential mechanism for social welfare: private truthful and nearly optimal. Working paper. Zhiyi Huang and Sampath Kannan. 2012. Exponential mechanism for social welfare: private truthful and nearly optimal. Working paper.","DOI":"10.1109\/FOCS.2012.36"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/2050805.2050827"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 21st Conference on Learning Theory (COLT). 425--436","author":"Kleinberg Robert","year":"2008","unstructured":"Robert Kleinberg , Alexandru Niculescu-Mizil , and Yogeshwer Sharma . 2008 a. Regret bounds for sleeping experts and bandits . In Proceedings of the 21st Conference on Learning Theory (COLT). 425--436 . Robert Kleinberg, Alexandru Niculescu-Mizil, and Yogeshwer Sharma. 2008a. Regret bounds for sleeping experts and bandits. In Proceedings of the 21st Conference on Learning Theory (COLT). 425--436."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374475"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(85)90002-8"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 21st Advances in Neural Information Processing Systems (NIPS).","author":"Langford John","year":"2007","unstructured":"John Langford and Tong Zhang . 2007 . The epoch-greedy algorithm for contextual multi-armed bandits . In Proceedings of the 21st Advances in Neural Information Processing Systems (NIPS). John Langford and Tong Zhang. 2007. The epoch-greedy algorithm for contextual multi-armed bandits. In Proceedings of the 21st Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.08.007"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273587"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(87)90007-3"},{"key":"e_1_2_1_44_1","unstructured":"Ilya Segal. 2010. Personal communication. Ilya Segal. 2010. Personal communication."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOMW.2012.6193489"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 24th Conference on Learning Theory (COLT). (To appear in J. Mach. Learn. Res.","author":"Slivkins Aleksandrs","year":"2011","unstructured":"Aleksandrs Slivkins . 2011 a. Contextual bandits with similarity information . In Proceedings of the 24th Conference on Learning Theory (COLT). (To appear in J. Mach. Learn. Res. 2014.) Aleksandrs Slivkins. 2011a. Contextual bandits with similarity information. In Proceedings of the 24th Conference on Learning Theory (COLT). (To appear in J. Mach. Learn. Res. 2014.)"},{"key":"e_1_2_1_47_1","unstructured":"Aleksandrs Slivkins. 2011b. Monotone multi-armed bandit allocations. Open Problem Session at COLT 2011 (Conference on Learning Theory). Aleksandrs Slivkins. 2011b. Monotone multi-armed bandit allocations. Open Problem Session at COLT 2011 (Conference on Learning Theory)."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 21st Conference on Learning Theory (COLT). 343--354","author":"Slivkins Aleksandrs","year":"2008","unstructured":"Aleksandrs Slivkins and Eli Upfal . 2008 . Adapting to a changing environment: The Brownian restless bandits . In Proceedings of the 21st Conference on Learning Theory (COLT). 343--354 . Aleksandrs Slivkins and Eli Upfal. 2008. Adapting to a changing environment: The Brownian restless bandits. In Proceedings of the 21st Conference on Learning Theory (COLT). 343--354."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 27th International Conference on Machine Learning (ICML). 1015--1022","author":"Srinivas Niranjan","year":"2010","unstructured":"Niranjan Srinivas , Andreas Krause , Sham Kakade , and Matthias Seeger . 2010 . Gaussian process optimization in the bandit setting: No regret and experimental design . In Proceedings of the 27th International Conference on Machine Learning (ICML). 1015--1022 . Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. 2010. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning (ICML). 1015--1022."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2003.09.002"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229084"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2724705","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,15]],"date-time":"2023-10-15T11:05:31Z","timestamp":1697367931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2724705"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,6]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,5,6]]}},"alternative-id":["10.1145\/2724705"],"URL":"https:\/\/doi.org\/10.1145\/2724705","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,6]]},"assertion":[{"value":"2012-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}