Cost And Complexity Of Harnessing Games With Payments
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.
Volume (Year): 13 (2011)
Issue (Month): 01 ()
|Contact details of provider:|| Web page: http://www.worldscinet.com/igtr/igtr.shtml|
|Order Information:|| Email: |
When requesting a correction, please mention this item's handle: RePEc:wsi:igtrxx:v:13:y:2011:i:01:p:13-44. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Tai Tone Lim)
If references are entirely missing, you can add them using this form.