What are Dynamic Games?

The Brief Explanation

Game theory reasons about two or more agents who have (potentially competing) objectives. Traditional game theory considers a one-step decision process: each agent considers how to play given their knowledge of the other agent, and then executes that play, and the game is over. Dynamic games (sometimes called differential games in continuous-time scenarios) are games that are played repeatedly (or continuously) over a time horizon. Some examples include chess, investing, missile interception, and multi-agent collision-avoidance.

General dynamic games are very challenging to solve in a computationally tractable manner. We consider a subset of these games that is a bit more tractable and very relevant to many applications: zero-sum dynamic games. Zero-sum games are adversarial: there is one objective (e.g., distance to collision), one agent is assumed to be maximizing this objective (e.g., avoiding collision), whereas the other agent is assumed to be minimizing the objective (e.g., causing collision). If you can solve for the set of conditions from which the ego-agent can avoid collision despite worst-case efforts from its adversary, then you have a certificate of robustness within that region. This can be useful in cases where the other agent is not actually adversarial. For example, an airplane should operate in a region of airspace where, even if another plane is taken over and suddenly becomes adversarial, the airplane can maneuver away safely.

The Thorough Explanation

The classic book to read would be “Dynamic Noncooperative Game Theory” by Tamer Basar and Geert Jan Olsder.

A more recent work is Smooth Game Theory from David Fridovich-Keil.

Most people think of Rufus Isaacs as the father of differential game theory, developed during his time at the RAND corporation in the 1950’s. His book, Differential Games, may be a nice historical perspective for those interested.

Why Study Zero-Sum Dynamic Games?

In addition to the explicit multi-agent games described above, analyzing zero-sum games is also useful for general robustness. Safety-critical systems operate under uncertainty: models are imperfect, environments are dynamic, and sensors have noise. If this uncertainty can be quantified, we can treat it as an adversary during analysis. This asks, for example, “from where can I safely land my quadcopter even under worst-case wind conditions?” by treating the wind as an adversary.

Our group develops methods that provide safety guarantees under these worst-case conditions. This includes differential game formulations where the controller must ensure safety against an antagonistic disturbance, distributionally robust control barrier functions that account for stochastic and distributional uncertainty directly from sensor measurements, and adaptive safety filters that refine learned value functions online as conditions change. By treating robustness as a first-class design objective rather than an afterthought, our approaches deliver safety guarantees that are meaningful in deployment.

Robustness and Dynamic Game Papers from our Group

We have some work on handling explicit adversaries, for example:

We also have work on treating model error as an adversary to construct robust control Lyapunov functions and robust control barrier functions. A fun implication of this type of analysis is that we can actually simplify our dynamics model to something more tractable, characterize the resulting model-mismatch error, and then solve a game treating this introduced modeling error as an adversary. This lets us plan during deployment using the simpler and faster model, with robustness guarantees for the full system model. We have two main lines of work for this:

Another source of uncertainty is in state estimation, or where the system is in its environment. We have worked on:

A related topic is being robust to uncertain or unknown environments, for example: