{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T09:29:20Z","timestamp":1648805360594},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. Game Theory Rev."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p> This article studies how a mechanism designer can influence games by promising payments to the players depending on their mutual choice of strategies. First, we investigate the cost of implementing a desirable behavior and present algorithms to compute this cost. Whereas a mechanism designer can decide efficiently whether strategy profiles can be implemented at no cost at all our complexity analysis indicates that computing an optimal implementation is generally NP-hard. Second, we introduce and analyze the concept of leverage in a game. The leverage captures the benefits that a benevolent or a malicious mechanism designer can achieve by implementing a certain strategy profile region within economic reason, i.e., by taking the implementation cost into account. Mechanism designers can often manipulate games and change the social welfare by a larger extent than the amount of money invested. Unfortunately, computing the leverage turns out to be intractable as well in the general case. <\/jats:p>","DOI":"10.1142\/s0219198911002824","type":"journal-article","created":{"date-parts":[[2011,12,12]],"date-time":"2011-12-12T07:07:10Z","timestamp":1323673630000},"page":"13-44","source":"Crossref","is-referenced-by-count":0,"title":["COST AND COMPLEXITY OF HARNESSING GAMES WITH PAYMENTS"],"prefix":"10.1142","volume":"13","author":[{"given":"RAPHAEL","family":"EIDENBENZ","sequence":"first","affiliation":[{"name":"Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland"}]},{"given":"YVONNE ANNE","family":"PIGNOLET","sequence":"additional","affiliation":[{"name":"IBM Research, Zurich Laboratory, Switzerland"}]},{"given":"STEFAN","family":"SCHMID","sequence":"additional","affiliation":[{"name":"Deutsche Telekom Laboratories\/TU Berlin, Berlin, Germany"}]},{"given":"ROGER","family":"WATTENHOFER","sequence":"additional","affiliation":[{"name":"Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf2","first-page":"153","author":"Alon N.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"rf11","first-page":"40","author":"Dash R. K.","journal-title":"IEEE Intelligent Systems"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/0047-2727(83)90012-9"},{"key":"rf16","first-page":"634","author":"Feige U.","journal-title":"Journal of the ACM"},{"key":"rf18","first-page":"23","author":"Maskin E.","journal-title":"Nash Equilibrium and Welfare Optimality"},{"key":"rf19","volume-title":"Handbook of Social Choice Theory and Welfare (Implementation Theory)","author":"Maskin E.","year":"2002"},{"key":"rf21","volume":"173","author":"Monderer D.","journal-title":"Artif. Intell."},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"rf25","volume-title":"A Course in Game Theory","author":"Osborne M. J.","year":"1994"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.06.004"},{"key":"rf28","volume-title":"Rules of Encounter","author":"Rosenschein J. S.","year":"1994"},{"key":"rf30","first-page":"337","volume":"2","author":"Segal I.","journal-title":"The Quarterly Journal of Economics"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0713"}],"container-title":["International Game Theory Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219198911002824","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T09:18:29Z","timestamp":1565083109000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219198911002824"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":13,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1142\/S0219198911002824"],"URL":"https:\/\/doi.org\/10.1142\/s0219198911002824","relation":{},"ISSN":["0219-1989","1793-6675"],"issn-type":[{"value":"0219-1989","type":"print"},{"value":"1793-6675","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]}}}