A differential game on Wasserstein space. Application to weak approachability with partial monitoring

Vianney Perchet, Marc QuincampoixarXiv 2018 · OpenReview

TL;DR

This paper bridges the gap between discrete repeated games and continuous differential games by introducing a novel framework on Wasserstein spaces. This allows them to prove a fundamental result: any target set in this generalized setting is either "weakly approachable" or "weakly excludable," extending previous findings to scenarios with partial information.

What Problem Does This Paper Address?

The paper tackles the challenge of understanding "approachability" in game theory, particularly in repeated games where players aim to steer the average outcome towards a target set. While this concept is well-studied in discrete settings with full information, extending it to continuous-time games and scenarios with partial monitoring (where players don't observe everything) is complex. Traditional approaches often rely on differential games in Euclidean spaces, but these don't directly handle the probabilistic nature of information in partial monitoring. The authors aim to generalize approachability results to these more complex settings by leveraging differential games on Wasserstein spaces, which are well-suited for representing probability distributions.

Methods

The core of the paper involves two main methodological contributions:

  1. Differential Game on Wasserstein Space: The authors introduce a new differential game whose state space is the Wasserstein space of probability distributions. This allows them to model scenarios where outcomes are themselves probability measures, a natural fit for partial monitoring. They prove the existence of a value for this game, a crucial step for analyzing its properties.
  2. New Strategy Concept: To bridge the gap between continuous differential games and discrete repeated games, they introduce a new class of "non-anticipative with delay piecewise-constant strategies" (NADC). This strategy concept is designed to be more amenable to discretization and directly connects to strategies used in repeated games. They demonstrate that this new strategy class yields the same game values as more traditional "non-anticipative with delay" (NAD) strategies.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Wasserstein Space as a Natural Playground: The paper highlights that the Wasserstein space is a powerful tool for modeling games with probabilistic information, effectively unifying partial monitoring scenarios with full monitoring frameworks.
  • Generalization of Approachability: The central result is a significant generalization of Blackwell's approachability theorem. It proves that in this new, more general setting, any target set is either weakly approachable or weakly excludable, providing a fundamental dichotomy.
  • Bridging Continuous and Discrete: The introduction of NADC strategies is a key innovation that elegantly connects the continuous-time differential game to discrete-time repeated games, facilitating the transfer of results between these domains.
  • Value Existence is Key: Proving the existence of a value for the differential game on Wasserstein space is a critical technical achievement that underpins the subsequent approachability results.

Key Results

  • Existence of Value: The paper establishes the existence of a value for the introduced differential game on Wasserstein space.
  • Weak Approachability/Excludability Dichotomy: They prove that any closed set in the generalized setting (related to partial monitoring) is either weakly approachable or weakly excludable.
  • Equivalence of Strategy Classes: The paper demonstrates that their newly defined NADC strategies yield the same game values as traditional NAD strategies, simplifying analysis and connecting to repeated game strategies.
  • Connection to Previous Work: The authors show how their framework can recover and provide alternative proofs for existing results in Euclidean spaces, such as Vieille's result on weak approachability.

Limitations and Future Work

  • Technical Complexity: The use of Wasserstein spaces and differential games introduces significant mathematical complexity, which might limit direct application by researchers outside of specialized fields.
  • Compatibility Condition: While the paper proves that any set satisfying a "suitable compatibility condition" is either weakly approachable or excludable, the exact nature and tractability of this condition in practical scenarios are not fully explored.
  • Future Work: The authors suggest that their framework can be extended to other game theory concepts and potentially applied to more complex scenarios in machine learning and economics. Further exploration of the compatibility condition and its implications for specific problem types would be valuable.

Summary updated

Abstract

Studying continuous time counterpart of some discrete time dynamics is now a standard and fruitful technique, as some properties hold in both setups. In game theory, this is usually done by considering differential games on Euclidean spaces. This allows to infer properties on the convergence of values of a repeated game, to deal with the various concepts of approachability, etc. In this paper, we introduce a specific but quite abstract differential game defined on the Wasserstein space of probability distributions and we prove the existence of its value. Going back to the discrete time dynamics, we derive results on weak approachability with partial monitoring: we prove that any set satisfying a suitable compatibility condition is either weakly approachable or weakly excludable. We also obtain that the value for differential games with nonanticipative strategies is the same that those defined with a new concept of strategies very suitable to make links with repeated games.
BibTeX
@misc{perchet2018differential,
  author = {Vianney Perchet and Marc Quincampoix},
  title = {{A differential game on Wasserstein space. Application to weak approachability with partial monitoring}},
  year = {2018},
  eprint = {1811.04575},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.04575},
}
Figure