Approachability of convex sets in games with partial monitoring

DOI10.1007/S10957-011-9797-3zbMATH Open1220.91005arXiv1102.4439OpenAlexW2019199866MaRDI QIDQ637538FDOQ637538

Authors: Vianney Perchet 

Publication date: 6 September 2011

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Abstract: We provide a necessary and sufficient condition under which a convex set is approachable in a game with partial monitoring, i.e. where players do not observe their opponents' moves but receive random signals. This condition is an extension of Blackwell's Criterion in the full monitoring framework, where players observe at least their payoffs. When our condition is fulfilled, we construct explicitly an approachability strategy, derived from a strategy satisfying some internal consistency property in an auxiliary game. We also provide an example of a convex set, that is neither (weakly)-approachable nor (weakly)-excludable, a situation that cannot occur in the full monitoring case. We finally apply our result to describe an $epsilon$-optimal strategy of the uninformed player in a zero-sum repeated game with incomplete information on one side.

Full work available at URL: https://arxiv.org/abs/1102.4439

Recommendations

• A primal condition for approachability with partial monitoring
• On a unified framework for approachability with full or partial monitoring
• Approachability of convex sets in generalized quitting games
• Set-valued approachability and online learning with partial monitoring
• A Necessary and Sufficient Condition for Approachability

zbMATH Keywords

repeated gamesincomplete informationconvex setspartial monitoringBlackwell approachability

Mathematics Subject Classification ID

Multistage and repeated games (91A20) Signaling and communication in game theory (91A28)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Calibrated learning and correlated equilibrium
• Repeated games with incomplete information. With the collaboration of Richard E. Stearns
• Repeated games and qualitative differential games: approachability and comparison of strategies
• An analog of the minimax theorem for vector payoffs
• Weighted sums of certain dependent random variables
• Calibration and internal no-regret with random signals
• Weak Approachability
• Optimal strategies in repeated games with incomplete information

Cited In (9)

• A differential game on Wasserstein space. Application to weak approachability with partial monitoring
• On a unified framework for approachability with full or partial monitoring
• Approachability of convex sets in generalized quitting games
• Title not available (Why is that?)
• Set-valued approachability and online learning with partial monitoring
• Approachability with delayed information
• A primal condition for approachability with partial monitoring
• Zero-sum repeated games: recent advances and new links with differential games
• Approachability, regret and calibration: implications and equivalences

This page was built for publication: Approachability of convex sets in games with partial monitoring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q637538)