Solving Maxmin Optimization Problems via Population Games
本文证明一类最大最小优化问题可转化为群体博弈的纳什均衡求解，并利用离散时间复制者方程（即指数乘法权重算法）导出迭代算法，该算法推广了数值分析中的迭代重加权最小二乘法，适用于集体投资和模型不确定性下的决策。
Abstract Population games are games with a finite set of available strategies and an infinite number of players, in which the reward for choosing a given strategy is a function of the distribution of players over strategies. The paper shows that, in a certain class of maxmin optimization problems, it is possible to associate a population game to a given maxmin problem in such a way that solutions to the optimization problem are found from Nash equilibria of the associated game. Iterative solution methods for maxmin optimization problems can then be derived from systems of differential equations whose trajectories are known to converge to Nash equilibria. In particular, we use a discrete-time version of the celebrated replicator equation of evolutionary game theory, also known in machine learning as the exponential multiplicative weights algorithm. The resulting algorithm can be viewed as a generalization of the Iteratively Reweighted Least Squares (IRLS) method, which is well known in numerical analysis as a useful technique for solving Chebyshev function approximation problems on a finite grid. Examples are provided to show the use of the generalized IRLS method in collective investment and in decision making under model uncertainty.