An official website of the United States government
We consider the stochastic generalized Nash equilibrium problem (SGNEP) where a set of self-interested players, subject to certain global constraints, aim to optimize their local objectives that depend on their own decisions and the decisions of others and are influenced by some random factors. A distributed stochastic generalized Nash equilibrium seeking algorithm is proposed based on the Douglas-Rachford operator splitting scheme, which only requires local communications among neighbors. The proposed scheme significantly relaxes assumptions on co-coercivity and contractiveness in the existing literature, where the projected stochastic subgradient method is applied to provide approximate solutions to the augmented best-response subproblems for each player. Finally, we illustrate the validity of the proposed algorithm through a Nash-Cournot production game.
more »
« less
Distributed Solution of GNEP over Networks via the Douglas-Rachford Splitting Method
The aim of this paper is to find the distributed solution of the generalized Nash equilibrium problem (GNEP) for a group of players that can communicate with each other over a connected communication network. Each player tries to minimize a local objective function of its own that may depend on the other players’ decisions, and collectively all the players’ decisions are subject to some globally shared resource constraints. After reformulating the local optimization problems, we introduce the notion of network Lagrangian and recast the GNEP as the zero finding problem of a properly defined operator. Utilizing the Douglas-Rachford operator splitting method, a distributed algorithm is proposed that requires only local information exchanges between neighboring players in each iteration. The convergence of the proposed algorithm to an exact variational generalized Nash equilibrium is established under two different sets of assumptions. The effectiveness of the proposed algorithm is demonstrated using the example of a Nash-Cournot production game.
more »
« less
- Award ID(s):
- 2014816
- PAR ID:
- 10316599
- Date Published:
- Journal Name:
- 60th IEEE Conference on Decision and Control (CDC)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the stochastic generalized Nash equilibrium problem (SGNEP) where a set of self-interested players, subject to certain global constraints, aim to optimize their local objectives that depend on their own decisions and the decisions of others and are influenced by some random factors. A distributed stochastic generalized Nash equilibrium seeking algorithm is proposed based on the Douglas-Rachford operator splitting scheme, which only requires local communications among neighbors. The proposed scheme significantly relaxes assumptions on co-coercivity and contractiveness in the existing literature, where the projected stochastic subgradient method is applied to provide approximate solutions to the augmented best-response subproblems for each player. Finally, we illustrate the validity of the proposed algorithm through a Nash-Cournot production game.more » « less
-
In this paper, we develop distributed computation algorithms for Nash equilibriums of linear quadratic network games with proven differential privacy guarantees. In a network game with each player's payoff being a quadratic function, the dependencies of the decisions in the payoff function naturally encode a network structure governing the players' inter-personal influences. Such social influence structure and the individual marginal payoffs of the players indicate economic spillovers and individual preferences, and thus they are subject to privacy concerns. For distributed computing of the Nash equilibrium, the players are interconnected by a public communication graph, over which dynamical states are shared among neighboring nodes. When the players' marginal payoffs are considered to be private knowledge, we propose a distributed randomized gradient descent algorithm, in which each player adds a Laplacian random noise to her marginal payoff in the recursive updates. It is proven that the algorithm can guarantee differential privacy and convergence in expectation to the Nash equilibrium of the network game at each player's state. Moreover, the mean-square error between the players' states and the Nash equilibrium is shown to be bounded by a constant related to the differential privacy level. Next, when both the players' marginal payoffs and the influence graph are private information, we propose two distributed algorithms by randomized communication and randomized projection, respectively, for privacy preservation. The differential privacy and convergence guarantees are also established for such algorithms.more » « less
-
In this paper, we study the problem of distributed generalized stochastic Nash equilibrium seeking for robot systems over a connected undirected graph. We use the cost functions containing uncertainty to represent the system’s performance under varying conditions. To mitigate the challenges posed by this uncertainty, we employ the Tikhonov regularization scheme, which also helps us to relax the strongly monotone condition of the cost functions to the strictly monotone condition. We also consider the inequality constraints, which represent the feasible working space of robots. Additionally, auxiliary parameters are introduced in the control laws to facilitate seeing the variational generalized stochastic Nash equilibrium. The convergence of the proposed control laws is analyzed by using the operator splitting method. Finally, we demonstrate the effectiveness of the proposed algorithm through an example involving multiple robots connected through a communication network.more » « less
-
Markov games model interactions among multiple players in a stochastic, dynamic environment. Each player in a Markov game maximizes its expected total discounted reward, which depends upon the policies of the other players. We formulate a class of Markov games, termed affine Markov games, where an affine reward function couples the players’ actions. We introduce a novel solution concept, the soft-Bellman equilibrium, where each player is boundedly rational and chooses a soft-Bellman policy rather than a purely rational policy as in the well-known Nash equilibrium concept. We provide conditions for the existence and uniqueness of the soft-Bellman equilibrium and propose a nonlinear least-squares algorithm to compute such an equilibrium in the forward problem. We then solve the inverse game problem of inferring the players’ reward parameters from observed state-action trajectories via a projected-gradient algorithm. Experiments in a predator-prey OpenAI Gym environment show that the reward parameters inferred by the proposed algorithm outper- form those inferred by a baseline algorithm: they reduce the Kullback-Leibler divergence between the equilibrium policies and observed policies by at least two orders of magnitude.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/CDC45484.2021.9682862
