1st International Conference on Game Theory for Networks

Research Article

Reliable relaying with uncertain knowledge

  • @INPROCEEDINGS{10.1109/GAMENETS.2009.5137387,
        author={Jiwoong Lee and Jean Walrand},
        title={Reliable relaying with uncertain knowledge},
        proceedings={1st International Conference on Game Theory for Networks},
        keywords={Relay network Reliable relaying Bounded Knowledge Inconsistent Beliefs Common Knowledge},
  • Jiwoong Lee
    Jean Walrand
    Year: 2009
    Reliable relaying with uncertain knowledge
    DOI: 10.1109/GAMENETS.2009.5137387
Jiwoong Lee1,*, Jean Walrand1,*
  • 1: Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, California
*Contact email: porce@eecs.berkeley.edu, wlr@eecs.berkeley.edu


The motivation for this paper is to analyze the effect of information uncertainty on the design and performance of protocols. The paper considers two types of situations. The first is when different nodes in the network have bounded knowledge about what other nodes know. The second, called common knowledge about inconsistent beliefs, is when the information is inconsistent but everyone knows it. Situations of bounded or inconsistent information arise naturally in networks because the state of these systems changes and nodes take time to learn of those changes. The specific problem that the paper explores is the relaying of packets in a simple butterfly network. Despite its apparent simplicity, this problem enables to illustrate key features of situations of uncertain knowledge that arise in networks. The paper presents two impossibility facts and one possibility fact, in the latter of which a scheme that enables optimal coordination given persisting imperfection in knowledge is introduced.