Strong approachability
Let \(I\), \(J\) be finite sets of actions and \(u:I\times J \to \mathbb{R}^d\) a vector payoff function. Denote by \(\Delta(I)\) and \(\Delta(J)\) the simplices of probability distributions over \(I\) and \(J\) respectively. The payoff \(u\) for pure actions extends to expected payoffs for mixed actions \(p\in\Delta(I)\), \(q\in\Delta(J)\) as follows: \(u(p,q) = \sum_{i\in I} \sum_{j\in J} p_i u(i,j) q_j\). Single shot game is played by two agents who choose their actions \(p,q\) independently and simultaneously and receive payoff \(u(p,q)\). (The scheme includes zero-sum games and is important for modelling auctions, as explained in the paper). The two agents can play single shot game repeatedly. This leads to the sequence of actions \((p^n,q^n)_{n=1}^{\infty}\). A strategy of player 1 is \(\sigma_1: \bigcup_{n=1}^{\infty} (\Delta(I)\times \Delta(J))^{n-1} \to \Delta(I)\). That is, given the history \(h_{n-1}= (p^k,q^k)_{k=1}^{n-1}\) player 1 has a plan to choose at the stage \(n\) a mixed action \(p^n=\sigma_1(h_{n-1})\). Similarly, for a strategy \(\sigma_2\) of player 2. The sequence of actions \((p^n,q^n)_{n=1}^{\infty}\) is uniquely determined by a pair of strategies \((\sigma_1,\sigma_2)\); different strategies may yield the same actions. The average payoff in the first \(N\) stages is \(g^N= \frac{1}{N} \sum_{n=1}^{N} u(p^n,q^n)\). A nonempty set \(A\subset \mathbb{R}^d\) is (i) approachable, (ii) strongly approachable by player 1 if he can plan a strategy \(\sigma_1\) so that for every \(\varepsilon >0\) there exists \(N\) such that (i) \(dist(g^n,A) <\varepsilon\), (ii) \(g^{n}\in A\) at all stages \(n\geq N\) no matter how smart strategy \(\sigma_2\) applies player 2. Every strongly approachable set is approachable. An epsilon-neighbourhood of an approachable set is strongly approachable. The subject of the work are general criteria for strong approachability of closed convex sets. Given payoff function \(u\) and vector \(\lambda\in\mathbb{R}^d\) one defines a scalar zero-sum game with payoff \(w:I\times J\to \mathbb{R}\), \(w(i,j) = \langle\lambda,u(i,j)\rangle\). Its value is denoted by \(V_\lambda\). Proposition 11: Let \(A\) be a closed convex set with nonempty \(Int(A)\). If \(V_{\lambda} > \inf_{a\in A} \langle\lambda, a\rangle\) for \(\lambda\neq 0\), then \(A\) is strongly approachable by player 1. Note for comparison that if \(A\) is approachable, then \(V_{\lambda} \geq \inf_{a\in A} \langle\lambda, a\rangle\). Thus one is led to study strong approachability when \(S= \{\lambda\in\mathbb{R}^d| V_{\lambda} = \inf_{a\in A} \langle\lambda, a\rangle, \|\lambda\| =1 \}\) is nonempty. For closed convex \(A\) denote by \(H_{\lambda}\) a supporting hyperplane of \(A\) such that \(\lambda\) is an outer-pointing normal vector to \(A\) at a point \(a\in A\cap H_{\lambda}\); the closed half-space containing \(A\) is \(\overline{H}_{\lambda}^{-}\). Denote \(R_1(p) = u(\{p\}\times \Delta(J))\) for \(p\in\Delta(I)\). Theorem 15: Let \(A\) be a closed convex approachable set with nonempty interior. Assume that for every \(\lambda\in S\) (1) there is exactly one set \(R_1(p_{\lambda})\subset \overline{H}_{\lambda}^{-}\) (still \(p_{\lambda}\in\Delta(I)\) may not be unique), (2) every point in \(R_1(p_{\lambda})\cap H_{\lambda}\cap A\) is a smooth boundary point of \(A\). The set \(A\) is strongly approachable by player 1 if and only if there exists \(R_1(p^{*})\) such that (C0) \(R_1(p^{*}) = R_1(p_{\lambda})\), (C1) \(R_1(p^{*}) \cap H_{\lambda} \cap A \neq \emptyset\), and (C2) any point in \(R_1(p^{*})\cap H_{\lambda}\) has a neighbourhood \(\mathcal{N}\) such that \(R_1(p^{*})\cap \mathcal{N} \subset A\), for every \(\lambda\in S\). A simple criterion (related to Proposition 11) provides Corollary 10: If \(A\) is a closed convex set and \(Int(A)\cap R_2(q)\) is nonempty for every \(q\in\Delta(J)\), then \(A\) is strongly approachable by player 1; \(R_2(q) = u(\Delta(I)\times \{q\})\).
- A Necessary and Sufficient Condition for Approachability
- A Simple Adaptive Procedure Leading to Correlated Equilibrium
- An analog of the minimax theorem for vector payoffs
- Approachability in a Two-person Game
- Approachability in infinite dimensional spaces
- Calibrated learning and correlated equilibrium
- Convex Analysis
- Game theory. Translated from the Hebrew by Ziv Hellman and edited by Mike Borns
- Motzkin decomposition of closed convex sets
- Optimal strategies in repeated games with incomplete information
- Prediction, Learning, and Games
- Repeated games with incomplete information. With the collaboration of Richard E. Stearns
- Stochastic Games with a Single Controller and Incomplete Information
- The Game of Normal Numbers
- Zero-sum repeated games: recent advances and new links with differential games
- Approachability in repeated games: Computational aspects and a Stackelberg variant
- Approachability in infinite dimensional spaces
- Approachability of convex sets in generalized quitting games
- Recent contributions to linear semi-infinite optimization
- Recent contributions to linear semi-infinite optimization: an update
- Approachability with constraints
- Approachable sets of vector payoffs in stochastic games
- Attainability in repeated games with vector payoffs
- Repeated games and qualitative differential games: approachability and comparison of strategies
- Weak Approachability
- A primal condition for approachability with partial monitoring
- A Necessary and Sufficient Condition for Approachability
- Weak approachability of convex sets in absorbing games
This page was built for publication: Strong approachability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482552)
