text: 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.
  @cite_37: We study network formation with n players and link cost α > 0. After the network is built, an adversary randomly deletes one link according to a certain probability distribution. Cost for player ν incorporates the expected number of players to which ν will become disconnected. We focus on unilateral link formation and Nash equilibrium . We show existence of Nash equilibria and a price of stability of 1 + ο (1) under moderate assumptions on the adversary and n ≥ 9. We prove bounds on the price of anarchy for two special adversaries: one removes a link chosen uniformly at random, while the other removes a link that causes a maximum number of player pairs to be separated. We show an Ο (1) bound on the price of anarchy for both adversaries, the constant being bounded by 15 + ο (1) and 9 + ο (1), respectively.
  @cite_3: We present an approach to network formation based on the notion that social networks are formed by individual decisions that trade off the costs of forming and maintaining links against the potential rewards from doing so. We suppose that a link with another agent allows access, in part and in due course, to the benefits available to the latter via his own links. Thus individual links generate externalities whose value depends on the level of decay delay associated with indirect links. A distinctive aspect of our approach is that the costs of link formation are incurred only by the person who initiates the link. This allows us to formulate the network formation process as a noncooperative game.
  @cite_19: 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.
  @cite_45: Current peer-to-peer (P2P) systems often suffer from a large fraction of freeriders not contributing any resources to the network. Various mechanisms have been designed to overcome this problem. However, the selfish behavior of peers has aspects which go beyond resource sharing. This paper studies the effects on the topology of a P2P network if peers selfishly select the peers to connect to. In our model, a peer exploits locality properties in order to minimize the latency (or response times) of its lookup operations. At the same time, the peer aims at not having to maintain links to too many other peers in the system. By giving tight bounds on the price of anarchy, we show that the resulting topologies can be much worse than if peers collaborated. Moreover, the network may never stabilize, even in the absence of churn. Finally, we establish the complexity of Nash equilibria in our game theoretic model of P2P networks. Specifically, we prove that it is NP-hard to decide whether our game has a Nash equilibrium and can stabilize.
  @cite_15: We study topology control problems in ad hoc networks where network nodes get to choose their power levels in order to ensure desired connectivity properties. Unlike most other work on this topic, we assume that the network nodes are owned by different entities, whose only goal is to maximize their own utility that they get out of the network without considering the overall performance of the network. Game theory is the appropriate tool to study such selfish nodes: we define several topology control games in which the nodes need to choose power levels in order to connect to other nodes in the network to reach their communication partners while at the same time minimizing their costs. We study Nash equilibria and show that-among the games we define-these can only be guaranteed to exist if each network node is required to be connected to all other nodes (we call this the STRONG CONNECTIVITY GAME). For a variation called CONNECTIVITY GAME, where each node is only required to be connected (possibly via intermediate nodes) to a given set of nodes, we show that Nash equilibria do not necessarily exist. We further study how to find Nash equilibria with incentive-compatible algorithms and compare the cost of Nash equilibria to the cost of a social optimum, which is a radius assignment that minimizes the total cost in a network where nodes cooperate. We also study variations of the games; one where nodes not only have to be connected, but k-connected, and one that we call the REACHABILITY GAME, where nodes have to reach as many other nodes as possible, while keeping costs low. We extend our study of the STRONG CONNECTIVITY GAME and the CONNECTIVITY GAME to wireless networks with directional antennas and wireline networks, where nodes need to choose neighbors to which they will pay a link. Our work is a first step towards game-theoretic analyses of topology control in wireless and wireline networks.
  @cite_12: Connections in networks are organized to fulfil a function, and a common one is targeted transport or navigation. Here the authors use game theory to show how networks designed to maximize navigation efficiency at minimal cost share basic structural properties, which are also found in real cases.
summary: 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.