We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A NECESSARY AND SUFFICIENT CONDITION FOR APPROACHABILITY.
- Authors
Spinat, Xavier
- Abstract
Approachability in games with vector payoffs (Blackwell 1956) has found many applications in game theory, for example, in the study of repeated games with lack of information on one side (Aumann and Maschler 1995) or in problems of calibration and learning processes (Foster and Vohra 1997, Hart and Mas-Colell 1997). In a two-person repeated game with vector payoffs, a set F is approachable by a player if he can guarantee that the average payoff will remain forever close to F from some stage on with an arbitrarily large probability. Approachability itself is difficult to prove because its definition involves the existence of a strategy that gives a uniformly good asymptotic distribution of the payoff. Blackwell solved this difficulty by introducing a very useful sufficient condition for approachability. We will use two features of this condition. First, Blackwell's condition, based on geometric considerations, is simple to verify and is also a necessary condition in the case of convex sets. Second, Blackwell's condition gives an explicit way to construct specific approachability strategies that satisfy several useful properties. Those strategies are, for example, robust to discretization or random perturbation. In the first section of this paper, we set some notations and recall the main result obtained by Blackwell. In the second section, we introduce the notion of secondary points for a set: These points are "useless" (in the sense of approachability). In the third section, we reduce any approachable set to a subset in which there are no such secondary points and therefore, using appropriate reductions, we show the main result of the paper: A set F is approachable if and only if a subset of F satisfies Blackwell's condition. The fourth section of this paper is devoted to certain properties of the approachability strategies induced by Blackwell's condition, and we use the main result to prove that robust approachability strategies exist in the general case....
- Subjects
GAME theory; PROBABILITY theory; VECTOR analysis; GEOMETRIC probabilities; DECISION making; DECISION theory; PERTURBATION theory
- Publication
Mathematics of Operations Research, 2002, Vol 27, Issue 1, p31
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.27.1.31.333