All publications

Cost and Complexity of Harnessing Games with Payments
Citation key	EPSW-CCHGP-11
Author	Eidenbenz, Raphael and Pignolet, Yvonne Anne and Schmid, Stefan and Wattenhofer, Roger
Year	2011
ISSN	0219-1989
Online ISSN	1793-6675
Journal	International Game Theory Review (IGTR)
Volume	13
Number	1
Publisher	World Scientific
Abstract	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.