direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Publications by Type: Journal and Magazine Articles

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.
Link to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions