APPLYING METRIC REGULARITY TO COMPUTE A CONDITION MEASURE OF A SMOOTHING ALGORITHM FOR MATRIX GAMES

作者：Mordukhovich Boris S^*; Pena Javier F; Roshchina Vera

来源：SIAM Journal on Optimization, 2010, 20(6): 3490-3511.

DOI：10.1137/100786733

• matrix games
• smoothing algorithm
• condition measure
• variational analysis
• metric regularity
• generalized differentiation

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, Pena, and Sandholm [Proceedings of the 23rd Conference on Artificial Intelligence, 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.

• 出版日期2010