The Maximal Variation of Martingales of Probabilities and Repeated Games with Incomplete Information |
| |
Authors: | Abraham Neyman |
| |
Affiliation: | 1. Institute of Mathematics, and Center for the Study of Rationality, The Hebrew University of Jerusalem, Givat Ram, Jerusalem, 91904, Israel
|
| |
Abstract: | The variation of a martingale $p_{0}^{k}=p_{0},ldots,p_{k}$ of probabilities on a finite (or countable) set X is denoted $V(p_{0}^{k})$ and defined by $$ Vbigl(p_0^kbigr)=EBiggl(sum_{t=1}^k|p_t-p_{t-1}|_1Biggr). $$ It is shown that $V(p_{0}^{k})leqsqrt{2kH(p_{0})}$ , where H(p) is the entropy function H(p)=?∑ x p(x)logp(x), and log stands for the natural logarithm. Therefore, if d is the number of elements of X, then $V(p_{0}^{k})leqsqrt{2klog d}$ . It is shown that the order of magnitude of the bound $sqrt{2klog d}$ is tight for d≤2 k : there is C>0 such that for all k and d≤2 k , there is a martingale $p_{0}^{k}=p_{0},ldots,p_{k}$ of probabilities on a set X with d elements, and with variation $V(p_{0}^{k})geq Csqrt{2klog d}$ . An application of the first result to game theory is that the difference between v k and lim j v j , where v k is the value of the k-stage repeated game with incomplete information on one side with d states, is bounded by $|G|sqrt{2k^{-1}log d}$ (where ∥G∥ is the maximal absolute value of a stage payoff). Furthermore, it is shown that the order of magnitude of this game theory bound is tight. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|