Algorithm Design 14
Chapter 10 Local Search
10.2 Game Theory & Local Search
Shapley Network Design Game
Description
Given a directed graph \(G(V,E)\), each edge \(e\in E\) having cost \(c_e\)
\(k\) players, each having source and target \((s_i,t_i)\). For simplicity, let \(s_i=s\).
Player \(i\) wants to go from \(s_i\) to \(t_i\).
Set strategy for player \(i\): \(\{\text{paths }s_i\to t_i\}\)
Strategy profile: \(P=\{P_1,\cdots,P_k\}\), where \(P_i\) denotes a path \(s_i\to t_i\)
Cost of player \(i\): \[ C_i(P)=\sum_{e\in P_i}\frac{c_e}{|\{j\in [k]:e\in P_j\}|} \]
Each player is selfish, and wants to minimize its own cost
Nash Equilibrium (NE)
Def: We say a strategy profile \(P=(P_1,\cdots,P_k)\) is a Nash Equilibrium, if \(\forall i\), \(\forall P_i'\) \[ C_i(P_1,\cdots,P_{i-1},P_i,P_{i+1},\cdots,P_n)\le C_i(P_1,\cdots,P_{i-1},P_i',P_{i+1},P_n) \] Similar to "local minimum", any single player wants to change its strategy.
But some players can collaborate to make their costs decrease.
Social Optimal
Def: Minimum Steiner Tree connecting \(s,t_1,\cdots,t_k\)
Steiner Tree: Given a set \(S\subseteq V\), find a connected graph \((V',E')\) that \(S\subseteq V'\subseteq V\), and minimize the sum of cost of all edges in \(E'\).
Pollard Conjecture: \(\frac{\texttt{M Steriner T}}{\texttt{M Spanning T}}\ge \frac{\sqrt 3}{2}\)
THM: There is a game where the social cost of the unique NE is \(\Theta(\log k)\) times the social optimum.
Remark: this THM indicates that NE can be extremely bad.
Example:
\(V=s\cup T\cup\{t_1,\cdots,t_k\}\)
\(E=\{(s,t_i,\frac{1}{i}):i\in [k]\}\cup\{(T,t_i,0):i\in [k]\}\cup(s,T,1+\epsilon)\)
Social Optimal: All players use \(s\to T\to t_i\), with \(C_i=\frac{1+\epsilon}{k}\). Total Cost = \(1+\epsilon\).
NE: the above state is not NE, finally NE would be player \(i\) use \(s\to t_i\), with \(C_i=\frac{1}{i}\). Total Cost = \(H_k\).
NE Properties
Existence: NE can be achieved by best response dynamics (BRP).
If BRP terminates (no cycle), it must be a NE.
Price of Anarchy(无政府主义): \(PoA=\frac{Cost(\texttt{worst NE})}{cost(\texttt{Social Optimal})}\)
Price of Stability: \(PoS=\frac{Cost(\texttt{best NE})}{cost(\texttt{Social Optimal})}\)
THM: \(PoS\le \mathcal O(\log k)\)
Proof: [potential function method]
Let \(H(k)=\sum_{i=1}^k \frac{1}{i}\), and \(X_e=|\{i\in [k]:e\in P_i\}|\) \[ \Phi(P):=\sum_{e\in E}c_e H(X_e) \]
Key Lemma: Suppose player \(i\) wants to update from \(P_i\) to \(P_i'\), then \[ C_i(P_i,P\backslash P_i)-C_i(P_i',P\backslash P_i)=\Phi(P_i,P\backslash P_i)-\Phi(P_i',P\backslash P_i) \] Proof: \[ \begin{aligned} &\quad C_i(P_i,P\backslash P_i)-C_i(P_i',P\backslash P_i)\\ &=\sum_{e\in P_i}\frac{c_e}{X_e}-\sum_{e\in P_i'}\frac{c_e}{X_e'}\\ &=\sum_{e\in P_i\backslash P_i'}\frac{c_e}{X_e}-\sum_{e\in P_i'\backslash P_i}\frac{c_e}{X_e+1}\\ &=\left(\sum_{e\in P_i\backslash P_i'}c_eH(X_e)-\sum_{e\in P_i\backslash P_i'}c_eH(X_e-1)\right)-\left(\sum_{e\in P_i'\backslash P_i}c_eH(X_e+1)-\sum_{e\in P_i'\backslash P_i}c_eH(X_e)\right)\\ &=\left(\sum_{e\in P_i\backslash P_i'}c_eH(X_e)-\sum_{e\in P_i\backslash P_i'}c_eH(X_e')\right)-\left(\sum_{e\in P_i'\backslash P_i}c_eH(X_e')-\sum_{e\in P_i'\backslash P_i}c_eH(X_e)\right)\\ &=\left(\sum_{e\in P_i\backslash P_i'}c_eH(X_e)+\sum_{e\in P_i'\backslash P_i}c_eH(X_e)\right)-\left(\sum_{e\in P_i'\backslash P_i}c_eH(X_e')+\sum_{e\in P_i\backslash P_i'}c_eH(X_e')\right)\\ &=\Phi(P_i,P\backslash P_i)-\Phi(P_i',P\backslash P_i) \end{aligned} \] \(\square\)
Consider BRD, \(\Phi\) decreases monotonically, and BRD is finite, so BRD will terminate and lead to NE.
Let \(P^*\) denote the social optimal potential, so, \[ H_k\cdot C(P^*)\ge \Phi(P^*)>\Phi(P_{NE})\ge C(P_{NE}) \]
Undirected graph case
Worst case Example not holds.
Current best lower bound: \(PoA\ge1.8\)
Current best upper bound:
- \(PoS\le \mathcal O(\log\log n)\) for broadcast game (each vertex has \(t_i\), and \(s_i=s\)) [Fiat et.al.]
- \(PoS\le \mathcal O(\log\log\log n)\) for broadcast game [Lee, Ligett]
- \(PoS\le \mathcal O(1)\) for broadcast game [Bilo et.al. 20]
- \(PoS\le \mathcal O(\frac{\log n}{\log \log n})\) for multicast game
Chapter 11 Linear Programming
11.1 Totally Unimodular Matrix
Definitions
- [ Totally Unimodular Matrix,TUM ] Matrix \(A\) is TUM if the determinant of every square submatrix belongs to \(\{0,\pm 1\}\)
- [ Integral Polytope/Polyhedron ] A polytope \(P\) is integral if every vertex of \(P\) is an integral vector
Prop: If \(A\) is TUM, for every invertible square submatrix \(U\) (i.e. \(\det(U)=\pm 1\)) , \(U^{-1}\) is integral (every entry in \(U^{-1}\) is integral)
Proof: \(U_{ij}^{-1}=\frac{\det(U^*_{ji})}{\det(U)}=\frac{0,\pm 1}{\pm 1}\)
THM [ Hoffman, Kruscal ]: \(A\) is TUM \(\iff\) For any integral vector \(\vec b\), \(P=\{\vec x:A\vec x\le \vec b\}\) is integral
Proof: \(\Rightarrow\)
A vertex is the solution of a linear system \(A'\vec x=\vec b'\) ( \(A'\) consists of a subset of rows \(I\) of \(A\) and full rank, \(\vec b'=\vec b_I\) ).
Therefore, \(A'\) is invertible, and \(\vec x=A'^{-1}\vec b'\). By Prop, \(A'^{-1}\) is integral, so \(\vec x\) is integral.
THM [ Judging TUM ]: \(A\in \mathbb R^{m\times n}\) is TUM \(\iff\) \(\forall R\subseteq [m]\), \(\exists R=R_1+R_2\), s.t. \(\forall j\in[n]\), \(\sum\limits_{i\in R_1}a_{i,j}-\sum\limits_{i\in R_2}a_{i,j}\in \{0,\pm 1\}\).
Proof: OMITTED
Example 1: Bipartite Matching
Maximize \(\sum_{e} x_e\) , s.t. \(\forall v,\sum_{v\in e}x_e\le 1\), \(\forall e, x_e\ge 0\).
\(A\in \mathbb R^{(|V|+|E|)\times |E|}\), \(A_{v,e}=\mathbf 1(v\in e)\), \(A_{|V|+e_i,e_j}=\mathbf 1(i=j)\)
Example 2: Consecutive "1" Matrix
\(A\in \mathbb R^{m\times n}\), \(\forall i\in [m]\), \(\exist 1\le l_i\le r_i\le n\), \(A_{i,j}=\mathbf 1(j\in [l_i,r_i])\)
Remark: Interval Scheduling
Example 3: Network Matrix
Given a directed tree \(T(V,E)\), \(|E|=m\), and a set of ordered pairs of vertices \(P\subseteq V\times V\), \(|P|=k\).
Network Matrix: \(M\in \mathbb R^{m\times k}\) , if \(e=(u,v)\), \(\bar e:=(v,u)\) \[ M_{e,(v_1,v_2)}=\begin{cases}1&e\in Path(v_1,v_2)\\ -1&\bar e\in Path(v_1,v_2)\\ 0&e,\bar e\notin Path(v_1,v_2)\end{cases} \] THM [ Tutte ]: A network matrix is TUM
Remark:
Reverse result almost correct, only \(2\) classes of matrices are TUM but not network matrix
TUM=Network Matrix+ (2 classes of matrices & their operation)
Remark: TDI, Matroid \(\sim\) TUM