Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by [PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design.
Also related are network formation games where not centrality but some other property is the goal of each agent. There are games where agents simply want to be connected to all other agents, e.g. @cite_3 @cite_37 @cite_19 . Among them, the work by @cite_15 is closely related to our work. In their wireline strong connectivity game agents are points in the Euclidian plane who strategically buy incident edges to create a connected network. The edge price equals the length of the edge. This is similar to our model in the Euclidian plane with @math but the focus on connectivity changes the game completely. Another related geometric game was proposed by @cite_45 . Also there the agents are points in some metric space but agents pay a fixed price for each edge and try to minimize the total stretch towards all other agents. Guly 'a @cite_12 considered a network formation game in the hyperbolic plane where agents strive for maximum navigability. This is also a geometric model but drastically different from our approach.
@cite_37 @cite_3 @cite_19 @cite_45 @cite_15 @cite_12
2221218932 2007583146 2143039680 1974040162
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. We study network design games where @math self-interested agents have to form a network by purchasing links from a given set of edges. We consider Shapley cost sharing mechanisms that split the cost of an edge in a fair manner among the agents using the edge. It is well known that the price of anarchy of these games is as high as @math . Another line of research has focused on evaluating the price of stability, i.e., the cost of the best Nash equilibrium relative to the social optimum. In this paper we investigate to which extent coordination among agents can improve the quality of solutions. We resort to the concept of strong Nash equilibria, which were introduced by Aumann and are resilient to deviations by coalitions of agents. We analyze the price of anarchy of strong Nash equilibria and develop lower and upper bounds for unweighted and weighted games in both directed and undirected graphs. These bounds are tight or nearly tight for many scenarios. It shows that, by using coordination, the price of anarchy drops from linear to logarithmic bounds. We complement these results by also proving the first superconstant lower bound on the price of stability of standard equilibria (without coordination) in undirected graphs. More specifically, we show a lower bound of @math for weighted games, where @math is the total weight of all the agents. This almost matches the known upper bound of @math . Our results imply that, for most settings, the worst-case performance ratios of strong coordinated equilibria are essentially always as good as the performance ratios of the best equilibria achievable without coordination. These settings include unweighted games in directed graphs as well as weighted games in both directed and undirected graphs. We consider computational aspects of a game theoretic approach to network reliability. Consider a network where failure of one node may disrupt communication between two other nodes. We model this network as a simple coalitional game, called the vertex Connectivity Game (CG). In this game, each agent owns a vertex, and controls all the edges going to and from that vertex. A coalition of agents wins if it fully connects a certain subset of vertices in the graph, called the primary vertices. We show that power indices, which express an agent's ability to affect the outcome of the vertex connectivity game, can be used to identify significant possible points of failure in the communication network, and can thus be used to increase network reliability. We show that in general graphs, calculating the Banzhaf power index is #P-complete, but suggest a polynomial algorithm for calculating this index in trees. We also show a polynomial algorithm for computing the core of a CG, which allows a stable division of payments to coalition agents. In this paper, we study a basic network design game in which n self-interested agents, each having individual connectivity requirements, wish to build a network by purchasing links from a given set of edges. A fundamental cost-sharing mechanism is Shapley cost-sharing, which splits the cost of an edge in a fair manner among the agents using the edge. It is well known that in such games, the price of anarchy is n, while the price of stability is H(n), where H(n) denotes the nth harmonic number. We investigate whether an optimal minimum-cost network represents an attractive, relatively stable state that agents might want to purchase: what extra cost does an agent incur compared to a possible strategy deviation? We employ the concept of α-approximate Nash equilibria, in which no agent can reduce its cost by a factor of more than α. We prove that for single-source games in undirected graphs, every optimal network represents an H(n)-approximate Nash equilibrium. We show that this bound is tight by presenting a...