Communication as Coordination

Madhu Sudan (Microsoft Research & MIT)

The classical theory of communication sets aside the meaning of messages and
focusses on delivery when the channel is unreliable. Semantic communication
attempts to focus on the challenges in getting the meaning across.
Misunderstanding in this setting emerges not from unreliability of the
channel, but rather the uncertainty of the communicating parties about each
other. Overcoming misunderstanding however requires the communication to have
a goal for each communicating player, and furthermore the fact that these
goals are compatible. Defining goals and compatibility in general is a dauting
task, so in this talk we focus on a simple, game-theoretic, setting to
illustrate the problems and solutions.

We consider two players Alice and Bob who are playing a repeated
coordination game - i.e., in each round both players have a binary
choice (for simplicity 0/1). Bob's goal is to coordinate with Alice
- so he wins in a particular if he can predict Alice's choice and make
the same. Alice's payoff's are not known to Bob - all he knows is that
for any fixed action of her's, her payoff does not decrease if he coordinates
with her. At the end of each round players know what each other played.
Thus the actions in the game effectively lead to communication, while also
providing the goals. Alice and Bob don't know each other's strategy, but only
that they come from some well-known set. (So Bob knows Alice's strategy
belongs to some set O_A, and Alice knows that Bob knows this. And vice
versa, Alice knows that Bob's strategy is from some set O_B and Bob knows
that Alice knows this.) Bob's ultimate goal is to coordinate with Alice
for ever, after a finite number of mistakes: If this is possible, Bob has
learned from Alice's communications what her strategy is, and has learned to
emulate this. What are the sets O_A and O_B for which this is possible?
In particular, can we have O_A = O_B (so both players may be trying learn
each other's strategy so that they can play it)? We show in this talk that
while such learning is not possible deterministically, it is possible to
overcome this impossibility result by allowing randomized strategies.


Based on joint work with Jacob Leshno (MSR/Columbia)