Testing Randomness by Matching Pennies
DOI:
https://doi.org/10.5644/SJM.20.01.04Keywords:
randomness, computability, algorithmic complexity, equilibrium, hypothesis testingAbstract
In the game of Matching Pennies, Alice and Bob each hold a penny, and at every tick of the clock they simultaneously display the head or the tail sides of their coins. If they both display the same side, then Alice wins Bob's penny; if they display different sides, then Bob wins Alice's penny. To avoid giving the opponent a chance to win, both players seem to have nothing else to do but to randomly play heads and tails with equal frequencies. However, while not losing in this game is easy, not missing an opportunity to win is not. Randomizing your own moves can be made easy. Recognizing when the opponent's moves are not random can be arbitrarily hard.
The notion of randomness is central in game theory, but it is usually taken for granted. The notion of outsmarting is not central in game theory, but it is central in the practice of gaming. We pursue the idea that these two notions can be usefully viewed as two sides of the same coin. The resulting analysis suggests that the methods for strategizing in gaming and security, and for randomizing in computation, can be leveraged against each other.
2010 Mathematics Subject Classification. 03D32,91A26,91A26, 68Q32.
Downloads
References
Samson Abramsky and Viktor Winschel. Coalgebraic analysis of subgame-perfect equilibria in infinite games without discounting. Mathematical Structures in Computer Science, 27(5):751–761, 2017.
Laurent Bienvenu, Glenn Shafer, and Alexander Shen. On the history of martingales in the study of randomness. Electronic Journal for History of Probability and Statistics, 5(1):1–40, June 2009.
Lenore Blum and Manuel Blum. Toward a mathematical theory of inductive inference. Information and Control, 28(2):125–155, 1975.
J.H. Conway. Regular Algebra and Finite Machines. Chapman and Hall mathematics series. Dover Publications, Incorporated, 2012.
Martin Davis, editor. The Undecidable : Basic papers on undecidable propositions, unsolvable problems, and computable functions. Raven Press, Helwett, N.Y., 1965.
Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer New York, 2010.
Albert Einstein and Hedwig Born. The Born-Einstein letters 1916–1955. Walker, New York, 1971.
Ronald A. Fisher. Statistical Methods for ResearchWorkers. Oliver and Boyd, Edinburgh, 1925.
Ronald A. Fisher. Statistical Methods and Scientific Inference. Oliver and Boyd, Edinburgh, UK, second edition, 1959.
E. Mark Gold. Language identification in the limit. Information and Control, 10(5):447–474, 1967.
Joseph Y. Halpern and Rafael Pass. Game theory with costly computation: Formulation and application to protocol security. In ndrew Chi-Chih Yao, editor, ICS, pages 120–142. Tsinghua University Press, 2010.
Joseph Y. Halpern and Rafael Pass. Sequential equilibrium in computational games. In Francesca Rossi, editor, IJCAI. IJCAI/AAAI, 2013.
Joseph Y. Halpern, Rafael Pass, and Lior Seeman. I’m Doing asWell as I Can: Modeling People as Rational Finite Automata. In J¨org Hoffmann and Bart Selman, editors, AAAI. AAAI Press, 2012.
Jules Hedges, Paulo Oliva, Evguenia Shprits, Viktor Winschel, and Philipp Zahn. Selection equilibria of higher-order games. In Yuliya Lierler and Walid Taha, editors, Practical Aspects of Declarative Languages - 19th International Symposium, PADL 2017, Paris, France, January 16-17, 2017, Proceedings, volume 10137 of Lecture Notes in Computer Science, pages 136–151. Springer, 2017.
John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Massachusetts, 1979.
Marcus Hutter. Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability. Springer-Verlag, Berlin, Heidelberg, 2010.
Vicki Knoblauch. Computable strategies for repeated prisoner’s dilemma. Games and Economic Behavior, 7(3):381–389, November 1994.
Andrey N. Kolmogorov. On tables of random numbers (Reprinted from ”Sankhya: The Indian Journal of Statistics”, Series A, Vol. 25 Part 4, 1963). Theor. Comput. Sci., 207(2):387–395, 1998.
Pierre-Simon Laplace. Essai Philosophique sur les Probabilit´es. H. Remy, Brussels, 1829. Ming Li and Paul M. B. Vit´anyi. An
introduction to Kolmogorov complexity and its applications (2. ed.). Graduate texts in computer science. Springer, 1997.
Per Martin-L¨of. The definition of random sequences. Information and Control, 9(6):602–619, 1966.
Richard von Mises. Probability, Statistics, and Truth. Dover Books on Mathematics Series. Dover Publications, 1957.
John H Nachbar and William R Zame. Non-computable strategies and discounted repeated games. Economic Theory, 8(1):103–22, June 1996.
Andre Nies. Computability and Randomness. Oxford University Press, Inc., New York, NY, USA, 2009.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007.
Dusko Pavlovic. A semantical approach to equilibria and rationality. In Alexander Kurz and Andzrej Tarlecki, editors, Proceedings of CALCO 2009, volume 5728 of Lecture Notes in Computer Science, pages 317–334. Springer Verlag, 2009. arxiv.org:0905.3548.
Dusko Pavlovic. Monoidal computer I: Basic computability by string diagrams. Information and Computation, 226:94–116, 2013. arxiv:1208.5205.
Dusko Pavlovic. Programs as Diagrams: From Categorical Computability to Computable Categories. Theory and Applications of Computability. Springer, September 2023.
Dusko Pavlovic and Muzamil Yahia. Monoidal computer III: A coalgebraic view of computability and complexity. In C. Crˆıstea, editor, Coalgebraic Methods in Computer Science (CMCS) 2018— Selected Papers, volume 11202 of Lecture Notes in Computer Science, pages 167–189. Springer, 2018. https://arxiv.org/abs/1704.04882.
Michael O Rabin. Effective computability of winning strategies. Contributions to the Theory of
Games, 3(39):147–157, 1957.
Jorma Rissanen. Information and Complexity in Statistical Modeling. Information science and statistics. Springer, New York, 2007.
Ariel Rubinstein. Modeling Bounded Rationality. Zeuthen lecture book series. MIT Press, 1998.
Glen Shafer and Vladimir Vovk. Probability and Finance: It’s Only a Game! Wiley Series in Probability and Statistics. Wiley, 2005.
Ray J. Solomonoff. A formal theory of inductive inference. Part I., Part II. Information and Control, 7:1–22, 224–254, 1964.
Alan M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society. Second Series, 42:230–265, 1936. Reprinted in [5].
Jean-Andr´e Ville. Sur la notion de collectif. Comptes Rendus, 203:26–27, July 1936.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005.
Vladimir Vovk and Dusko Pavlovic. Universal probability-free prediction. Ann. Math. Artif. Intell., 81(1-2):47–70, 2017. arxiv.org:1603.04283.
C.S. Wallace. Statistical and Inductive Inference by Minimum Message Length. Information Science and Statistics. Springer, 2005.
Terry A.Welch. A technique for high-performance data compression. IEEE Computer, 17(6):8– 19, 1984.
J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theor., 24(5):530–536, September 2006.
A. K. Zvonkin and L. A. Levin. The complexity of finite objects and the algorithmic concepts of information and randomness. Russian Math. Surveys, 25(6):83–124, 1970.
