scientific article; zbMATH DE number 15815

In at least two different applications in game theory, one needs good approximations of \([0, 1]\)-valued functions by \(\{0, 1\}\)-valued ones: for the Shapley value of non-atomic games, the interpretation being the approximation of an ``ideal coalition by a real coalition, and also for the approximation of mixed strategies by pure strategies [see \textit{R. J. Aumann}, \textit{Y. Katznelson}, \textit{R. Radner}, \textit{R. W. Rosenthal} and \textit{B. Weiss}, Math. Oper. Res. 8, 327--341 (1983; Zbl 0532.90101)]. This second type of application was already a classical problem in statistical decision theory (existence of non-randomized procedures; see \textit{A. Dvoretzky}, \textit{A. Wald} and \textit{J. Wolfowitz}, Pac. J. Math. 1, 59- 74 (1951; Zbl 0044.15001)). Somewhat more generally, one wants to approximate functions with values in a simplex by functions with values in the extreme points of that simplex: in the second type of application, this means one wants the result to be applicable to problems with more than two actions or decisions, and in the first, this will allow to approximate any finite increasing sequence of ideal coalitions by a similar sequence of real coalitions. Two types of results are known. The first type deals with exact approximation on a fixed finite set of measures -- such are the theorems of Lyapunov and Dvoretzky-Wald-Wolfowitz. Thus, for any measurable function \(f\) with values in the simplex \(\Delta(A)\), and for any finite set of non-atomic measures \(\mu_ i\), there exist measurable functions \(\widetilde f\) with values in \(A\), such that \(\mu_ i(\widetilde f)= \mu_ i(f)\) for all \(i\). We show (Theorem 2.2) that one can in addition dispense in this statement with the requirement of countable additivity (it suffices that each \(\mu_ i\) be finitely additive, bounded, and nonatomic), and that \(f\) can be uniformly approximated by convex combinations of such functions \(\widetilde f\). This allows to enlarge the space EXT of games that have an extension so as to include the whole of \(bv'\text{FA}\) (and in particular FA itself, and all polynomials in elements of FA). Indeed, finite additivity is now allowed, and the uniform approximation by convex combinations allows to deal properly with the atomic parts. As a consequence, the value is now a projection of norm 1 onto FA, and is defined on a space that includes all finite games, and much more is gained. Along the way, we also obtain an extension to all of FA -- the dual of the space of bounded measurable functions on some \(\sigma\)-field -- of a classical criterion of weak-compactness in the space of measures: a subset of FA is weakly relatively compact iff any sequence contains a weak\(^*\)-convergent subsequence (i.e., a subsequence along which the integral of any bounded measurable function converges). The second type of known results (loc. cit.) says essentially that, for any fixed measure \(Q\) on the set of nonatomic probabilities \(\nu\) on the space, \(f\) can be approximated by functions \(\widetilde f\) in the sense that \(\nu(\widetilde f)\) converges to \(\nu(f)\) in measure \((Q(d\nu))\). Indeed, consider a game with incomplete information, where \(s\) is the signal to player I, \(t\) that to player II (the set of player I's opponents), \(a_{ij}(s, t)\) is the corresponding payoff (vector), with \(i\) and \(j\) the actions of players I and II. Let \(s\) and \(t\) be chosen at random with \(\nu_ t(ds)\) and \(Q(dt)\), where each \(\nu_ t\) is nonatomic. Denote by \(x_ i(s)\) and \(y_ j(t)\) mixed strategies of both players: the payoff is \[ \int Q(dt) \sum_ j y_ j(t) \int \sum_ i x_ i (s) a_{ij}(s, t) \nu_ t(ds). \] Denote by \(Q^{ij}(d\mu)\) the distribution of the nonatomic measures (on \(S\)) \(\mu_ t(ds)= a_{ij}(s,t) \nu_ t(ds)\). Then if \(\int \widetilde x d\mu\) approximates \(\int x d\mu\) in measure under all measures \(Q^{ij}(d\mu)\) (or for \(\sum_{ij} Q^{ij}\)), the inner integral with \(\widetilde x\) is \(\varepsilon\)-close (in measure) to the inner integral with \(x\), so that, \(y\) being bounded, the payoff with \(\widetilde x\) is uniformly (over \(y\)) \(\varepsilon\)-close to the payoff with \(x: \widetilde x\) is an \(\varepsilon\)-purification of \(x\). We show: (a) that this is really an approximation for some locally convex topology \(\mathcal T\) on the space of bounded measurable functions -- i.e., for a topology of uniform convergence on some class \(\mathcal E\) of compact, convex, symmetric subsets of the (weak\(^*\)) dual (the equicontinuous subsets); (b) that those equicontinuous subsets of the dual (and hence the topology) can be characterized only in terms of the dual as a normed vector space, or as an ordered vector space; (c) that countable additivity of the non-atomic measure \(\nu_ t\) is superfluous: one can work with the non-atomic elements of the full dual, and obtain in this way a much stronger topology. Those results imply in particular that one could also define the extension of a game as an extension by continuity for the topology \(\mathcal T\). As noted at the end of Section 5, the only thing missing to be able to use the full strength of this result is a more direct characterization of the sets in \(\mathcal E\): without it, everything still depends on being able to find approximations of the game with specific representations in terms of a distribution on non-atomic measures. But the results of (b) (and (c)) above suggest there should be such a simple and direct characterization. We also show that the two above approaches for defining the extension of a game are mutually compatible; in particular, no inconsistency could arise (say a lack of linearity or of positivity of the Shapley value) from using one approach in one problem and the other in another. On the contrary, in the restatement of the Lyapunov-Dvoretzky-Wald-Wolfowitz Theorem in the beginning of this introduction, one can further require all functions \(\widetilde f\) to belong to any fixed neighbourhood of \(f\) in terms of the \({\mathcal T}\)-topology. Finally, in Section 6, we apply the previous results to the definition of the extension of a game, and we show that the correct definition suggested by Theorem 2.2 already yields the extension for \({\mathcal T}\)- continuous games: as far as concerns the extension of games, Theorem 5.2 yields in principle nothing more than Theorem 2.2. But it remains of course true, as observed above, that for practical applications, it would be extremely useful to have a direct characterization of the class \(\mathcal E\). [For the entire collection see Zbl 0707.00031.]

Recommendations

Cited in

(6)

This page was built for publication:

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