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

Abstract:


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