Title: Correlated Equilibria- Existence and some Properties for Bimatrix Games
Speaker: T.E.S. Raghavan, University of Illinois at Chicago
Date and Time: Friday 3 January 2014, 3:00 pm
Venue: Room 217, Mechanical Engineering
Abstract:
The concept of a Nash equilibrium is at the heart of modern non-cooperative game theory. It says that a set of strategies constitute a Nash equilibrium when no participant can gain by deviating from his/her strategy unilaterally while all the other participants remain status quo sticking to their strategies.
The seminal contribution of Nash was to come up with this definition and prove its existence for bimatrix games via Brouwer’s fixed point theorem. While even von Neumann and Borel and all including Herman Weyl, were trying to develop algorithms for computing value and good strategies for zero sum two person games which finally culminated in reducing zero sum two person games to a simple LP problem with its constructive Simplex algorithm, the Nash equilibrium computation has been elusive due to its lack of order field property for games with more than two players. However the concept of a correlated equilibrium due to Aumann is another solution concept which has greater appeal when we allow suggestions to players, by a non participating person in the game.
In fact when there is no communication between players and the game admits multiple Nash equilibria it is not clear how any particular equilibrium in mixed strategies is playable.
Suppose a referee comes up with the advice: Dear Players-please play this particular Nash equilibrium.
It is true that the referee is only advising them. Suppose the referee is respected by all players. In such a case, being a Nash equilibrium, no player gains by disrespecting the referee’s advice unilaterally while the rest of the players respect the referee’s advice. The referee could do even better still. He could select a mixture of action tuples with some probability and based on the outcome of this chance experiment advise each player to choose the corresponding action component of the player while keeping actual outcome of the experiment secret.
We call any such probability distribution on the joint action spaces, a correlated equilibrium, if players have no gain by deviating unilaterally from the referee’s advice when they believe rest will take referee’s advice.