Stackelberg Games: Applications and Solutions
Abstract
Stackelberg Games: Solutions and ApplicationsProject Summary: Approved for public releaseZero-sum games are used to model situations in which the interests of two agents, or teams of agents, are diametrically opposed: e.g., chess or soccer. While such games are relatively well understood, they fail to model problems involving multiple agents whose interests may not be diametrically opposed: i.e., potentially win-win situations. A canonical example of a potential win-win situation is a bargaining problem, where two (or more) players can both #win# (i.e., improve their joint lot) by cooperating, but it remains for them to decide how to share the proceeds. Such general-sum settings are far more difficult to analyze, and hence far less well understood. We propose to study general-sum sequential, i.e., Stackelberg, games. Two-player Stackelberg games are characterized by a leader and a follower, and can be formalized as bilevel optimization problems, in which the leader aims to optimize anupper-level function whose value is determined by the follower#s choice, which is intended to optimize a lower-level function. In a game with multiple leaders and followers, the followers are assumed to play a Nash equilibrium in the game defined by the leaders# choices, which are themselves also assumed to comprise a Nash equilibrium. The goal of this proposal is to develop efficient, i.e., polynomial-time, algorithms that compute equilibria in general-sum Stackelberg games. Furthermore, we seek to generalize well-known results for one-shot zero-sum games, as well as our own proposed research on one-shot general-sum Stackelberg games, to the stochastic setting, which can be understood as bi-level Markov decision processes, or more generally, games. Examples of stochastic Stackelberg games abound. A reach-avoid problem is one in which an agent is navigating to a goal, while trying to avoid colliding with obstacles. These problems are often modeled as stochastic zero-sum simultaneous-move games, as the agent can find a more robust policy in the presence of an adversary than otherwise. We intend to take this idea one step further: to model the problem as a stochastic zero-sum Stackelberg game, in which the adversary moves first, constraining the agent#s feasible actions; by endowing the adversary with even more power, we expect the agent to discover an even more robust policy. Solving this game requires developing algorithms that compute (or, more generally, learn from samples) Stackelberg equilibrium policies in stochastic zero-sum Stackelberg games. Human assistance and disaster relief can also be viewed as a stochastic Stackelberg game, with the Department of Defense (DoD) as the leader, and humanitarian organizations as followers. Followinga disaster, the DoD allocates recovery resources (water, blankets, personnel, etc.) to various organizations on the ground, who must coordinate their behavior to assist affected populations, while at the same time pursuing their own objectives (e.g., ensuring thesafety of their responders). The algorithms we seek to develop in this work should someday assist the DoD in optimizing resource allocation for human assistance and disaster relief and any similar challenge, in which the DoD has the power to play the role of a leader, with other military or humanitarian units acting as a coalition of followers.The proposed work is Fundamental Research, and isto develop technology for both military and civil application.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412657
Entities
People
- Amy Greenwald
Organizations
- Brown University
- Office of Naval Research
- United States Navy