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

DOI10.1137/100786733MaRDI QIDQ3083340zbMATH OpenOpenAlexFDO

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

Publication date 21 March 2011

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

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

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)

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.

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

Cited in

(3)

• Metric regularity -- a survey. 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)