Log in

No account? Create an account
09 May 2011 @ 07:42 pm
Beyond Nash Equilibrium: Solution Concepts for the 21st Century  
I spent the last week in Taiwan at AAMAS 2011 and thought I'd do my usual thing of randomly blogging about bits of various talks that peaked my interest.

Joe Halpern gave a plenary talk as part of his acceptance of the ACM Research Award. His interest was in Game Theory and, in particular, in extensions of/alternatives to Nash Equilibrium. A Nash Equilibrium happens in a game when no player can improve their score by changing their strategy. It makes quite a lot of assumptions about how much information the players have about both the game and each other but has nevertheless been used quite widely to analyze all sorts of situations in terms of game playing and optimal strategies. In practical terms, if the Nash equilibrium occurs at some state that is beneficial in some global fashion, then in theory you can rely on the game players to act, out of self-interest, in a way that is globally (as well as individually) good.

Halpern was interested in looking at equilibria in situations where, for instance, players are allowed to (or just do anyway) form coalitions and so increase their scores by collaborating, or where some proportion of players can be assumed to be acting "irrationally". For instance, consider a game where you put all the players in a room and tell them that they get £2 each if they all stay in the room, but if anyone leaves then everyone who leaves gets £1 and all those who stay get nothing. The Nash equilibrium here is that everyone stays in the room. However in a game with, say, 1000 people playing your best strategy is probably going to be to leave because some player is bound not to be playing according to the optimal strategy for that game. Halpern was interested in investigating when equilibria exist which can accommodate coalitions or irrationality from a certain proportion of the game players. He was also interested in modelling the cost of computation, for instance adding a cost to keeping track of what other players were doing, or even the cost of acting in a genuinely random fashion, and then looking at how that effected the existence of equilibria in your game.

Halpern said a lot of these systems were not well studied in economics (where a lot of game theory originates) because such equilibria do not, in general, exist. However in a computer science context, we are often interested in designing systems (games) which have (globally beneficial) equilibria that are robust under these circumstances and, of course, we tend to have more control over the game's properties than economists do, so there is more of a practical drive towards studying these properties and understanding how and where we can create them.

This entry was originally posted at http://purplecat.dreamwidth.org/41160.html.