# Local Connection Game

A local connection game is given by a set of vertices and graph G where connection is built by adding edges.

If the cost to user a(user at node a) is given by $$C(u)=\alpha n_u + \beta \sum_v(dist(u,v))^2$$

where $n_u$ is the number of edges incident to u that u purchases and $dist(u,v)$ is the shortest distance from u to v. $\alpha$,$\beta$$\ge$$0$

What is the relationship between $\alpha$ and $\beta$ such that

i)the optimum solution is a star

ii)the optimum solution is a complete graph.

iii)the Nash solution is a star

iv)Determine the price of stability in this model.

I have gone through the theory and the game where the cost is given by $C(u)=\alpha n_u +\sum_v dist(u,v)$ ,but this question is pretty confusing. I'd appreciate if anyone could throw some light on this question.Thanks.

• is this homework? – Per Alexandersson Dec 9 '16 at 13:49
• @PerAlexandersson: No. It isn't homework. It was given as an exercise to better understand the local connection game. – Sylar Persie Dec 9 '16 at 18:50
• Given by who? Is this research related? – Per Alexandersson Dec 9 '16 at 19:16