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.

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.