Learning problems commonly exhibit an interesting feedback mechanism wherein the population data reacts to competing decision makers' actions. This paper formulates a new game theoretic framework for this phenomenon, called multi-player performative prediction. We focus on two distinct solution concepts, namely (i) performatively stable equilibria and (ii) Nash equilibria of the game. The latter equilibria are arguably more informative, but can be found efficiently only when the game is monotone. We show that under mild assumptions, the performatively stable equilibria can be found efficiently by a variety of algorithms, including repeated retraining and repeated (stochastic) gradient play. We then establish transparent sufficient conditions for strong monotonicity of the game and use them to develop algorithms for finding Nash equilibria. We investigate derivative free methods and adaptive gradient algorithms wherein each player alternates between learning a parametric description of their distribution and gradient steps on the empirical risk. Synthetic and semi-synthetic numerical experiments illustrate the results.
翻译:学习问题通常展示出一个有趣的反馈机制,让人口数据对相互竞争的决策者的行为作出反应。本文件为这一现象制定了一个新的游戏理论框架,称为多玩家表现预测。我们侧重于两个不同的解决方案概念,即(一) 性能稳定的平衡和(二) Nash 平衡。后一种平衡可以说信息更加丰富,但只有在游戏为单调时才能有效找到。我们显示,在温和假设下,通过多种算法,包括反复的再培训和反复的(随机的)梯度游戏,可以有效地找到表现稳定的平衡。我们随后为游戏的强烈单一性创造足够的透明条件,并利用这些条件来开发寻找纳什平衡的算法。我们调查衍生法和适应性梯度算法,让每个玩家在学习其分布的参数描述和实验风险的梯度之间相互交替使用。合成和半合成数字实验展示了结果。