Network Formation Games And The Potential Function Method

Step 1: Count distances. Let the graph have $m \ge n-1$ edges (it must be connected). Exactly $2m$ ordered pairs are at distance 1. The other $n(n-1) - 2m$ ordered pairs are at distance $\ge 2$.

Step 2: Lower-bound the cost. $$SC \ge \alpha m + 2\big(n(n-1) - 2m\big) + 2m = (\alpha - 2)m + 2n(n-1).$$

Step 3: Both extremes are tight. A star and a clique have diameter $\le 2$, so they meet this bound exactly. The bound is linear in $m$: minimize $m$ (star, $m = n-1$) when $\alpha > 2$, and maximize it (clique) when $\alpha < 2$.

∎

Star, $\alpha \ge 1$. Let the center buy all $n-1$ edges. The center can’t drop any, since that disconnects the graph. A leaf can only add edges: $k$ new edges cost $\alpha k$ and save only $k$ in distance (each target goes from distance 2 to 1). That is not profitable.

Clique, $\alpha \le 1$. Assign each edge to one endpoint. Dropping $k$ edges saves $\alpha k$ but adds $k$ to distance (each target goes from 1 to 2). That is not profitable.

∎

For $\alpha\le 1$ or $\alpha \ge 2$, Lemmas 19.1–19.2 give an optimal network that is stable. For $1<\alpha<2$, the star is stable and the clique is optimal. By Step 2 of Lemma 19.1, their costs are $(\alpha-2)(n-1) + 2n(n-1)$ and $(\alpha-2)\frac{n(n-1)}{2} + 2n(n-1)$. The ratio is largest as $\alpha \downarrow 1$:

∎

Step 1: Lower-bound OPT. Any connected graph costs at least $(n-1)\alpha$, and there are $\Theta(n^2)$ distances of at least 1. So $\mathrm{OPT} = \Omega(\alpha n + n^2)$.

Step 2: Distance cost. At most $n^2 d$, which is $\le d\cdot$OPT.

Step 3: Cut edges (removal disconnects $G$). There are at most $n-1$ of them, costing $\le \alpha(n-1) \le$ OPT.

Step 4: Noncut edges bought by $u$. For each such $e = (u,v)$, let $V_e$ be the nodes whose shortest path from $u$ uses $e$. If deleting $e$ leaves $\mathrm{dist}(u,v) \le 2d$ (Step 5), each $w \in V_e$ gets at most $2d$ farther. Stability (dropping $e$ saves $\alpha$) forces $\alpha \le 2d|V_e|$, i.e. $|V_e| \ge \alpha/2d$. The sets $V_e$ are disjoint, so $u$ buys at most $2dn/\alpha$ noncut edges, costing $O(dn)$. Over all nodes this is $O(dn^2)$.

Step 5: Deleting $e$ leaves $u$ within $2d$ of $v$. Take a shortest $u$–$v$ path avoiding $e$, and let $e' = (u',v')$ be where it enters $V_e$ (Fig. 19.1).

• $u' \notin V_e$, so the shortest $u$–$u'$ path $P_u$ doesn’t use $e$ and has length $\le d$.
• $v' \in V_e$, so $e$ followed by $P_v$ (from $v$ to $v'$) is a shortest $u$–$v'$ path. Hence $|P_v| \le d-1$.

The detour $P_u, e', P_v$ has length $\le 2d$.

Total: $SC(G) = O(\alpha n + d n^2) = O(d)\cdot$OPT.

∎

Step 1: Suppose a long path. Let $\mathrm{dist}(u,v) \ge 2k$.

Step 2: Value of buying the edge $(u,v)$. The nodes on the far half of the path, at positions $k+1,\dots,2k$ from $u$, get closer by $1, 3, \dots, 2k-1$, a total saving of $k^2$.

The key step: if $k^2 > \alpha$, buying $(u,v)$ is a profitable deviation. So stable graphs have diameter below about $2\sqrt\alpha$. Lemma 19.4 finishes the proof.

∎

Let $\mathrm{dist}(u,v) = d$, $d' = (d-1)/4$, and let $B$ be the ball of radius $d'$ around $u$.

Step 1: $v$ wouldn’t buy an edge to $u$. For $w\in B$, $\mathrm{dist}(v,w) \ge d - d'$ before, and $\le d'+1$ after adding $(v,u)$. The saving per node is $\ge d - 2d' - 1 = (d-1)/2$. Stability gives $$\frac{(d-1)|B|}{2} \le \alpha.$$

Step 2: $u$ wouldn’t buy an edge to the boundary of $B$. For $w \in B$, let $A_w$ be the nodes $t$ whose shortest $u$–$t$ path leaves $B$ right after $w$. Then $w$ is at distance exactly $d'$. Buying $(u,w)$ saves $d'-1$ for each $t \in A_w$, so $|A_w|(d'-1) \le \alpha$.

Step 3: Some boundary node carries many. The $n - |B|$ nodes outside $B$ are split among at most $|B|$ sets $A_w$, so some $|A_w| \ge (n-|B|)/|B|$. Hence $(d'-1)(n-|B|)/|B| \le \alpha$, i.e. $|B|(1 + \alpha/(d'-1)) \ge n$. Using $\alpha > d > d'$, this gives $$|B| \ge \frac{n(d'-1)}{2\alpha}.$$

Step 4: Combine.

so $d' - 1 \le \alpha/\sqrt n$ and $d \le 4\alpha/\sqrt n + O(1)$. Lemma 19.4 finishes the proof.

∎

Step 1: Edges in both or neither path. $i$’s share and $\Phi_e$ are unchanged.

Step 2: Edges in $P_i \setminus P'_i$. $i$ stops paying $c_e/k_e$, and $\Phi_e$ drops from $c_eH_{k_e}$ to $c_eH_{k_e - 1}$, also a drop of $c_e/k_e$.

Step 3: Edges in $P'_i \setminus P_i$. $i$ starts paying $c_e/(k_e+1)$, and $\Phi_e$ rises by exactly $c_e/(k_e+1)$.

Summing over edges gives the claim.

∎

Let $S$ minimize $\Phi$. Any unilateral move to $S'$ has $\Phi(S') \ge \Phi(S)$, so the mover’s utility changes by $\Phi(S) - \Phi(S') \le 0$. No one gains.

∎

Let $S^N$ minimize $\Phi$, which is an equilibrium by Theorem 19.11, and let $S^*$ be optimal.

• (a) Lower half of the hypothesis.
• (b) $S^N$ minimizes $\Phi$.
• (c) Upper half of the hypothesis.

∎

Step 1: In PLS. The neighbours of a profile are the single-player deviations. Local minima of $\Phi$ are exactly the pure equilibria.

Step 2: The source problem. Weighted satisfiability (Krentel): clauses $C_j$ with weights $w_j$, cost = total weight of unsatisfied clauses, neighbours = flip one variable. It is PLS-complete.

Step 3: Build a congestion game. There is one player per variable $x_i$ and one resource per clause. Player $i$ has two strategies:

• $S_i$ = the clauses containing literal $x_i$, meaning ”$x_i$ is false”;
• $\bar S_i$ = the clauses containing $\bar x_i$, meaning ”$x_i$ is true”.

So the load on clause $j$ equals its number of false literals.

Step 4: Costs. With $k_j$ literals in clause $j$, set $c_j(\xi) = 0$ for $\xi < k_j$ and $c_j(k_j) = w_j$. A clause is false iff its load is $k_j$.

The key step: the Rosenthal potential is $\sum_j c_j(\xi_j) =$ the weight of unsatisfied clauses. So equilibria are exactly the local optima of the MAX-SAT instance.

∎

Step 1: Order the players. Player 1’s source is closest to $t$. Player 2 is closest to $\{t, s_1\}$, and so on.

Step 2: Lowest index pays all. Charge the full $c_e$ to the lowest-indexed user of $e$.

Step 3: Induct. Player 1 pays for its whole path regardless, so it takes a shortest $s_1$–$t$ path. Player 2 pays only for edges player 1 doesn’t use, so it connects by a cheapest path to the existing tree, and so on.

The key step: equilibrium play reproduces Prim’s MST heuristic for Steiner tree, which is a 2-approximation.

∎

Step 1: Dropping out costs society exactly $i$‘s profit. If provider $i$ leaves, each of its clients $j$ switches to its second-best option, costing $p_{ij}$ instead of $c_{js_i}$. The welfare loss per client is $p_{ij} - c_{js_i}$, exactly $i$‘s profit from $j$.

Step 2: Any move is leave-then-re-enter. The change in $V$ equals the difference in $i$‘s profit between the two locations.

∎

Let $S$ be an equilibrium, $O = \{o_1,\dots,o_k\}$ optimal, and $O^i = \{o_1,\dots,o_i\}$.

• (a) Monotonicity.
• (b) Submodularity: $S - s_i \subseteq S \cup O^{i-1}$, so adding $o_i$ is worth at least as much to the smaller set.
• (c) Property (3) at the profile where $i$ plays $o_i$.
• (d) $S$ is an equilibrium, so switching to $o_i$ doesn’t help $i$.
• (e) Property (2).

So $V(O) \le 2V(S)$.

∎

Step 1: Improvement per step. Let $\beta_i$ be the best possible gain in player $i$‘s payoff. In a basic game, $i$‘s payoff change equals the welfare change. So the expected welfare gain per step is $\frac1n\sum_i \beta_i$.

Step 2: Lower-bound $\beta_i$. Switching to $o_i$ is available, and the game is basic, so

Step 3: Rerun the PoA chain. As in Theorem 19.19,

So $\sum_i\beta_i \ge V(O) - 2V(S)$.

The key step: writing $D = V(O) - 2V(S)$, each step raises $V$ by at least $D/n$ in expectation. So $D$ shrinks by a factor of about $(1 - 2/n)$ per step: by $e$ after $n/2$ steps, and to an $\epsilon$ fraction after $O(n\log\epsilon^{-1})$ steps.

∎