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.
Peer-to-peer (P2P) networks can be easily deployed to distribute user-generated content at a low cost, but the free-rider problem hinders the efficient utilization of P2P networks. Using game theory, we investigate incentive schemes to overcome the free-rider problem in content production and sharing. We build a basic model and obtain two benchmark outcomes: 1) the non-cooperative outcome without any incentive scheme and 2) the cooperative outcome. We then propose and examine three incentive schemes based on pricing, reciprocation, and intervention. We also study a brute-force scheme that enforces full sharing of produced content. We find that 1) cooperative peers share all produced content while non-cooperative peers do not share at all without an incentive scheme; 2) by utilizing the P2P network efficiently, the cooperative outcome achieves higher social welfare than the non-cooperative outcome does; 3) a cooperative outcome can be achieved among non-cooperative peers by introducing an incentive scheme based on pricing, reciprocation, or intervention; and 4) enforced full sharing has ambiguous welfare effects on peers. In addition to describing the solutions of different formulations, we discuss enforcement and informational requirements to implement each solution, aiming to offer a guideline for protocol design for P2P networks. We analyze networks that feature reputational learning: how links are initially formed by agents under incomplete information, how agents learn about their neighbors through these links, and how links may ultimately become broken. We show that the type of information agents have access to, and the speed at which agents learn about each other, can have tremendous repercussions for the network evolution and the overall network social welfare. Specifically, faster learning can often be harmful for networks as a whole if agents are myopic, because agents fail to fully internalize the benefits of experimentation and break off links too quickly. As a result, preventing two agents from linking with each other can be socially beneficial, even if the two agents are initially believed to be of high quality. This is due to the fact that having fewer connections slows the rate of learning about these agents, which can be socially beneficial. Another method of solving the informational problem is to impose costs for breaking links, in order to incentivize agents to experiment more carefully. In this paper, we propose a routing algorithm called minimum fusion Steiner tree (MFST) for energy efficient data gathering with aggregation (fusion) in wireless sensor networks. Different from existing schemes, MFST not only optimizes over the data transmission cost, but also incorporates the cost for data fusion, which can be significant for emerging sensor networks with vectorial data and or security requirements. By employing a randomized algorithm that allows fusion points to be chosen according to the nodes' data amounts, MFST achieves an approximation ratio of 5 4log(k + 1), where k denotes the number of source nodes, to the optimal solution for extremely general system setups, provided that fusion cost and data aggregation are nondecreasing against the total input data. Consequently, in contrast to algorithms that only excel in full or nonaggregation scenarios without considering fusion cost, MFST can thrive in a wide range of applications How do networks form and what is their ultimate topology? Most of the literature that addresses these questions assumes complete information: agents know in advance the value of linking even with agents they have never met and with whom they have had no previous interaction (direct or indirect). This paper addresses the same questions under the much more natural assumption of incomplete information: agents do not know in advance—but must learn—the value of linking. We show that incomplete information has profound implications for the formation process and the ultimate topology. Under complete information, the network topologies that form and are stable typically consist of agents of relatively high value only. Under incomplete information, a much wider collection of network topologies can emerge and be stable. Moreover, even with the same topology, the locations of agents can be very different: An agent can achieve a central position purely as the result of chance rather than as the result of merit. All of this can occur even in settings where agents eventually learn everything so that information, although initially incomplete, eventually becomes complete. The ultimate network topology depends significantly on the formation history, which is natural and true in practice, and incomplete information makes this phenomenon more prevalent. Consider the following network communication setup, originating in a sensor networking application we refer to as the "sensor reachback" problem. We have a directed graph G=(V,E), where V= v sub 0 v sub 1 ...v sub n and E spl sube V spl times V. If (v sub i ,v sub j ) spl isin E, then node i can send messages to node j over a discrete memoryless channel (DMC) (X sub ij ,p sub ij (y|x),Y sub ij ), of capacity C sub ij . The channels are independent. Each node v sub i gets to observe a source of information U sub i (i=0...M), with joint distribution p(U sub 0 U sub 1 ...U sub M ). Our goal is to solve an incast problem in G: nodes exchange messages with their neighbors, and after a finite number of communication rounds, one of the M+1 nodes (v sub 0 by convention) must have received enough information to reproduce the entire field of observations (U sub 0 U sub 1 ...U sub M ), with arbitrarily small probability of error. In this paper, we prove that such perfect reconstruction is possible if and only if H(U sub s | U sub S(c) ) < spl Sigma sub i spl isin S,j spl isin S(c) for all S spl sube 0...M ,S spl ne O,0 spl isin S(c). Our main finding is that in this setup, a general source channel separation theorem holds, and that Shannon information behaves as a classical network flow, identical in nature to the flow of water in pipes. At first glance, it might seem surprising that separation holds in a fairly general network situation like the one we study. A closer look, however, reveals that the reason for this is that our model allows only for independent point-to-point channels between pairs of nodes, and not multiple-access and or broadcast channels, for which separation is well known not to hold. This "information as flow" view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of implementing codes using a layered protocol stack. This paper presents the first study of the endogenous formation of networks by strategic, self-interested agents who benefit from producing and disseminating information. This work departs from previous works on network formation (especially in the economics literature) which assume that agents benefit only by acquiring information produced by other agents. The strategic production and dissemination of information have striking consequences. We show first that the network structure that emerges (in equilibrium) typically displays a core-periphery structure, with the few agents at the core playing the role of eeconnectorsee, creating and maintaining links to the agents at the periphery. We then determine conditions under which the networks that emerge are minimally connected and have short network diameters (properties that are important for efficiency). Finally, we show that the number of agents who produce information and the total amount of information produced in the network grow at the same rate as the agent population; this is in stark contrast to the "law of the few" that had been established in previous works which do not consider information dissemination. Recently, localization has become an indispensable technique for wireless applications. In view of the limitation of global position system (GPS) in certain environments, alternative approaches are in demand. In this paper, we consider a cooperative localization approach named sum-product algorithm over a wireless network (SPAWN). Although SPAWN theoretically facilitates cooperative localization, it has several practical limitations. Specifically, SPAWN results in high computational complexity and increased network traffic. The main complexity of SPAWN lies in the selection of agents anchors involved in the cooperative localization. To this end, we formulate the agent anchor selection problem into a network formation game. Together with a practical limit on the number of agents anchors used for cooperative localization, our proposed approach can markedly reduce the computational complexity and the resultant network traffic. Simulations show that these advantages come with a slight degradation in the localization mean squared error (MSE) performance. Collaborative spectrum sensing among secondary users (SUs) in cognitive networks is shown to yield a significant performance improvement. However, there exists an inherent trade off between the gains in terms of probability of detection of the primary user (PU) and the costs in terms of false alarm probability. In this paper, we study the impact of this trade off on the topology and the dynamics of a network of SUs seeking to reduce the interference on the PU through collaborative sensing. Moreover, while existing literature mainly focused on centralized solutions for collaborative sensing, we propose distributed collaboration strategies through game theory. We model the problem as a non-transferable coalitional game, and propose a distributed algorithm for coalition formation through simple merge and split rules. Through the proposed algorithm, SUs can autonomously collaborate and self-organize into disjoint independent coalitions, while maximizing their detection probability taking into account the cooperation costs (in terms of false alarm). We study the stability of the resulting network structure, and show that a maximum number of SUs per formed coalition exists for the proposed utility model. Simulation results show that the proposed algorithm allows a reduction of up to 86.6 of the average missing probability per SU (probability of missing the detection of the PU) relative to the non-cooperative case, while maintaining a certain false alarm level. In addition, through simulations, we compare the performance of the proposed distributed solution with respect to an optimal centralized solution that minimizes the average missing probability per SU. Finally, the results also show how the proposed algorithm autonomously adapts the network topology to environmental changes such as mobility.