Communication Networks: How is Information Transmitted?
What specific properties must a network have to allow optimal communication between agents and a decision maker? Tristan Tomala and Ludovic Renou combine theories from economics and computer science to identify the mechanisms that allow information to be transmitted to the decision maker without being distorted or falsified.
Theories of mechanism design are based on the revelation principle, which demonstrates that it is possible to build a process wherein each person is invited to clearly articulate his or her preference to the decision maker in a given situation. The decision maker can then collect this information and ultimately make a decision. But, as Tomala notes, “while this principle is appealing in theory, it assumes that each actor has the opportunity to communicate directly with the decision maker. In practice, in a company for example, not all employees can communicate directly with the CEO in a face-to-face conversation in his or her office. Direct and secure communication is very rare; even an email is not a direct interaction—the information goes through a server first!” It is thus difficult for the decision maker to be sure that information is reliable.
SOCIAL CHOICE FUNCTIONS
Tomala explains that while the decision maker’s final choice depends on information collected from individuals, this information generally differs depend- ing on how people are consulted. According to the theory of social choice, these rules (or social choice functions) act as an incentive when it is in agents’ interest to reveal their true preference. Thus, if sev- eral colleagues decide to buy a coffee machine for their open space, asking each person to pay a fee each time they use the machine is a better incen tive than dividing the price of the machine among the people who have said that they want to use it. In the latter case, everyone is better off saying that they don’t plan to make any coffee! If the decision maker has to make decisions based on the infor- mation collected, he or she will thus seek to adopt social choice functions that provide agents with an incentive to reveal their true preferences.
DEFINING THE RIGHT RULES OF THE GAME
What are the necessary conditions for a commu- nication network to enable the implementation of such incentive-providing functions? Based on infor- mation system theory, Tomala and Renou devel- oped a visual representation of the communication network where each agent is a node with links to other agents. If there is a path of links (or “edges”) between two nodes, then the network is said to be connected. A 1-connected network has at least one path of links between a given pair of agents, a 2- connected network has two such paths, and so on. Tomala and Renou look at directed networks, wherein the communication links run in a specific direction. The network is said to be strongly connected if it is possible to go from one node to another by following the direction of the links (information circulates in several directions, going up toward the decision maker or trickling down to other agents). The network is weakly connected if it is possible to move between any two nodes while disregarding the direction of the links. The researchers show that for any situation and regardless of the environment, an economically efficient communication network—that is, one that can be used to implement social choice functions that create appropriate incentives—must fulfill two conditions (illustrated in the diagram):
• Being strongly 1-connected. The network is configured so that there is a path of links from each node to the decision maker. Each person is linked, directly or indirectly, to the decision maker.
• Being weakly 2-connected. The network is constructed so that each agent is either directly connected to the decision maker or is indirectly connected via at least two different paths. There are no cases of an isolated person who interacts with only one other person (other than the decision maker) nor are there any cases where one person stands between a whole group and the rest of the network. Thus, the hierarchical pyramid is not an optimal communication network. An agent’s superior (n+1) controls all information, and if his or her interests or preferences differ from those of the agent, the n+1 will tend to distort the information transmit- ted to his or her own superior (n+2), even though the interests of the agent and the n+1 may be similar. In contrast, with a weakly 2-connected net- work, agents dispose of two means to transmit information. They can either transmit part of the information to their n+1 and the rest to the decision maker through a different channel, or trans- mit the same information through two different channels. The decision maker can then make use of both paths and compare the different versions. Tomala sums it up as follows: “If a network is weakly 2-connected, there’s always a way to sort things out.”
Based on an interview with Tristan Tomala and the article “Mechanism Design and Communication Networks” (co-authored with Ludovic Renou), presented at the International Conference on Game Theory for Networks of the Institute for Computer Sci- ences, Social Informatics and Telecommunications Engineering (ICST).
This demonstration of the mechanism for obtaining optimal communication constitutes a significant contribution to computing techniques in cryptography. By analyzing directed connected networks, Tomala and Renou show how a 2-connected network can protect the security of messages and networks. For example, in a 2-connected network, the agent can code a message, send it through one channel and transmit the key to decode it through another, so that only the decision maker is able to read the message, without any intervention from third parties or hackers. This work opens the way for further research, notably on the situation of an “active designer.” In this scenario, the decision maker collects information from all the agents and then delegates the decision to the agents rather than making it him or herself.
The work of Tomala and Renou is based both on the theory of mechanism design (particularly the work of Myerson and Maskin), the theory of communication networks (more specifically the work of Dolev, Franklin, and Wright), network theory in general, and information system theory, which is traditionally reserved for modeling work in computer science.