Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient Best-Response Computation for Strategic Network Formation under Attack
91
0
0.0
(
0
)
Added by
Pascal Lenzner
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by investigating a very recently introduced model by Goyal et al. [WINE16] which focuses on robust networks in the presence of a strong adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes and their neighbors. Our main result is to establish that this natural model is one of the few exceptions which are both realistic and computationally tractable. In particular, we answer an open question of Goyal et al. by providing an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure and may thus be of independent interest.
rate research
Read More
Strategic network formation arises where agents receive benefit from connections to other agents, but also incur costs for forming links. We consider a new network formation game that incorporates an adversarial attack, as well as immunization against attack. An agents 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 is a stylized model of settings where reachability rather than centrality is the primary concern and vertices vulnerable to attacks may reduce risk via costly measures. In the reachability benefit model without attack or immunization, the set of equilibria is the empty graph and any tree. The introduction of attack and immunization changes the game dramatically; new equilibrium topologies emerge, some more sparse and some more dense than trees. We show that, under a mild assumption on the adversary, every equilibrium network with $n$ agents contains at most $2n-4$ edges for $ngeq 4$. So despite permitting topologies denser than trees, the amount of overbuilding is limited. We also show that attack and immunization dont significantly erode social welfare: every non-trivial equilibrium with respect to several adversaries has welfare at least as that of any equilibrium in the attack-free model. We complement our theory with simulations demonstrating fast convergence of a new bounded rationality dynamic which generalizes linkstable best response but is considerably more powerful in our game. The simulations further elucidate the wide variety of asymmetric equilibria and demonstrate topological consequences of the dynamics e.g. heavy-tailed degree distributions. Finally, we report on 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.
We study a network formation game where agents receive benefits by forming connections to other agents but also incur both direct and indirect costs from the formed connections. Specifically, once the agents have purchased their connections, an attack starts at a randomly chosen vertex in the network and spreads according to the independent cascade model with a fixed probability, destroying any infected agents. The utility or welfare of an agent in our game is defined to be the expected size of the agents connected component post-attack minus her expenditure in forming connections. Our goal is to understand the properties of the equilibrium networks formed in this game. Our first result concerns the edge density of equilibrium networks. A network connection increases both the likelihood of remaining connected to other agents after an attack as well the likelihood of getting infected by a cascading spread of infection. We show that the latter concern primarily prevails and any equilibrium network in our game contains only $O(nlog n)$ edges where $n$ denotes the number of agents. On the other hand, there are equilibrium networks that contain $Omega(n)$ edges showing that our edge density bound is tight up to a logarithmic factor. Our second result shows that the presence of attack and its spread through a cascade does not significantly lower social welfare as long as the network is not too dense. We show that any non-trivial equilibrium network with $O(n)$ edges has $Theta(n^2)$ social welfare, asymptotically similar to the social welfare guarantee in the game without any attacks.
Recently Cole and Gkatzelis gave the first constant factor approximation algorithm for the problem of allocating indivisible items to agents, under additive valuations, so as to maximize the Nash Social Welfare. We give constant factor algorithms for a substantial generalization of their problem -- to the case of separable, piecewise-linear concave utility functions. We give two such algorithms, the first using market equilibria and the second using the theory of stable polynomials. In AGT, there is a paucity of methods for the design of mechanisms for the allocation of indivisible goods and the result of Cole and Gkatzelis seemed to be taking a major step towards filling this gap. Our result can be seen as another step in this direction.
We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to $n$ agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of agents valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. This led to a flurry of work obtaining constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and $O(n)$-approximation algorithms for more general valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant.
The study of approximate mechanism design for facility location problems has been in the center of research at the intersection of artificial intelligence and economics for the last decades, largely due to its practical importance in various domains, such as social planning and clustering. At a high level, the goal is to design mechanisms to select a set of locations on which to build a set of facilities, aiming to optimize some social objective and ensure desirable properties based on the preferences of strategic agents, who might have incentives to misreport their private information such as their locations. This paper presents a comprehensive survey of the significant progress that has been made since the introduction of the problem, highlighting the different variants and methodologies, as well as the most interesting directions for future research.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
