Tuesday, May 30, 2006

On Zero Knowledge in Games...

I'm back now from the ESA PC meeting, not to return for at least five more years. ESA has a 'diversity' policy: no one can repeat memberships on a committee within five years (This doesn't apply to PC chairs though). Rumor has it that this is a reaction to a system where new blood wasn't coming into the conference committees at all.

I don't know if institutionalized diversity is necessarily the answer in the long term: maybe it's a good short term measure to get some new blood in. You do need some amount of continuity on committees while trying to encourage fresh participation. SODA/STOC/FOCS appears to do this reasonably well.

While catching up with my blogs (what are they putting in the water in Atlanta, anyway ?), I came across this post from Antimeta. It considers (for example) the situation when reading a letter of reference:
we were trying to figure out whether silences can carry implicatures, or more ordinarily, whether you can say something without words. And of course the answer is yes:

Q: "What do you like about John?"
A: [silence]

The problem is about the communication of meaning, and the interplay with intention. Antimeta goes on to say:
A is expected to make a contribution to the conversation mentioning some positive fact about John. A's silence violates the maxim of quantity (she hasn't said as much as is expected), so Q can infer that some other conversational principle (one requiring politeness) must conflict with anything that A would be in a position to say. Therefore, Q comes to believe that there is nothing (or at least nothing relevant) about John that A likes.

But then I realized that we should think about this (and perhaps the original recommendation letter example) a bit more carefully. It seems that the story given above could work in at least two different ways. In one case, A is struggling for an answer, and the silence just comes about because she can't think of anything she likes about John. In the second case, A knows there is nothing she likes about John and remains actively silent. I think the second case is an example of an implicature carried by a silence, but the first is not.

The explanation of the distinction comes from Grice's earlier classic paper, "Meaning" in which he suggests that speaker A means y by utterance x iff "A intended the utterance of x to produce some effect [y] in an audience by means of recognition of this intention." He comes to this recursive intention account of meaning by way of a bunch of examples, which I think parallel the situation here. If I don't intend you to believe (or consider) something by means of my action, then I didn't mean it, even if it's true. Thus, my silence can reveal my dislike for John, just as an accidentally dropped photograph can reveal where I was the other day, but neither means it. But even just performing the action intentionally isn't enough - Grice suggests that showing someone a photograph doesn't constitute a meaning of what is depicted, because my intention plays only an unnecessary role in the observer's coming to believe the truth of what is depicted.

All I can say is: Phew ! Pursuing a Ph.D program in logic and philosophy is no joke.

Seriously though, the post also talks about a paper by Edward Epsen that attempts to apply zero knowledge ideas to game theory. Specifically, the author considers a two-player setting where one player either does (is "informed") or doesn't (is "uninformed") know whether the game being played is one of k choices. The second player has a prior belief with probability q that player 1 is informed. It turns out that there's a zero knowledge protocol to drive q to 1. That is, there is a protocol that will convince player 2 that player 1 is informed about the choice of game being played without knowing which game it is.

I'm simplifying: these are games of incomplete information, where players may not even know the payoffs from their actions. According to the author, these were first used by Aumann and others to handle Cold War conflicts (one example given is: "suppose the US convinced the Soviet Union to reduce its ballistic missile stockpile by 100. What percentage of the Soviet stockpile is this?". Obviously it would be hard to determine the answer to the second question, and thus hard to determine the payoff of the first action.



  1. Thanks for the link to Epsen's paper! Chazelle's essay a while back explicitly pointed to zero-knowledge as a concept ripe for incorporation into the game theory of international relations. Looks like we have a winner...(wonder if Chazelle knew of the results?) 

    Posted by David Molnar

  2. sounds good. this leads to lots of questions in ones mind (?). there are games to be played. you do write well.

    Posted by thinking abt it

  3. Ellen: basically my thought is that there should be general community pressure to include new people, without an explicit mandate: SODA does this, and since David Johnson maintains a list of people who've never served, there is an explicit way of getting your name on a list of candidates, which both sends a message about the importance of this, as well as makes it easier to find new people.

    David: That is very interesting. I didn't notice the reference. Are you referring to Chazelle's ipod essay ?  

    Posted by Suresh


Disqus for The Geomblog