  We study a coordination game motivated by the formation of Internet Exchange
Points (IXPs), in which agents choose which facilities to join. Joining the
same facility as other agents you communicate with has benefits, but different
facilities have different costs for each agent. Thus, the players wish to join
the same facilities as their "friends", but this is balanced by them not
wanting to pay the cost of joining a facility. We first show that the Price of
Stability ($PoS$) of this game is at most 2, and more generally there always
exists an $\alpha$-approximate equilibrium with cost at most $\frac{2}{\alpha}$
of optimum. We then focus on how better stable solutions can be formed. If we
allow agents to pay their neighbors to prevent them from deviating (i.e., a
player $i$ voluntarily pays another player $j$ so that $j$ joins the same
facility), then we provide a payment scheme which stabilizes the solution with
minimum social cost $s^*$, i.e. PoS is 1. In our main technical result, we
consider how much a central coordinator would have to pay the players in order
to form good stable solutions. Let $\Delta$ denote the total amount of payments
needed to be paid to the players in order to stabilize $s^*$, i.e., these are
payments that a player would lose if they changed their strategy from the one
in $s^*$. We prove that there is a tradeoff between $\Delta$ and the Price of
Stability: $\frac{\Delta}{cost(s^*)} \le 1 - \frac{2}{5} PoS$. Thus when there
are no good stable solutions, only a small amount of extra payment is needed to
stabilize $s^*$; and when good stable solutions already exist (i.e., $PoS$ is
small), then we should be happy with those solutions instead. Finally, we
consider the computational complexity of finding the optimum solution $s^*$,
and design a polynomial time $O(\log n)$ approximation algorithm for this
problem.
