摘要 Abstract
本文基于中央调控下的非合作博弈提出了一种新的优化问题,其可以被构造成双层结构。在下层,每个参与者竞相最小化自己的成本函数,该函数不仅依赖于所有参与者的策略,还取决于中央调控者的干预决策;而位于上层的中央调控者试图通过可调的干预决策实现社会最优,即最小化所有参与者的成本函数之和。在此设定下,受中央调控者干预时,下层参与者进行非合作博弈并寻求纳什均衡,而这实际上与调控者的决策相关。同时,调控者的目的是选择一个决策使得社会成本(即所有参与者的成本函数之和)最小。该构建的双层社会优化问题是受约束、非凸且非光滑的。为解决这一复杂问题,利用平滑技术开发了一种不精确的零阶算法,允许以不精确的方式计算下层博弈的纳什均衡。借助平滑技术的特性,严格证明了所设计的算法对于具有平滑目标的相关优化问题达到次线性收敛速率。此外,还讨论了在下层博弈存在精确均衡的情况下次线性收敛速率的问题。最后,通过数值模拟验证了理论结果的有效性。
This paper proposes a novel optimization problem building on noncooperative games under central regulation, which can be formulated as a bilevel structure. In the low-level, each player competes to minimize its own cost function that depends not only on the strategies of all players, but also on an intervention decision of the central regulator, while the central regulator located at the high-level attempts to achieve the social optimum, that is, to minimize the sum of cost functions of all players through an adjustable intervention decision. In this setting, under the intervention of the central regulator, the low-level players perform in a noncooperative game and aim to seek the Nash equilibrium, which indeed is related with the regulator's decision. Meanwhile, the objective of the regulator is to choose a decision such that the social cost, i.e., the sum of cost functions of all players is minimum. This formulated bilevel social optimization problem is proven to be constrained, nonconvex and nonsmooth. To address this intricate problem, an inexact zeroth-order algorithm is developed by virtue of the smoothing techniques, allowing for the Nash equilibrium of the low-level game to be computed in an inexact manner. Levering the properties of smoothing techniques, it is rigorously shown that the devised algorithm achieves a sublinear convergence rate for computing a stationary point of a related optimization problem with a smoothed objective. Moreover, the sublinear convergence rate in the scenario where the exact equilibrium of the low-level game is available is also discussed. Finally, numerical simulations are conducted to demonstrate the efficiency of theoretical findings.