The Maximal Variation of Martingales of Probabilities and Repeated Games with Incomplete Information

Abraham Neyman ()

Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem

Abstract: The variation of a martingale m[k] of k+1 probability measures p(0),...,p(k) on a finite (or countable) set X is the expectation of the sum of ||p(t)-p(t-1)|| (the L one norm of the martingale differences p(t)-p(t-1)), and is denoted V(m[k]). It is shown that V(m[k]) is less than or equal to the square root of 2kH(p(0)), where H(p) is the entropy function (the some over x in X of p(x)log p(x) and log stands for the natural logarithm). Therefore, if d is the number of elements of X, then V(m[k]) is less than or equal to the square root of 2k(log d). It is shown that the order of magnitude of this bound is tight for d less than or equal to 2 to the power k: there is C>0 such that for every k and d less than or equal to 2 to the power k there is a martingale m[k]=p(0),...,p(k) of probability measures on a set X with d elements, and with variation V(m[k]) that is greater or equal the square root of Ck(log d). It follows that the difference between the value of the k-stage repeated game with incomplete information on one side and with d states, denoted v(k), and the limit of v(k), as k goes to infinity, is bounded by the maximal absolute value of a stage payoff times the square root of 2(log d)/k, and it is shown that the order of magnitude of this bound is tight.

Pages: 11 pages
Date: 2009-04
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://ratio.huji.ac.il/sites/default/files/publications/dp510.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://ratio.huji.ac.il/sites/default/files/publications/dp510.pdf [302 Moved Temporarily]--> https://ratio.huji.ac.il/sites/default/files/publications/dp510.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:huj:dispap:dp510

Access Statistics for this paper

More papers in Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem Contact information at EDIRC.
Bibliographic data for series maintained by Michael Simkin ().