Smoothing techniques for computing Nash equilibria of sequential games
Abstract: We develop first-order smoothing techniques for saddle-point problems that arise in the Nash equilibria computation of sequential games. The crux of our work is a construction of suitable prox-functions for a certain class of polytopes that encode the sequential nature of the games. An implementation based on our smoothing techniques computes approximate Nash equilibria for games that are four orders of magnitude larger than what conventional computational approaches can handle.
Keywords: smoothing, Nash equilibrium, sequential games
Category 1: Convex and Nonsmooth Optimization (Convex Optimization )
Category 2: Other Topics (Game Theory )
Citation: Working Paper, Carnegie Mellon University, 2008.
Entry Submitted: 04/09/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|