Approachability of convex sets in generalized quitting games

János Flesch, Rida Laraki, Vianney PerchetGames Econ. Behav 2016 · OpenReview

TL;DR

This paper extends Blackwell's approachability theory to "generalized quitting games," a class of repeated games where players can choose to "quit" and end the game. The authors introduce new geometric conditions for a player to guarantee their expected payoff approaches a target set, and show these conditions are crucial for understanding game determinacy, especially in variations of the "Big-Match" game.

What Problem Does This Paper Address?

Blackwell's approachability theory provides a powerful tool for analyzing repeated games, particularly for designing strategies for players with incomplete information. It focuses on whether a player can steer their expected payoff towards a specific convex target set. However, this theory was primarily developed for simpler game structures. This paper tackles the challenge of extending this framework to "generalized quitting games." These games are more complex because players have the option to quit at any stage, leading to an absorbing state with a potentially different payoff. This quitting mechanism introduces new strategic considerations and complicates the analysis of approachability, especially when comparing "weak" (strategy can depend on horizon) and "uniform" (strategy must be independent of horizon) notions of approachability. The authors aim to provide a characterization of approachable sets in these more general games and explore the relationship between weak and uniform approachability.

Methods

The core of the paper lies in introducing and analyzing three new geometric conditions for weak approachability. These conditions are nested and inspired by existing work on absorbing games and asymptotic values. The authors prove that the first condition is sufficient for weak approachability, while the third is necessary. They then apply these conditions to specific subclasses of games: "Big-Match games of type I" (only player 1 can quit) and "Big-Match games of type II" (only player 2 can quit). For these specific cases, they establish equivalences between their new conditions and Blackwell's classical condition, leading to full characterizations of weak approachability. The paper also leverages techniques from differential games and calibration algorithms to construct strategies and prove their results.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Generalizing Approachability: The paper successfully extends Blackwell's approachability concept to a richer class of games with quitting actions, opening up new avenues for strategic analysis in complex repeated games.
  • Geometric Conditions are Key: The introduction of three specific geometric conditions provides a powerful analytical framework for understanding approachability in these games. The interplay between sufficiency and necessity of these conditions is a central theme.
  • Big-Match Games as a Testbed: Analyzing "Big-Match" games (where only one player can quit) proves crucial. It reveals how the structure of quitting actions (who can quit, and how many options they have) dramatically impacts the conditions for approachability.
  • Weak vs. Uniform Approachability Divergence: A significant finding is that, unlike in simpler settings, weak approachability does not imply uniform approachability in generalized quitting games. This highlights the strategic impact of the horizon-dependent nature of weak strategies.
  • Determinacy is Not Universal: The paper demonstrates that while some subclasses of these games are "weakly determined" (every convex set is either weakly approachable or weakly excludable), this property does not hold universally, especially when considering uniform approachability.

Key Results

  • The authors introduce three geometric conditions for weak approachability in generalized quitting games. Condition (1) is sufficient, and Condition (3) is necessary.
  • In "Big-Match games of type I" (player 1 quits), their three conditions are equivalent to Blackwell's classical condition, leading to weak determinacy.
  • In "Big-Match games of type II" (player 2 quits), Conditions (1) and (2) are equivalent and sufficient for uniform approachability, but Condition (3) is not necessarily sufficient for weak approachability.
  • The paper shows that weak approachability does not imply uniform approachability in these games, and uniform determinacy fails in certain Big-Match game types.

Limitations and Future Work

The paper acknowledges that the explicit construction of approachability strategies, while provided, can be delicate and relies on calibration techniques. The rates of convergence in these strategies can decrease with the dimension of the payoff space, suggesting a need for further research into more efficient algorithms. The question of whether weak determinacy holds for "Big-Match games of type II" remains open. Additionally, the paper hints at the complexity of extending these results to games with imperfect monitoring or non-convex target sets, which are areas for future exploration.

Summary updated

Abstract

We consider Blackwell approachability, a very powerful and geometric tool in game theory, used for example to design strategies of the uninformed player in repeated games with incomplete information. We extend this theory to "generalized quitting games" , a class of repeated stochastic games in which each player may have quitting actions, such as the Big-Match. We provide three simple geometric and strongly related conditions for the weak approachability of a convex target set. The first is sufficient: it guarantees that, for any fixed horizon, a player has a strategy ensuring that the expected time-average payoff vector converges to the target set as horizon goes to infinity. The third is necessary: if it is not satisfied, the opponent can weakly exclude the target set. In the special case where only the approaching player can quit the game (Big-Match of type I), the three conditions are equivalent and coincide with Blackwell's condition. Consequently, we obtain a full characterization and prove that the game is weakly determined-every convex set is either weakly approachable or weakly excludable. In games where only the opponent can quit (Big-Match of type II), none of our conditions is both sufficient and necessary for weak approachability. We provide a continuous time sufficient condition using techniques coming from differential games, and show its usefulness in practice, in the spirit of Vieille's seminal work for weak approachability.Finally, we study uniform approachability where the strategy should not depend on the horizon and demonstrate that, in contrast with classical Blackwell approacha-bility for convex sets, weak approachability does not imply uniform approachability.
BibTeX
@inproceedings{flesch2016approachability,
  author = {János Flesch and Rida Laraki and Vianney Perchet},
  title = {{Approachability of convex sets in generalized quitting games}},
  booktitle = {Games Econ. Behav},
  year = {2016},
  url = {https://openreview.net/forum?id=Uw2wxHVRPPx},
}
Figure