Time+Place: | Tuesday 15/12/2015 14:30 Room 337-8 Taub Bld. |

Title: | When Can Limited Randomness Be Used in Repeated Games? |

Speaker: | Moni Naor - COLLOQUIUM LECTURE http://www.wisdom.weizmann.ac.il/~naor/ |

Affiliation: | Weizmann Institute of Science |

Host: | Nir Ailon |

A Nash equilibrium is a collection of players' strategies such that no player can improve her utility by a unilateral deviation. 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, 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 sequentially. In this talk we explore how much randomness is necessary for equilibria to exist in finitely repeated games with computationally bounded and unbounded players. No knowledge of Game Theory will be assumed. Joint work with Pavel Hubacek and Jonathan Ullman. Short Bio: Moni Naor is an Israeli computer scientist, currently a professor at the Weizmann Institute of Science. Naor received his Ph.D. in 1989 at the University of California, Berkeley. His advisor was Manuel Blum. He works in various fields of computer science, mainly the foundations of cryptography. He is notable for initiating research on public key systems secure against chosen ciphertext attack and creating non-malleable cryptography, visual cryptography (with Adi Shamir), and suggesting various methods for verifying that users of a computer system are human (leading to the notion of CAPTCHA). His research on Small-bias sample space, give a general framework for combining small k-wise independent spaces with small $\epsilon$-biased spaces to obtain $\delta$-almost k-wise independent spaces of small size. In 1994 he was the first, with Amos Fiat, to formally study the problem of practical broadcast encryption. Along with Benny Chor, Amos Fiat, and Benny Pinkas, he made a contribution to the development of Traitor tracing, a copyright infringement detection system which works by tracing the source of leaked files rather than by direct copy protection. He was named an IACR fellow in 2008 and received the Goedel Prize 2014 Desserts will be served from 14:15 Lecture starts at 14:30