Digging Deeper...

Day 2

Today we went deeper into exploring some game theory concepts. We started off with revisions to some techniques learned on day 1. We then looked at minmax, maxmin strategies, minmax theorem and derived the solution of a 2-player, zero-sum game as a linear program. As an example, we solved the linear program to get the solution of the matching pennies game. 

In the second half of the workshop, we discussed two major computational techniques to find Nash equilirbria in 2-player, general sum games - the Lemke Howson algorithm and the Support Enumeration Method. We solved an example of finding the Nash equilibrium using the Lemke Howson algorithm using both the graphical or geometric construction and pivoting to solve a system of linear equations. We wrapped up with a brief discussion on extending these two algorithms to n-player, general sum games.

For further readings on these topics, check Chapter 3 of Nisan's Algorithmic Game Theory textbook (Website link under Day 1. Also, there have been two recent papers on using local search techniques for finding Nash equilibria, that are given below. Both these papers should be available on IEEE Xplore. If you are interested in presentation slides of these papers (from our lab's paper reading group presentations), send email to me at pdasgupta-at-unomaha-dot-edu

1. S. Ceppi, N. Gatti, G. Patrini and M. Rocco, "Local Search Methods for Finding a Nash Equilibrium in Two-Player Games" IAT 2010.

2. N. Gatti, G. Patrini, M. Rocco and T. Sandholm "Combining Local Search Techniques and Path Following for Bimatrix Games, UAI 2012.