Self-organizing Networks of Information Gathering Cognitive Agents

Ahmed M. Alaa, Kartik Ahuja, Mihaela van der Schaar

Abstract

In many scenarios, networks emerge endogenously as cognitive agents establish links in order to exchange information. Network formation has been widely studied in economics, but only on the basis of simplistic models that assume that the value of each additional piece of information is constant. In this paper we present a first model and associated analysis for network formation under the much more realistic assumption that the value of each additional piece of information depends on the type of that piece of information and on the information already possessed: information may be complementary or redundant. We model the formation of a network as a non-cooperative game in which the actions are the formation of links and the benefit of forming a link is the value of the information exchanged minus the cost of forming the link. We characterize the topologies of the networks emerging at a Nash equilibrium (NE) of this game and compare the efficiency of equilibrium networks with the efficiency of centrally designed networks. To quantify the impact of information redundancy and linking cost on social information loss, we provide estimates for the Price of Anarchy (PoA); to quantify the impact on individual information loss we introduce and provide estimates for a measure we call Maximum Information Loss (MIL). Finally, we consider the setting in which agents are not endowed with information, but must produce it. We show that the validity of the well-known "law of the few" depends on how information aggregates; in particular, the "law of the few" fails when information displays complementarities.

Introduction

Traditional economic models of network formation often rely on the simplifying assumption that information has a fixed, additive value. However, in modern socio-technological contexts—such as Device-to-Device (D2D) communications, vehicular networks, and the Internet of Things (IoT)—information is context-dependent. Redundancy occurs when multiple sources provide the same data, while complementarity arises when combined data yields more value than the sum of individual parts. This paper addresses how self-interested agents decide to form costly links when the utility of information is governed by these complex relationships.

Theoretical Framework

The authors propose a Cognitive Information Network (CIN) model using a combination of non-cooperative game theory and information theory. Agents are modeled as players whose utility is the difference between the benefit of acquired information and the cost of maintaining links.

To quantify information, the framework employs Shannon Entropy ($H$) and Mutual Information ($I$). The state of information across the network is represented by an "entropic vector." The analysis focuses on identifying Nash Equilibria (NE), where no agent can unilaterally improve their utility by altering their links or information production. Efficiency is evaluated using the Price of Anarchy (PoA) for social welfare and a new metric, Maximum Information Loss (MIL), for individual deficits.

Equilibrium Topologies and the 'Law of the Few'

A central finding of the research is the identification of specific network topologies that emerge at equilibrium. The study reveals that strict Nash Equilibria often result in "star" topologies, where a central high-entropy agent is supported by multiple peripheral agents.

Network topologies emerging under different cost conditions.

Crucially, the paper challenges the "law of the few"—the notion that a small number of hubs provide the majority of a network's value. The authors prove that this law only holds when information is highly redundant. If agents produce independent, complementary information, the law fails, and a decentralized state emerges where most agents must act as information producers to maintain network utility.

Connectivity Regions and Efficiency

The research identifies three distinct cost-based regions that dictate network structure: the Connected region (low cost, leading to a single large component), the Isolated region (high cost, resulting in no links), and the Mixed region (intermediate costs allowing for varied topologies).

Phase diagram of connectivity regions based on link cost and information divergence.

In terms of efficiency, the Price of Anarchy is found to be 1 (indicating perfect efficiency) in both the connected and isolated regions for networks with uniform linking costs. Inefficiency primarily arises in the Mixed region. Furthermore, the study shows that redundancy can actually increase the PoA in networks with heterogeneous costs, as selfish agents may form inefficiently expensive links for redundant data.

Conclusion

This work provides a rigorous foundation for understanding endogenous network formation among cognitive agents. By accounting for information redundancy and complementarity, it offers a more realistic model than classical economic approaches. Future research directions include relaxing the assumption of complete information—where agents must discover what others know—and extending the model to dynamic settings or networks with physical capacity constraints.

Summary updated

Abstract

In many scenarios, networks emerge endogenously as cognitive agents establish links in order to exchange information. Network formation has been widely studied in economics, but only on the basis of simplistic models that assume that the value of each additional piece of information is constant. In this paper we present a first model and associated analysis for network formation under the much more realistic assumption that the value of each additional piece of information depends on the type of that piece of information and on the information already possessed: information may be complementary or redundant. We model the formation of a network as a non-cooperative game in which the actions are the formation of links and the benefit of forming a link is the value of the information exchanged minus the cost of forming the link. We characterize the topologies of the networks emerging at a Nash equilibrium (NE) of this game and compare the efficiency of equilibrium networks with the efficiency of centrally designed networks. To quantify the impact of information redundancy and linking cost on social information loss, we provide estimates for the Price of Anarchy (PoA); to quantify the impact on individual information loss we introduce and provide estimates for a measure we call Maximum Information Loss (MIL). Finally, we consider the setting in which agents are not endowed with information, but must produce it. We show that the validity of the well-known "law of the few" depends on how information aggregates; in particular, the "law of the few" fails when information displays complementarities.
BibTeX
@article{alaa2015self,
  author = {Ahmed M. Alaa and Kartik Ahuja and Mihaela van der Schaar},
  title = {{Self-organizing Networks of Information Gathering Cognitive Agents}},
  journal = {IEEE Trans. Cogn. Commun. Netw.},
  year = {2015},
  url = {https://openreview.net/forum?id=77zdRdLV2n_},
}
Figure