May 23, 2013

Supergametools

Many people are familiar with the introductory game-theory scenario of the prisoners dilemma. When the prisoners make their decision only once, the Nash equilibrium strategy is to testify against their partner. Things change, however, when the prisoners make their decision infinitely many times. A very neat folk theorem says that infinitely repeated games can give rise to many more Nash equilibria.

Analytically finding the set of Nash equilibria in an infinitely repeated game is usually not possible. A paper by Judd, Yeltekin, and Conklin (2003) gives some nice numerical algorithms to approximate the set.

I coded these algorithms up as functions in a library called supergametools. It is available for download here, and includes instructions for installation and usage. I give an example of how you would use the library for a simple prisoners dilemma below:

import numpy as np
import supergametools as sgt

# determine payoff matrices p1 = np.array([[4, 0], [6, 2]])
p2 = p1.T

# center and radious of initial guess
cen = np.array([3, 3], ndmin=2)
rad = 5

# find outer hull of set of supergame equilibria
outer_hull = sgt.outerbound(p1, p2, cen, rad)

# display results
print outer_hull


The output is the following image. The red lines give the convex hull of the equilibria set. The routine also gives the convex hull in matrix form.