Games with symmetric incomplete information and asymmetric computational resources

International Game Theory Review. 2018. Vol. 20. No. 2. P. 1–16.

Kreps V. L., Gavrilovich M.

We consider random public signals on the state of two-person zero-sum game with incomplete information on both sides (both players do not know the state of the game). To learn the state, each player chooses a finite automaton which receives the public signal; the player only sees the output of the automaton chosen. Supposing that the size of automata available to Player 1 is essentially bigger than that available to Player 2, we give an example of public signal with random length of output strings where the posterior belief of Player 1 is the state and the posterior belief of Player 2 is close to his original belief. Thus, we demonstrate that asymmetric information about the state of a game may appear not only due to a private signal but as a result of a public signal and asymmetric computational resources of players.Besides, for a class of random signals with fixed length of output strings, we estimate the fraction of signals such that some automaton of given size may help Player 2 to significantly reestimate prior probability of the state. We show that this fraction is negligible if the size of automata of Player 2 is sufficiently smaller than length of output strings.

Keywords: incomplete information, asymmetry, zero-sum games, finite automata, posterior belief

Publication based on the results of: Mechanism Design: modern approaches (2018)