Applying metric regularity to compute a condition measure of a smoothing algorithm for matrix games

DOI10.1137/100786733zbMATH Open1209.91017arXiv1007.4458OpenAlexW2068712022MaRDI QIDQ3083340FDOQ3083340

Javier Peña, Boris S. Mordukhovich, Vera Roshchina

Publication date: 21 March 2011

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We develop an approach of variational analysis and generalized differentiation to conditioning issues for two-person zero-sum matrix games. Our major results establish precise relationships between a certain condition measure of the smoothing first-order algorithm proposed by Gilpin et al. [Proceedings of the 23rd AAAI Conference (2008) pp. 75-82] and the exact bound of metric regularity for an associated set-valued mapping. In this way we compute the aforementioned condition measure in terms of the initial matrix game data.

Full work available at URL: https://arxiv.org/abs/1007.4458

Recommendations

• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• On the metric approach in the theory of matrix games
• scientific article; zbMATH DE number 772312
• Conditioning and regularization of nonsymmetric operators
• Regularity and conditioning of solution mappings in variational analysis

zbMATH Keywords

smoothing algorithmmetric regularityNash equilibriavariational analysismatrix gamesLipschitzian stability

Mathematics Subject Classification ID

Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37) 2-person games (91A05)

Cited In (3)

• METRIC REGULARITY—A SURVEY PART II. APPLICATIONS
• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• Generalized Newton's method based on graphical derivatives

This page was built for publication: Applying metric regularity to compute a condition measure of a smoothing algorithm for matrix games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3083340)