Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCharacterizing Strategic Cascades on Networks
152
0
0.0
(
0
)
Added by
Travis Martin
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Transmission of disease, spread of information and rumors, adoption of new products, and many other network phenomena can be fruitfully modeled as cascading processes, where actions chosen by nodes influence the subsequent behavior of neighbors in the network graph. Current literature on cascades tends to assume nodes choose myopically based on the state of choices already taken by other nodes. We examine the possibility of strategic choice, where agents representing nodes anticipate the choices of others who have not yet decided, and take into account their own influence on such choices. Our study employs the framework of Chierichetti et al. [2012], who (under assumption of myopic node behavior) investigate the scheduling of node decisions to promote cascades of product adoptions preferred by the scheduler. We show that when nodes behave strategically, outcomes can be extremely different. We exhibit cases where in the strategic setting 100% of agents adopt, but in the myopic setting only an arbitrarily small epsilon % do. Conversely, we present cases where in the strategic setting 0% of agents adopt, but in the myopic setting (100-epsilon)% do, for any constant epsilon > 0. Additionally, we prove some properties of cascade processes with strategic agents, both in general and for particular classes of graphs.
rate research
Read More
A digital security breach, by which confidential information is leaked, does not only affect the agent whose system is infiltrated, but is also detrimental to other agents socially connected to the infiltrated system. Although it has been argued that these externalities create incentives to under-invest in security, this presumption is challenged by the possibility of strategic adversaries that attack the least protected agents. In this paper we study a new model of security games in which agents share tokens of sensitive information in a network of contacts. The agents have the opportunity to invest in security to protect against an attack that can be either strategically or randomly targeted. We show that, in the presence of random attack, under-investments always prevail at the Nash equilibrium in comparison with the social optimum. Instead, when the attack is strategic, either under-investments or over-investments are possible, depending on the network topology and on the characteristics of the process of the spreading of information. Actually, agents invest more in security than socially optimal when dependencies among agents are low (which can happen because the information network is sparsely connected or because the probability that information tokens are shared is small). These over-investments pass on to under-investments when information sharing is more likely (and therefore, when the risk brought by the attack is higher).
We analyze a network formation game in a strategic setting where payoffs of individuals depend only on their immediate neighbourhood. We call these payoffs as localized payoffs. In this game, the payoff of each individual captures (1) the gain from immediate neighbors, (2) the bridging benefits, and (3) the cost to form links. This implies that the payoff of each individual can be computed using only its single-hop neighbourhood information. Based on this simple model of network formation, our study explores the structure of networks that form, satisfying one or both of the properties, namely, pairwise stability and efficiency. We analytically prove the pairwise stability of several interesting network structures, notably, the complete bi-partite network, complete equi-k-partite network, complete network and cycle network, under various configurations of the model. We validate and extend these results through extensive simulations. We characterize topologies of efficient networks by drawing upon classical results from extremal graph theory and discover that the Turan graph (or the complete equi-bi-partite network) is the unique efficient network under many configurations of parameters. We examine the tradeoffs between topologies of pairwise stable networks and efficient networks using the notion of price of stability, which is the ratio of the sum of payoffs of the players in an optimal pairwise stable network to that of an efficient network. Interestingly, we find that price of stability is equal to 1 for almost all configurations of parameters in the proposed model; and for the rest of the configurations of the parameters, we obtain a lower bound of 0.5 on the price of stability. This leads to another key insight of this paper: under mild conditions, efficient networks will form when strategic individuals choose to add or delete links based on only localized payoffs.
In social networks, information and influence diffuse among users as cascades. While the importance of studying cascades has been recognized in various applications, it is difficult to observe the complete structure of cascades in practice. Moreover, much less is known on how to infer cascades based on partial observations. In this paper we study the cascade inference problem following the independent cascade model, and provide a full treatment from complexity to algorithms: (a) We propose the idea of consistent trees as the inferred structures for cascades; these trees connect source nodes and observed nodes with paths satisfying the constraints from the observed temporal information. (b) We introduce metrics to measure the likelihood of consistent trees as inferred cascades, as well as several optimization problems for finding them. (c) We show that the decision problems for consistent trees are in general NP-complete, and that the optimization problems are hard to approximate. (d) We provide approximation algorithms with performance guarantees on the quality of the inferred cascades, as well as heuristics. We experimentally verify the efficiency and effectiveness of our inference algorithms, using real and synthetic data.
Many real-world networks such as social networks consist of strategic agents. The topology of these networks often plays a crucial role in determining the ease and speed with which certain information driven tasks can be accomplished. Consequently, growing a stable network having a certain desired topology is of interest. Motivated by this, we study the following important problem: given a certain desired topology, under what conditions would best response link alteration strategies adopted by strategic agents, uniquely lead to formation of a stable network having the given topology. This problem is the inverse of the classical network formation problem where we are concerned with determining stable topologies, given the conditions on the network parameters. We study this interesting inverse problem by proposing (1) a recursive model of network formation and (2) a utility model that captures key determinants of network formation. Building upon these models, we explore relevant topologies such as star graph, complete graph, bipartite Turan graph, and multiple stars with interconnected centers. We derive a set of sufficient conditions under which these topologies uniquely emerge, study their social welfare properties, and investigate the effects of deviating from the derived conditions.
We address the issue of the effects of considering a network of contacts on the emergence of cooperation on social dilemmas under myopic best response dynamics. We begin by summarizing the main features observed under less intellectually demanding dynamics, pointing out their most relevant general characteristics. Subsequently we focus on the new framework of best response. By means of an extensive numerical simulation program we show that, contrary to the rest of dynamics considered so far, best response is largely unaffected by the underlying network, which implies that, in most cases, no promotion of cooperation is found with this dynamics. We do find, however, nontrivial results differing from the well-mixed population in the case of coordination games on lattices, which we explain in terms of the formation of spatial clusters and the conditions for their advancement, subsequently discussing their relevance to other networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
