Generalized Stochastic Nash Equilibrium Framework: Theory, Computation, and Application

纳什均衡（NE）是博弈论中的一个基本概念，它被描述为所有参与者选择的特定策略的集合，其中没有参与者可以通过单方面改变他们在可行策略集中的策略来降低他们的成本。广义NE （Generalized NE，简称GNE）是这一概念的一个重要延伸，即每个玩家的策略选择会影响其他玩家的可行策略集。如果玩家共享一些公共资源，这种情况自然会出现。考虑到资源和信息可用性的不确定性，制定该模型的一种途径是使用随机拟变分不等式（SQVI）。由于缺乏求解SQVIs的有效方法，我们的目标是引入具有收敛保证的计算效率高的算法。此外，为了避免决策受到低概率糟糕情景的影响，我们研究了基于风险的GNE模型。本研究结果将提供一套数学工具，以优化各种领域的决策，如电源控制、无线传感器网络和医疗保健系统，从而提高系统效率和性能。此外，该项目还将通过开设新的本科和研究生课程，为本科生和研究生提供研究经验，并通过暑期学院和课堂讲座和演讲为高中生开展拓展项目，从而对教育产生影响。本项目主要研究两个方向。(1)为解决SQVI问题开发首批具有复杂性保证的算法。提出的算法将结合方差减少、加速和嵌套近似技术来解决（强）单调问题。此外，当问题包含复杂的约束时，该项目旨在开发不精确的算法，以有效地近似约束集上的投影，增强所提出方案对现实问题的适用性。（II）利用随机逼近技术和分布鲁棒性方法，研究基于风险的GNE模型作为大规模SQVI问题的新重构。为了解决该问题的大规模性质所带来的挑战，将开发一套新的高效算法，使用块坐标和方差减少技术。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Nash Equilibrium (NE) is one of the fundamental concepts in game theory which is described as a collection of specific strategies chosen by all the players, where no player can reduce their cost by unilaterally changing their strategy within their feasible strategy set. An important extension of this concept, which is known as Generalized NE (GNE), is when each player’s strategy choice affects the feasible strategy set of other players. This situation arises naturally if the players share some common resources. One avenue to formulate this model, considering the uncertainty in the availability of resources and information, is using Stochastic Quasi-Variational Inequalities (SQVI). Motivated by the lack of efficient methods for solving SQVIs, we aim to introduce computationally efficient algorithms with convergence guarantees. Moreover, to avoid decisions influenced by a bad scenario with a low probability, we investigate risk-based GNE models. The outcome of this research will provide a set of mathematical tools to optimize decision-making in various domains such as power control, wireless sensor network, and healthcare systems, that improves system efficiency and performance. Additionally, the project will have educational impacts by creating new undergraduate and graduate courses, providing research experience for undergraduate and graduate students, and conducting outreach programs for high school students through summer academies and classroom lectures and presentations.This project focuses on two main research directions. (I) Developing amongst the first known algorithms with complexity guarantees for solving SQVI problems. The proposed algorithms will incorporate variance reduction, acceleration, and nested approximation techniques to address (strongly) monotone problems. Moreover, when the problem contains complicated constraints, the project aims to develop inexact algorithms that approximate the projection onto the constraint set efficiently, enhancing the applicability of the proposed schemes to real-world problems. (II) Examining novel reformulations of risk-based GNE models as large-scale SQVI problems by leveraging the stochastic approximation technique and distributionally robust approach. To tackle the challenge posed by the large-scale nature of the problem, a new set of efficient algorithms using block-coordinate and variance-reduction techniques will be developed.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.