Linear programming in Python: CVXOPT and game theory

CVXOPT is an excellent Python package for linear programming. However, when I was getting started with it, I spent way too much time getting it to work with simple game theory example problems. This tutorial aims to shorten the startup time for everyone trying to use CVXOPT for more advanced problems.

All code is available here.

Installation of dependencies:

  • Using Docker is the fastest way to run the code. In only 5 commands you can replicate my environment and run the code.
  • Alternatively, the code has the following dependencies: Python (3.5.3), numpy (1.12.1), cvxopt (1.1.9), glpk optimizer (but you can use the default optimizer, glpk is better for some more advanced problems)

Please review how CVXOPT solves simple maximization problems. While this article focuses on game theory problems, it is critical to understand how CVXOPT defines optimization problems in general.

The first problem we will solve is a 2-player zero-sum game.

The constraints matrix A is defined as

Next, we define a maxmin helper function

Last, we use the maxmin helper function to solve our example problem:

In other words, player A chooses action 1 with probility 1/6 and action 2 with probability 5/6.

Next we will solve a Correlated Equilibrium problem called Game of Chicken as defined on page 3 of this document. The constraints matrix A is defined as

Next, we define a ce and build_ce_constraints helper functions:

Using the helper functions, we solve the Game of Chicken

In other words, the optimal strategy is for both players to select actions [6, 6] 50% of the time, actions [2, 7] 25% of the time, and action [7, 2] also 25% of the time.

Hopefully this overview helps in getting you started with linear programming and game theory in Python.

Credits: cvxopt.org/examples/tutorial/lp.html, cs.duke.edu/courses/fall12/cps270/lpandgames.pdf, en.wikipedia.org/wiki/Minimax#Example, https://www3.ul.ie/ramsey/Lectures/Operations_Research_2/gametheory4.pdf, cs.rutgers.edu/~mlittman/topics/nips02/nips02/greenwald.ps, cs.duke.edu/courses/fall16/compsci570/LPandGames.pdf

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store