A gradient-based approach for computing Nash equilibria of large sequential games

Samid Hoda(shodaandrew.cmu.edu)
Andrew Gilpin(gilpincs.cmu.edu)
Javier Pena(jfpandrew.cmu.edu)

Abstract: We propose a new gradient based scheme to approximate Nash equilibria of large sequential two-player, zero-sum games. The algorithm uses modern smoothing techniques for saddle-point problems tailored specifically for the polytopes used in the Nash equilibrium problem.

Keywords: Nash equilibrium, linear programming, smoothing techniques

Category 1: Other Topics (Game Theory )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Working Paper, Tepper School of Business, Carnegie Mellon University

Download: [PDF]

Entry Submitted: 07/06/2007
Entry Accepted: 07/13/2007
Entry Last Modified: 07/06/2007

Modify/Update this entry