COST AND COMPLEXITY OF HARNESSING GAMES WITH PAYMENTS

Raphael Eidenbenz (), Yvonne Anne Pignolet (), Stefan Schmid () and Roger Wattenhofer ()
Additional contact information
Raphael Eidenbenz: Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland
Yvonne Anne Pignolet: IBM Research, Zurich Laboratory, Switzerland
Stefan Schmid: Deutsche Telekom Laboratories/TU Berlin, Berlin, Germany
Roger Wattenhofer: Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland

International Game Theory Review (IGTR), 2011, vol. 13, issue 01, 13-44

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 generallyNP-hard. Second, we introduce and analyze the concept ofleveragein 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.

JEL-codes: B4 C0 C6 C7 D5 D7 M2 (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219198911002824
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:igtrxx:v:13:y:2011:i:01:n:s0219198911002824

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219198911002824

Access Statistics for this article

International Game Theory Review (IGTR) is currently edited by David W K Yeung

More articles in International Game Theory Review (IGTR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().