On the computation of equilibria in monotone and potential stochastic hierarchical games
On the computation of equilibria in monotone and potential stochastic hierarchical games
复制标题
单调和潜在随机层次博弈中均衡的计算
作者：
Shisheng Cui;U. Shanbhag
我们考虑了一类非合作分层$${extbf{N}}$$N-玩家对策，其中第i个玩家求解一个带有均衡约束的参数随机数学规划(MPEC)，并且警告说，给定竞争对手的决策，MPEC中第i个玩家的隐式形式在玩家策略中是凸的。用于计算均衡的通用方案很少，如果有的话，这促使计算方案在两个区域中的发展：(A)单调区域。当特定于玩家的隐式问题是凸的时，通过随机包含给出了均衡的充要条件。在算子的单调性假设下，我们发展了一个方差减少的随机邻近点格式，它在单调/强单调区域内求解具有最优或接近最优样本复杂性保证的邻近点问题时，获得了确定性的收敛速度。最后，证明了生成的序列在几乎确定的意义下，在单调和强单调状态下都收敛到一个平衡点；(B)势。当对策的隐式形式允许一个势函数时，我们发展了一个异步松弛的不精确光滑的近端最佳响应框架，该框架要求高效地计算具有强凸隐式目标的MPEC的近似解。为此，我们考虑这个游戏的$$eta$$η平滑的对应物，其中每个玩家的问题通过随机平滑来平滑。事实上，平滑后的对手的纳什均衡就是原始博弈的$$ETA$$η近似纳什均衡。我们提出的方案产生了一个序列和一个松弛变量，几乎肯定会收敛到$$Eta$$η近似的纳什均衡。该格式依赖于求解近似问题，这是一个隐含形式具有强凸目标的随机MPEC，在有限时间内具有更高的精度。平滑框架允许为此类问题开发允许快速收敛的经方差减少的零阶格式。对一类多领导者多追随者博弈的数值研究表明，减方差的近端方案在运行时间少得多的情况下提供了显著更好的精度。松弛的最佳响应方案与问题大小的比例很好，并且通常比非松弛的对应方案表现出更多的稳定性。
We consider a class of noncooperative hierarchical $${ extbf{N}}$$ N -player games where the i th player solves a parametrized stochastic mathematical program with equilibrium constraints (MPEC) with the caveat that the implicit form of the i th player’s in MPEC is convex in player strategy, given rival decisions. Few, if any, general purpose schemes exist for computing equilibria, motivating the development of computational schemes in two regimes: (a) Monotone regimes. When player-specific implicit problems are convex, then the necessary and sufficient equilibrium conditions are given by a stochastic inclusion. Under a monotonicity assumption on the operator, we develop a variance-reduced stochastic proximal-point scheme that achieves deterministic rates of convergence in terms of solving proximal-point problems in monotone/strongly monotone regimes with optimal or near-optimal sample-complexity guarantees. Finally, the generated sequences are shown to converge to an equilibrium in an almost-sure sense in both monotone and strongly monotone regimes; (b) Potentiality. When the implicit form of the game admits a potential function, we develop an asynchronous relaxed inexact smoothed proximal best-response framework, requiring the efficient computation of an approximate solution of an MPEC with a strongly convex implicit objective. To this end, we consider an $$eta $$ η -smoothed counterpart of this game where each player’s problem is smoothed via randomized smoothing. In fact, a Nash equilibrium of the smoothed counterpart is an $$eta $$ η -approximate Nash equilibrium of the original game. Our proposed scheme produces a sequence and a relaxed variant that converges almost surely to an $$eta $$ η -approximate Nash equilibrium. This scheme is reliant on resolving the proximal problem, a stochastic MPEC whose implicit form has a strongly convex objective, with increasing accuracy in finite-time. The smoothing framework allows for developing a variance-reduced zeroth-order scheme for such problems that admits a fast rate of convergence. Numerical studies on a class of multi-leader multi-follower games suggest that variance-reduced proximal schemes provide significantly better accuracy with far lower run-times. The relaxed best-response scheme scales well with problem size and generally displays more stability than its unrelaxed counterpart.
影响因子：
2.7
作者：
Shisheng Cui;U. Shanbhag;Farzad Yousefian
通讯作者：
Shisheng Cui;U. Shanbhag;Farzad Yousefian