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>