IDEAS home Printed from https://ideas.repec.org/p/huj/dispap/dp510.html
   My bibliography  Save this paper

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

Author

Listed:
  • Abraham Neyman

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.

Suggested Citation

  • Abraham Neyman, 2009. "The Maximal Variation of Martingales of Probabilities and Repeated Games with Incomplete Information," Discussion Paper Series dp510, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
  • Handle: RePEc:huj:dispap:dp510
    as

    Download full text from publisher

    File URL: http://ratio.huji.ac.il/sites/default/files/publications/dp510.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Robert J. Aumann, 1995. "Repeated Games with Incomplete Information," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262011476, December.
    2. MERTENS, Jean-François & ZAMIR, Shmuel, 1977. "The maximal variation of a bounded martingale," LIDAM Reprints CORE 309, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Abraham Neyman, 2012. "The value of two-person zero-sum repeated games with incomplete information and uncertain duration," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(1), pages 195-207, February.
    2. Abraham Neyman & Sylvain Sorin, 2010. "Repeated games with public uncertain duration process," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(1), pages 29-52, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Abraham Neyman, 2012. "The value of two-person zero-sum repeated games with incomplete information and uncertain duration," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(1), pages 195-207, February.
    2. Fedor Sandomirskiy, 2018. "On Repeated Zero-Sum Games with Incomplete Information and Asymptotically Bounded Values," Dynamic Games and Applications, Springer, vol. 8(1), pages 180-198, March.
    3. Abraham Neyman, 2013. "The Maximal Variation of Martingales of Probabilities and Repeated Games with Incomplete Information," Journal of Theoretical Probability, Springer, vol. 26(2), pages 557-567, June.
    4. Fedor Sandomirskiy, 2014. "Repeated games of incomplete information with large sets of states," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 767-789, November.
    5. Koessler, Frederic & Laclau, Marie & Renault, Jérôme & Tomala, Tristan, 2022. "Long information design," Theoretical Economics, Econometric Society, vol. 17(2), May.
    6. Dinah Rosenberg & Eilon Solan & Nicolas Vieille, 2003. "The MaxMin value of stochastic games with imperfect monitoring," International Journal of Game Theory, Springer;Game Theory Society, vol. 32(1), pages 133-150, December.
    7. Xiaochi Wu, 2022. "Existence of value for a differential game with asymmetric information and signal revealing," International Journal of Game Theory, Springer;Game Theory Society, vol. 51(1), pages 213-247, March.
    8. Dirk Bergemann & Stephen Morris, 2019. "Information Design: A Unified Perspective," Journal of Economic Literature, American Economic Association, vol. 57(1), pages 44-95, March.
    9. Andrew Kosenko, 2020. "Mediated Persuasion," Papers 2012.00098, arXiv.org, revised Dec 2020.
    10. Xiaochi Wu, 2021. "Differential Games with Incomplete Information and with Signal Revealing: The Symmetric Case," Dynamic Games and Applications, Springer, vol. 11(4), pages 863-891, December.
    11. Vida, Péter & Āzacis, Helmuts, 2013. "A detail-free mediator," Games and Economic Behavior, Elsevier, vol. 81(C), pages 101-115.
    12. Frédéric Koessler & Françoise Forges, 2008. "Multistage Communication With And Without Verifiable Types," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 10(02), pages 145-164.
    13. Marie Laclau & Tristan Tomala, 2016. "Repeated games with public information revisited," PSE Working Papers hal-01285326, HAL.
    14. Makoto Shimoji, 2016. "Rationalizable Persuasion," Discussion Papers 16/08, Department of Economics, University of York.
    15. Alp Atakan & Mehmet Ekmekci & Ludovic Renou, 2021. "Cross-verification and Persuasive Cheap Talk," Papers 2102.13562, arXiv.org, revised Apr 2021.
    16. Smolin, Alex & Ichihashi, Shota, 2022. "Data Collection by an Informed Seller," TSE Working Papers 22-1330, Toulouse School of Economics (TSE).
    17. , H. & ,, 2016. "Approximate efficiency in repeated games with side-payments and correlated signals," Theoretical Economics, Econometric Society, vol. 11(1), January.
    18. Andreas Haupt & Zoe Hitzig, 2023. "Opaque Contracts," Papers 2301.13404, arXiv.org.
    19. Elliot Lipnowski & Doron Ravid & Denis Shishkin, 2024. "Perfect Bayesian Persuasion," Papers 2402.06765, arXiv.org.
    20. Thomas Mariotti & Nikolaus Schweizer & Nora Szech & Jonas von Wangenheim, 2023. "Information Nudges and Self-Control," Management Science, INFORMS, vol. 69(4), pages 2182-2197, April.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:huj:dispap:dp510. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Michael Simkin (email available below). General contact details of provider: https://edirc.repec.org/data/crihuil.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.