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

广义随机纳什均衡框架：理论、计算和应用

• 批准号: 2231863
• 负责人: Afrooz Jalilzadeh
• 金额: $ 27.85万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-08-15 至 2026-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2231863&HistoricalAwards=false
• 关键词: Generalized; Stochastic; Nash; Equilibrium; Framework

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.

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