Strong approachability (Q482552): Difference between revisions

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\})\).