Reaching Correlated Equilibria Through Multi-agent Learning

Many games have undesirable Nash equilibria. For exam- ple consider a resource allocation game in which two players compete for an exclusive access to a single resource. It has three Nash equilibria. The two pure-strategy NE are effi- cient, but not fair. The one mixed-strategy NE is fair, but not efficient. Aumann’s notion of correlated equilibrium fixes this problem: It assumes a correlation device which suggests each agent an action to take. However, such a “smart” coordination device might not be available. We propose using a randomly chosen, “stupid” in- teger coordination signal. “Smart” agents learn which action they should use for each value of the coordination signal. We present a multi-agent learning algorithm which con- verges in polynomial number of steps to a correlated equilib- rium of a wireless channel allocation game, a variant of the resource allocation game. We show that the agents learn to play for each coordination signal value a randomly chosen pure-strategy Nash equilibrium of the game. Therefore, the outcome is an efficient correlated equilibrium. This CE be- comes more fair as the number of the available coordination signal values increases. We believe that a similar approach can be used to reach efficient and fair correlated equilibria in a wider set of games, such as potential games.