Abstract: We consider a network creation game in which each player (vertex) has a fixed budget to establish links to other players. In our model, each link has unit price and each agent tries to minimize its cost, which is either its local diameter or its total distance to other players in the (undirected) underlying graph of the created network. Two versions of the game are studied: in the MAX version, the cost incurred to a vertex is the maximum distance between the vertex and other vertices, and in the SUM version, the cost incurred to a vertex is the sum of distances between the vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard. We take the social cost of the created network to be its diameter, and next we study the maximum possible diameter of an equilibrium graph with n vertices in various cases. When the sum of players' budgets is n-1, the equilibrium graphs are always trees, and we prove that their maximum diameter is Theta(n) and Theta(log n) in MAX and SUM versions, respectively. When each vertex has unit budget (i.e. can establish link to just one vertex), the diameter of any equilibrium graph in either version is Theta(1). We give examples of equilibrium graphs in the MAX version, such that all vertices have positive budgets and yet the diameter is Omega(sqrt(log n)). This interesting (and perhaps counter-intuitive) result shows that increasing the budgets may increase the diameter of equilibrium graphs and hence deteriorate the network structure. Then we prove that every equilibrium graph in the SUM version has diameter 2^O(sqrt(log n)). Finally, we show that if the budget of each player is at least k, then every equilibrium graph in the SUM version is k-connected or has diameter smaller than 4.
Recommendations
- Basic network creation games
- The price of anarchy in network creation games is (mostly) constant
- The Price of Anarchy in Network Creation Games Is (Mostly) Constant
- The max-distance network creation game on general host graphs
- Bounded budget connection (BBC) games or how to make friends and influence people, on a budget
Cited in
(23)- On network formation games with heterogeneous players and basic network creation games
- On the tree conjecture for the network creation game
- Geometric spanner games
- On the structure of equilibria in basic network formation
- On selfish creation of robust networks
- On network formation games with heterogeneous players and basic network creation games
- Basic network creation games
- Correction: ``Basic network creation games
- Network creation games: think global -- act local
- Celebrity games
- On the tree conjecture for the network creation game
- Efficient equilibrium concepts in non-cooperative network formation
- Bounded Budget Betweenness Centrality Game for Strategic Network Formations
- Inequality and network formation games
- Distance-uniform graphs with large diameter
- Bounded budget connection (BBC) games or how to make friends and influence people, on a budget
- Bounded budget connection (BBC) games or how to make friends and influence people, on a budget
- On tree equilibria in max-distance network creation games
- On the PoA Conjecture: Trees versus Biconnected Components
- The Impact of Cooperation in Bilateral Network Creation
- Bounded budget betweenness centrality game for strategic network formations
- Fair tree connection games with topology-dependent edge cost
- Facility location and restoration games
This page was built for publication: A bounded budget network creation game
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962196)
