Brown Bag Seminar: Zsombor Z. Méder

Being Random - An Impractical Guide. Algorithmic Information Theory Meets Game Theory

Zsombor Z. MÉDER, Singapore University of Technology and Design

(with Shuige Liu)

Nash equilibrium often requires players to adopt a mixed strategy, i.e., a randomized choice between pure strategies. Typically, the player is asked to use some randomizing device, and the story usually ends here. In this talk, I will argue that:

1. game theory needs to give an account of what counts as a random sequence (of behavior);
2. from a game-theoretic perspective, a plausible account of randnomness is given by algorithmic complexity theory, and, in particular, the complexity measure proposed by Kolmogorov;
3. in certain contexts, strategic reasoning amounts to modelling the opponent’s mind as a Turing machine;
4. this account of random behavior also highlights some interesting aspects on the nature of strategic thinking. Namely, it indicates that it is an art, in the sense that it cannot be reduced to following an algorithm.