“On Consensus through Communication with a Commonly Known Protocol,” E. Tsakas & M. Voorneveld (2010)

(Site note: I will be down in Cuba until Dec. 24, so posting will be light until then, though I do have a few new papers to discuss. I’m going to meet with some folks there about the recent economic reforms and their effects, so perhaps I’ll have something interesting to pass along on that front.)

A couple weeks ago, I posted about the nice result of Parikh and Krasucki (1990), who show that when communication is pairwise, beliefs can fail to converge under many types of pre-specified orders of communication. In their paper, and in every paper following it that I know of, common knowledge of the order of communication is always assumed. For instance, if Amanda talks with Bob and then Bob talks with Carol, since only common knowledge of the original information partitions is assumed, for Carol to update “properly” she needs to know whether has Bob has talked to Amanda previously.

In a paper pointed out by a commenter, Tsakas and Voorneveld point out through counterexample just how strict this requirement is. They expand the state space to include knowledge of the order of communication (using knowledge in the standard Aumann way). It turns out that with all of the necessary conditions of Parikh and Krasucki holding, and uncertainty about whether a single act of communication occurred, consensus can fail to be reached. What’s worrying here from a modeling perspective is that it is really convenient to model communication as a directed graph, where A links to B if A talks to B infinite times. I see the Tsakas and Voorneveld result as giving some pause to that assumption. In particular, in the example, all agents have common knowledge of the communications graph, since the only uncertainty is in one period and therefore no uncertainty about the structure of the graph.

There is no positive result here: we don’t have useful conditions guaranteeing belief convergence under uncertainty about the protocol. In the paper I’m working on, I restrict all results to “regular” communication, meaning the only communication is through formal channels that occur infinite times, and because of this I only need to assume knowledge of the graph.

http://edocs.ub.unimaas.nl/loader/file.asp?id=1490 (Working Paper. Tsakas and Voorneveld also have a 2007 paper on this topic that corrects some erroneous earlier work: https://gupea.ub.gu.se/dspace/bitstream/2077/4576/1/gunwpe0255.pdf. In particular, even if consensus is reached, information only becomes common knowledge among under really restrictive assumptions. This is important if, for instance, you are studying mechanisms on a network, since many results in game theory require common knowledge about what opponents will do: see Dekel and Brandenburger (1987) and Aumann and Brandenburger (1995), for instance. I’ll have more to say about this about this once I get a few more results proved.)

%d bloggers like this: