The Weizmann Institute of Science Faculty of Mathematics and Computer Science Foundations of Computer Science Seminar Lecture Hall, Room 1, Ziskind Building on Sunday, June 19, 2011 at 11:00 Note unusual day/time/location Bernhard von Stengel London School of Economics will speak on Nash Codes for Noisy Channels Abstract: We consider a coordination game between a sender and a receiver who communicate over a noisy channel. The sender wants to inform the receiver about the state by transmitting a message over the channel. Both receive positive payoff only if the receiver decodes the received signal as the correct state. The sender uses a known ``codebook" to map states to messages. When does this codebook define a Nash equilibrium? The receiver's best response is to decode the received signal as the most likely message that has been sent. Given this decoding, an equilibrium or ``Nash code" results if the sender encodes every state as prescribed by the codebook, which is not always the case. We show two theorems that give sufficient conditions for Nash codes. First, the ``best" codebook for the receiver (which gives maximum expected receiver payoff) defines a Nash code. A second, more surprising observation holds for communication over a binary channel which is used independently a number of times, a basic model of information theory: Given a consistent tie-breaking decoding rule which holds generically, ANY codebook of binary codewords defines a Nash code. This holds irrespective of the quality of the code and also for nonsymmetric errors of the binary channel. (Joint work with P. Hernandez) --------------------------------------------------------- Technion Math Net-2 (TECHMATH2) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Diana Mandelik <diana.mandelik@weizmann.ac.il>