Hoda, Samid; Gilpin, Andrew; Peña, Javier; Sandholm, Tuomas Smoothing techniques for computing Nash equilibria of sequential games. (English) Zbl 1232.91042 Math. Oper. Res. 35, No. 2, 494-512 (2010). Summary: We develop first-order smoothing techniques for saddle-point problems that arise in finding a Nash equilibrium 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 game. We also introduce heuristics that significantly speed up the algorithm, and decomposed game representations that reduce the memory requirements, enabling the application of the techniques to drastically larger games. An implementation based on our smoothing techniques computes approximate Nash equilibria for games that are more than four orders of magnitude larger than what prior approaches can handle. Finally, we show near-linear further speedups from parallelization. Cited in 11 Documents MSC: 91A20 Multistage and repeated games 91A05 2-person games 90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) Keywords:smoothing techniques; Nash equilibrium; sequential games Software:GameShrink PDFBibTeX XMLCite \textit{S. Hoda} et al., Math. Oper. Res. 35, No. 2, 494--512 (2010; Zbl 1232.91042) Full Text: DOI