详细信息    查看全文

• 作者：Andrew Gilpin (1)
  Javier Pe?a (2) jfp@andrew.cmu.edu
  Tuomas Sandholm (1)
• 关键词：Mathematics Subject Classification (2000) 91A05 – 90C33 – 90C47 – 90C52
• 刊名：Mathematical Programming
• 出版年：2012
• 出版时间：June 2012
• 年：2012
• 卷：133
• 期：1-2
• 页码：279-298
• 全文大小：333.7 KB
• 参考文献：1. Bienstock D.: Potential Function Methods for Approximately Solving Linear Programming Problems. Kluwer International Series, Dordrecht (2002)
  2. Dantzig G.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)
  3. Gilpin, A., Sandholm, T., S?rensen, T.B.: Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of Texas Hold’em poker. In: Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 50–57. AAAI Press, Vancouver (2007)
  4. Goffin J.-L.: On the convergence rate of subgradient optimization methods. Math. Program. 13, 329–347 (1977)
  5. Hirriart-Urruty J., Lemaréchal C.: Fundamentals of Convex Analysis. Springer, Berlin (2001)
  6. Hoda S., Gilpin A., Pe?a J., Sandholm T.: Smoothing techniques for computing Nash equilibria of sequential games. Math. Oper. Res. 35(2), 494–512 (2010)
  7. Koller D., Megiddo N.: The complexity of two-person zero-sum games in extensive form. Games Econ. Behav. 4(4), 528–552 (1992)
  8. Lan, G., Lu, Z., Monteiro, R.D.C.: Primal-dual first-order methods with iteration-complexity for cone programming. (to appear in Math Program) (2010)
  9. McMahan, H., Gordon, G.J.: A fast bundle-based anytime algorithm for poker and other convex games. In: Proceedings of the 11th International Conference on Artificial Intelligence and Statistics (AISTATS), San Juan, Puerto Rico (2007)
  10. Mordukhovich, B., Pe?a, J., Roshchina, V.: Computation of a condition measure of a smoothing algorithm for matrix games. (to appear in SIAM J. Optim.) (2010)
  11. Nesterov Y.: A method for unconstrained convex minimization problem with rate of convergence O(1/k 2). Doklady AN SSSR 269, 543–547 (1983) (Translated to English as Soviet Math. Docl.)
  12. Nesterov Y.: Excessive gap technique in nonsmooth convex minimization. SIAM J. Optim. 16(1), 235–249 (2005)
  13. Nesterov Y.: Smooth minimization of non-smooth functions. Math. Program. 103, 127–152 (2005)
  14. Osborne M., Rubinstein A.: A Course in Game Theory. MIT Press, Cambridge (1994)
  15. Romanovskii I.: Reduction of a game with complete memory to a matrix game. Sov. Math. 3, 678–681 (1962)
  16. Shi, J., Littman, M.: Abstraction methods for game theoretic poker. In: CG ’00: Revised Papers from the Second International Conference on Computers and Games, London, UK, pp. 333–345. Springer, Berlin (2002)
  17. Smola, A.J., Vishwanathan, S.V.N., Le, Q.: Bundle methods for machine learning. In: Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), Vancouver, Canada (2007)
  18. von Stengel B.: Efficient computation of behavior strategies. Games Econ. Behav. 14(2), 220–246 (1996)
  19. Wright S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)
  20. Ye Y., Todd M., Mizuno S.: An -iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19, 53–67 (1994)
  21. Zinkevich, M., Bowling, M., Burch, N.: A new algorithm for generating equilibria in massive zero-sum games. In: Proceedings of the National Conference on Artificial Intelligence (AAAI), Vancouver, Canada (2007)
  22. Zinkevich, M., Bowling, M., Johanson, M., Piccione, C.: Regret minimization in games with incomplete information. In: Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), Vancouver, Canada (2007)
• 作者单位：1. Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA2. Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, USA
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem min_{x ? Q1}max_{y ? Q2} xTAy = max_{y ? Q2} min_{x ? Q1} xTAy.\min_{x \in Q_1}\max_{y \in Q_2} {x}^{\rm T}{Ay} = \max_{y \in Q_2} \min_{x \in Q_1} {x}^{\rm T}{Ay}.