On a Bounded Budget Network Creation Game

Details On a Bounded Budget Network Creation Game On a Bounded Budget Network Creation Game

2011-11-02

arxiv.org/abs/1111.0554v1

Computer Science

Computer Science and Game Theory

26 pages, 3 figures, preliminary version appeared in SPAA'11

Scientific paper

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. 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.

Affiliated with

Also associated with

No associations

Rating

On a Bounded Budget Network Creation Game does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On a Bounded Budget Network Creation Game, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a Bounded Budget Network Creation Game will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-329569