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.
Strategic network formation was first studied in the economics literature. Some of this literature @cite_25 - @cite_5 asks which networks are stable (according to some criteria) and hence more likely to persist and be observed. A (smaller) literature asks which networks emerge as the result of some specific dynamic process @cite_21 @cite_0 . In all these works, simplistic benefit functions are used: the value of each additional good" exchanged is constant @cite_25 - @cite_14 . However, in realistic settings, information possessed by different agents can be redundant or complementary. For instance, secondary users in a multi-band cognitive radio system may be interested in gathering information about spectrum occupancy for bands that they do not sense by communicating with other users who do sense these bands @cite_11 ; sensors deployed over a correlated random field @cite_23 - @cite_17 may be interested in gathering complementary measurements about some set of physical processes of interest; and mobile users who exchange offloaded traffic of SNSs and context-aware applications are only interested in gathering non-redundant traffic and data updates.
@cite_14 @cite_21 @cite_17 @cite_0 @cite_23 @cite_5 @cite_25 @cite_11
2098012117 2221218932 2103720435 2084436032
In Cognitive Radio Networks (CRN), there are multiple primary and secondary users in a region, and primaries can lease out their unused bandwidth to secondaries in exchange for a fee. This gives rise to price competition among the primaries, wherein each primary tries to attract secondaries by setting a lower price for its bandwidth than the other primaries. Radio spectrum has the distinctive feature that transmissions at neighboring locations on the same channel interfere with each other, whereas the same channel can be used at far-off locations without mutual interference. So in the above price competition scenario in a CRN, each primary must jointly select a set of mutually non-interfering locations within the region (which corresponds to an independent set in the conflict graph representing the region) at which to offer bandwidth and the price at each location. In this paper, we analyze this price competition scenario as a game and seek a Nash Equilibrium (NE). We identify a class of conflict graphs, which we refer to as mean valid graphs, such that the conflict graphs of a large number of topologies that commonly arise in practice are mean valid. We explicitly compute a symmetric NE in mean valid graphs and show that it is unique. Strategic network formation arises in settings where agents receive some benefit from their connectedness to other agents, but also incur costs for forming these links. We consider a new network formation game that incorporates an adversarial attack, as well as immunization or protection against the attack. An agent's network benefit is the expected size of her connected component post-attack, and agents may also choose to immunize themselves from attack at some additional cost. Our framework can be viewed as a stylized model of settings where reachability rather than centrality is the primary interest as in many technological networks such as the Internet, and vertices may be vulnerable to attacks such as viruses, but may also reduce risk via potentially costly measures such as an anti-virus software. Our main theoretical contributions include a strong bound on the edge density at equilibrium. In particular, we show that under a very mild assumption on the adversary's attack model, every equilibrium network contains at most only @math 2n-4 edges for @math ni¾?4, where n denotes the number of agents and this upper bound is tight. We also show that social welfare does not significantly erode: every non-trivial equilibrium with respect to several adversarial attack models asymptotically has social welfare at least as that of any equilibrium in the original attack-free model. We complement our sharp theoretical results by a behavioral experiment on our game with over 100 participants, where despite the complexity of the game, the resulting network was surprisingly close to equilibrium. 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. In a cognitive radio network, the secondary users are allowed to utilize the frequency bands of primary users when these bands are not currently being used. To support this spectrum reuse functionality, the secondary users are required to sense the radio frequency environment, and once the primary users are found to be active, the secondary users are required to vacate the channel within a certain amount of time. Therefore, spectrum sensing is of significant importance in cognitive radio networks. There are two parameters associated with spectrum sensing: probability of detection and probability of false alarm. The higher the probability of detection, the better the primary users are protected. However, from the secondary users' perspective, the lower the probability of false alarm, the more chances the channel can be reused when it is available, thus the higher the achievable throughput for the secondary network. In this paper, we study the problem of designing the sensing duration to maximize the achievable throughput for the secondary network under the constraint that the primary users are sufficiently protected. We formulate the sensing-throughput tradeoff problem mathematically, and use energy detection sensing scheme to prove that the formulated problem indeed has one optimal sensing time which yields the highest throughput for the secondary network. Cooperative sensing using multiple mini-slots or multiple secondary users are also studied using the methodology proposed in this paper. Computer simulations have shown that for a 6 MHz channel, when the frame duration is 100 ms, and the signal-to-noise ratio of primary user at the secondary receiver is -20 dB, the optimal sensing time achieving the highest throughput while maintaining 90 detection probability is 14.2 ms. This optimal sensing time decreases when distributed spectrum sensing is applied.