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

点击翻译按钮获取中文摘要

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.