Correlated equilibrium

Here is some Matlab code to compute the linear constraints describing the set of correlated equilibria of a normal-form game:

The main subroutine celp.m.
An example of how to call it: runce.m.
A linear-program solver used in the example: iqph.m. (There's a lot more detail about this solver elsewhere on my site.)

Here is one example of a correlated equilibrium computed by the example code. (The equilibrium is for the Shapley game; see the example for payoffs.) Each entry of the matrix is the probability of a pair of strategies (one for the row player and one for the column player). In this equilibrium, the players avoid the diagonal elements (where both players choose the same action), since both players lose in case of a tie; they randomize equally over the remaining pairs. Each player wins half of the time, as indicated by the “P1 value” and “P2 value” lines below.

P =
    0.0000    0.1667    0.1667
    0.1667    0.0000    0.1667
    0.1667    0.1667    0.0000
P1 value 0.5
P2 value 0.5

And, here is a visualization of the set of correlated equilibria of another game:

PDF version

The game is a version of the famous “Battle of the Sexes” game, with the following payoffs (the first matrix gives one player's payoffs for each joint action, while the second matrix gives the other player's payoffs):

   F O    F O
F  3 0    4 0
O  0 4    0 3

Each corner of the pyramid represents a pair of strategies. Internal points represent distributions over strategy pairs; the blue hyperbola is the set of distributions in which the two players randomize independently, and the green solid is the set of correlated equilibria. The intersections between these two sets are the Nash equilibria (of which this game has three).