When can limited randomness be used in repeated games?

DOI10.1007/978-3-662-48433-3_20zbMATH Open1356.91010arXiv1507.01191OpenAlexW782722446MaRDI QIDQ506541FDOQ506541

Pavel Hubáček, Jonathan Ullman, Moni Naor

Publication date: 1 February 2017

Published in: Theory of Computing Systems, Algorithmic Game Theory (Search for Journal in Brave)

Abstract: The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the $n$-stage repeated version of the game exist if and only if both players have $Omega(n)$ random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the $n$-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on "random-like" sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators emph{do not} exist, then $Omega(n)$ random bits remain necessary for equilibria to exist.

Full work available at URL: https://arxiv.org/abs/1507.01191

Recommendations

• When can limited randomness be used in repeated games?
• Playing games with bounded entropy
• Algorithms for Playing Games with Limited Randomness
• The truth behind the myth of the folk theorem
• Not just an empty threat: subgame-perfect equilibrium in repeated games played by computationally bounded players

zbMATH Keywords

entropygame theoryNash equilibriumrepeated gamescryptographyone-way functionspseudorandom generatorsfinitely repeated gameslimited randomness

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Noncooperative games (91A10) Multistage and repeated games (91A20) Signaling and communication in game theory (91A28)

Cites Work

• Strategic entropy and complexity in repeated games
• Repeated games with bounded entropy
• Title not available (Why is that?)
• A Pseudorandom Generator from any One-way Function
• Long Cheap Talk
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Foundations of Cryptography
• Algorithmic rationality: game theory with costly computation
• Nash equilibria of finitely repeated games
• Finitely repeated games: a generalized Nash folk theorem
• Finitely Repeated Games
• Title not available (Why is that?)
• Algorithms for Playing Games with Limited Randomness

Cited In (3)

• Uniqueness and efficiency of Nash equilibrium in a family of randomly generated repeated games.
• Playing games with bounded entropy
• Algorithms for Playing Games with Limited Randomness

This page was built for publication: When can limited randomness be used in repeated games?

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