## Efficient Networks in the Symmetric Connections Model¶

• low cost: $c < \delta - \delta^2$
• complete network is uniquely efficient
• that's going to be the situation where it's more beneficial to have a direct relationship. This is the value for direct relationship($\delta$) compared to an indirect relationship of distance 2($\delta^2$). So shortening anything of distance 2 or even further, the gain in changing that is bigger thant he loss in terms of cost of adding a link. So adding a link is always going to be beneficial and the complete network is going to be uniquely efficient in that setting.
• medium cost: $\delta - \delta^2 < c < \delta + (n - 2)\delta^2/2$
• star networks with all agents are uniquely efficient
• So the only architecture which is going to be efficient is going to be have somebody in the center and then everybody else have that one link to that person, and that's going to be the thing that maximizes total sum of utilizes necessity, and the only thing which maximiazes the total sum of utilies.
• high cost: $\delta + (n - 2)\delta^2 / 2 < c$
• empty network is uniquely efficient
• it just makes sense that nobody should connect any links, just too expensive it doesn't make sense to have anybody talking to anybody. So for very high costs the empty network is uniquely efficient

## Proof¶

• $c < \delta - \delta^2$ then $u_i(g+ij) > u_i(g)$ if ij not in g.

Also $u_k(g+ij) \ge u_k(g)$ if ij not in g for every k, thus

$\sum_k u_k(g+ij) \ge \sum_k u_k(g)$

• $c > \delta - \delta^2$ first, show that the value of a component is higtest when the component is a star

• value of a star with k players is

$2(k-1)[\delta - c] + (k - 1)(k - 2)\delta^2$ (expression A)

• one in the middle, k-1 other individuals out, so we got k-1 links in total, each one of those links give a value of $\delta-c$ to each of its participants, there's two people in it, k-1 links, so the direct value of connections is $2(k-1)[\delta-c]$
• then the indirect values that we're getting are coming from the fact that each one of these indirect people, there's k-1 of them, they have k-2 other neighbors, each at 2 distance of 2, so each of these k-1 people have k-2 neighbors, each one of those gives a benefit of delta squared.
• value of a network with k players and m links ($m \ge k-1$, in order to connect these k plays together) is at most

$2m[\delta - c] + [k(k-1) - 2m]\delta^2$ (expression B)

• the most you could be getting indirectly is you've got k players, k-1 other people that they could be connected to, 2m of those connections are direct connections. So the remaining indirect connections is [k(k-1) - 2m]. So this is the maximum possible value we can imagine for some other component with m links
• difference between A and B is

$2(m - (k - 1))[\delta^2 - (\delta - c)] > 0$ if $m > k - 1$

because we're in a region where $c>\delta - \delta^2$, so $\delta^2 > \delta -c$

so the first expression A is more valuable than the second expression

• If m = k-1 and not a star, then some pair is at a distance of more than 2, so less value than a star

• value of a star with k players is

$2(k-1)[\delta - c] + (k - 1)(k - 2)\delta^2$

• value of a component with k players and k-1 links that is not a star is at most

$2(k-1)[\delta-c] + [(k-1)(k-2)-1]\delta^2+ \delta^3$

• Star is better

Check that if two separate star components each g nonnegative utility, then one star with all those pla generates higher utility

• Separate:

$2(k-1)[\delta - c] + (k - 1)(k - 2)\delta^2$ + $2(k'-1)[\delta - c] + (k' - 1)(k' - 2)\delta^2$

= $2(k+k'-2)[\delta-c] + [(k-1)(k-2) + (k'-1)(k'-2)]\delta^2$

• As one star:

$2(k+k'-1)[\delta-c] + (k+k'-1)(k+k'-2)\delta^2$

• second expression is greater...

• So efficient networks are collections of stars or empty networks

• So, either a star with all player or empty

• Want a star if its value is >0, so when

$2(n-1)[\delta-c] + (n-1)(n-2)\delta^2 >0$

$c < \delta + (n - 2)\delta^2/2$