Approachability of convex sets in generalized quitting games
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3122013 (Why is no real title available?)
- scientific article; zbMATH DE number 3128733 (Why is no real title available?)
- scientific article; zbMATH DE number 18889 (Why is no real title available?)
- A Simple Adaptive Procedure Leading to Correlated Equilibrium
- A proof of calibration via Blackwell's approachability theorem.
- A zero-sum stochastic game with compact action sets and no asymptotic value
- An analog of the minimax theorem for vector payoffs
- Approachability in infinite dimensional spaces
- Approachability of convex sets in games with partial monitoring
- Approachability, regret and calibration: implications and equivalences
- Approachable sets of vector payoffs in stochastic games
- Belief-Free Equilibria in Games With Incomplete Information
- Belief-free communication equilibria in repeated games
- Belief-free equilibria in games with incomplete information: characterization and existence
- Calibrated learning and correlated equilibrium
- Calibration and internal no-regret with random signals
- Communication equilibrium payoffs in repeated games with imperfect monitoring
- Explicit formulas for repeated games with absorbing states
- Exponential weight approachability, applications to calibration and regret minimization
- Internal regret with partial monitoring: calibration-based optimal algorithms
- Optimal strategies in repeated games with incomplete information
- Repeated games with absorbing states
- Repeated games with incomplete information. With the collaboration of Richard E. Stearns
- Set-valued approachability and online learning with partial monitoring
- Stochastic Games
- Stochastic games
- The Asymptotic Theory of Stochastic Games
- The Big Match
- Weak Approachability
- Zero Sum Absorbing Games with Incomplete Information on One Side: Asymptotic Analysis
- Zero-sum repeated games: counterexamples to the existence of the asymptotic value and the conjecture \({\max}{\min}=\lim v_{n}\)
- ``Big Match with lack of information on one side. I
- ``Big match with lack of information on one side. II
Cited in
(6)- Approachability with constraints
- scientific article; zbMATH DE number 569952 (Why is no real title available?)
- An online convex optimization approach to Blackwell's approachability
- Weak approachability of convex sets in absorbing games
- Strong approachability
- Approachability of convex sets in games with partial monitoring
This page was built for publication: Approachability of convex sets in generalized quitting games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1651293)
