期刊
MATHEMATICS OF OPERATIONS RESEARCH
卷 35, 期 2, 页码 494-512出版社
INFORMS
DOI: 10.1287/moor.1100.0452
关键词
smoothing techniques; Nash equilibrium; sequential games
资金
- Tepper School of Business, Carnegie Mellon University
- National Science Foundation (NSF) [IIS-0427858, IIS-0905390]
- Siebel Scholarship
- NSF under CMMI [0855707]
- NSF under CCF [0830533]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [0855707] Funding Source: National Science Foundation
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据