Optimization Online


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

Samid Hoda(shoda***at***andrew.cmu.edu)
Andrew Gilpin(gilpin***at***cs.cmu.edu)
Javier Pena(jfp***at***andrew.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society