Machinations


Windfall of Malice
July 27, 2009, 9:55 pm
Filed under: Uncategorized | Tags: ,

A significant contribution of computer science to game theory is the concept of the price of anarchy.  This value is a measure of how much selfish behavior can hurt the overall social welfare in a game.  It is defined by considering the worst possible social welfare that can occur in a Nash equilibria and comparing it with the best social welfare achievable if the players are controlled by a benevolent dictator.  More specifically, the price of anarchy is just the ratio of these two quantities: the optimal social welfare achievable divided by the social welfare for the worst Nash equilibria.

A huge number of papers over the past several years have computed the price of anarchy in various games, some games have large price of anarchy and some games have small.  After reading enough of these papers, it’s easy to get the feeling that “Everyone talks about the price of anarchy, but nobody does anything about it!”  After all, an obvious contribution that CS theory should be making to the area of game theory is to propose algorithmic techniques that optimize social welfare.  A recent nice result in this direction is by Balcan, Blum and Mansor in SODA ’09: Improved Equilibria via Public Service Advertising.  They describe how efforts by a third party can tip the players in some games away from equilibria with poor social welfare and towards equilibria with better social welfare.

Another line of interesting work began with a paper by Moscibroda, Schmid, and Wattenhofer who showed that for a particular virus inoculation game, the existence of malevolent players can paradoxically improve  social welfare.  In particular, if the set of players in a game know that a small number of them are not selfish, but actually have worst case utility functions, then the price of anarchy of this new game is actually better than if there were no malevolent players.   A follow up paper by Babaioff, Kleinberg, and Papadimitriou showed the same effect can occur in network congestion games, and this paper coined the phrase “windfall of malice” to describe the effect.

An interesting (and obvious) question is: “Is it possible to achieve the windfall of malice without the actual presence of adversarial players?”  Recently, Diaz, Mitsche, Rustagi and I have made our own small contribution to this area by showing that the answer is “Yes.”  Our approach is based on the concept of a mediator.    Informally, a mediator is a trusted third party that suggests actions to each player.  The players retain free will and can ignore the mediator’s suggestions.  The mediator proposes actions privately to each player, but the algorithm the mediator uses to decide what to propose is public knowledge.  The idea of using a mediator has been made much more appealing recently by a paper by Abraham, Dolev, Gonen and Halpern in PODC ’06.  They show that it is almost always possible to simulate a mediator, without the need of a trusted third party, through the technique of “cheap talk”, i.e. talk among the players that has no economic consequences.

There are three basic results we are able to show in our paper:

  • We introduce a general technique for designing mediators that is inspired by careful study of the “windfall of malice” effect.  In our approach, the mediator makes a random choice of one of two possible configurations, where a configuration is just a set of proposed actions for each player.  The first configuration is optimal: the mediator proposes a set of actions that achieves the social optimum (or very close to it).  The second configuration is “fear inducing”: the mediator proposes a set of actions that leads to catastrophic failure for those players who do not heed the mediators advice.  The purpose of the second configuration is to ensure that the players follow the advice of the mediator when the optimal configuration is chosen.  Thus, the random choice of which configuration is chosen must be hidden from the players.
  • We use our technique to design mediators for two games.  First, we design a mediator for the virus inoculation game that was proposed by Moscibroda et al. that achieves a social welfare that is asymptotically optimal.  Second, we design a mediator for a variant of the El Farol game that improves the social welfare over the best Nash equilibria.  Surprisingly, our technique works for the El Farol game, even though this game does not have a windfall of malice.
  • We show the limits of our approach by proving an impossibility result that shows that for a large class of games, no mediator will improve the social welfare over the best Nash equilibria.  In particular, this impossibility result holds for the congestion games that Babaioff, Kleinberg and Papadimitriou show have a windfall of malice.  Thus, we show that some games with a windfall of malice effect can not be improved by the use of a mediator.

Much of my own work has been on designing algorithms that foil adversarial agents (e.g. consensus algorithms).  It’s interesting and surprising to see that adversarial agents and actions can actually cause beneficial effects!

Advertisements

3 Comments so far
Leave a comment

[…] Fear in Mediation: Exploiting the Windfall of Malice , that I’d previously blogged about here, was accepted, so I’m looking forward to  taking another trip out to Rome.  Amazingly, this […]

Pingback by WINE 2009 « Machinations

Heya Jared. Thanks for the survey, I added a few papers to my “toread” list. One typo in the first paragraph (since I noted it): “of the these two”

Comment by Jeremy Barbay

Hey Jeremy, good to hear from you again and thanks for the feedback. Hope life is good in Chile!

Comment by Jared




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: