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.

Categories:

• zero-knowledge