Cut games

Graph G=(V,E)G=(V,E) with weight wew_e on each edge eEe\in E.

Every node corresponds to a player.

Two strategies per player/node vv:

  • To put vv at the left or right side of the cut

Cut(S)Cut(S): the set of edges with their endpoints on different sides of the cut at a state SS

payoffi(S)=eCut(S)Niwe\text{payoff}_i(S)=\sum_{e\in Cut(S)\cap N_i}w_e

A pure Nash equilibrium was found.

带权图的最大割 Maximum cut

Cut games are potential games

Lemma: the function

Φ(S)=eCut(S)we\Phi(S)=\sum_{e\in Cut(S)}w_e

is a potential function for a cut game.

Proof

Consider two states SS and SS' that differ in the strategy of player ii i.e., S=(Si,si)S'=(S_{-i},s_i')

we will show that Φ(S)Φ(S)=payoffi(S)payoffi(S)\Phi(S)-\Phi(S')=\text{payoff}_i(S)-\text{payoff}_i(S')

Φ(S)Φ(S)=eCut(S)weeCut(S)we=eCut(S)Niwe+eCut(S)NiweeCut(S)NiweeCut(S)Niwe\Phi(S)-\Phi(S')=\sum_{e\in Cut(S)}w_e-\sum_{e\in Cut(S')}w_e\\ =\sum_{e\in Cut(S)\cap N_i}w_e+\sum_{e\in Cut(S)\diagdown N_i}w_e-\sum_{e\in Cut(S')\cap N_i}w_e-\sum_{e\in Cut(S')\diagdown N_i}w_e\\

Observe that the edges which belong to the cut but are not incident to node ii are the same in states SS and SS', since they are not affected by the change of strategy for player ii. (与 ii 不相邻的点在其改变策略前后对势函数的贡献不变) Hence, we have:

=eCut(S)Niwe+eCut(S)NiweeCut(S)NiweeCut(S)Niwe=payoffi(S)payoffi(S)=\sum_{e\in Cut(S)\cap N_i}w_e+\cancel{\sum_{e\in Cut(S)\diagdown N_i}w_e}-\sum_{e\in Cut(S')\cap N_i}w_e-\cancel{\sum_{e\in Cut(S')\diagdown N_i}w_e}\\ \\=\text{payoff}_i(S)-\text{payoff}_i(S')

Price of anarchy/stability

Review: price of stability (defined in social cost) 如果用社会福利定义,分子分母反过来。

PoS=value of best Nash equilibriumvalue of optimal solution,PoS0PoS=\frac{\text{value of best Nash equilibrium}}{\text{value of optimal solution}},PoS\ge0

The potential function mainly gives us information about the structure of the game. To assess the quality of states, we use the notion of the social welfare, defined as the total payoff of all players in state SS, i.e. Social welfare: total payoff of all players in state SS,

SW(S)=ipayoffi(S)SW(S)=\sum_i\text{payoff}_i(S)

Observation: SW(S)=2Φ(S)SW(S)=2\Phi(S).

Proof:

(简单来讲,就是因为一条割边被记了两次 because two player share a cut edge while Φ(S)\Phi(S) only count cut edge once.)

By definition of the social welfare, we have

SW(S)=ipayoffi(S)=ieCUT(S)NiweSW(S)=\sum_i\text{payoff}_i(S)=\sum_i\sum_{e\in CUT(S)\cap N_i}w_e

Now, observe that every edge in the cut contributes to the payoff the two players controlling its end points. Thus, we have:

SW(S)=eCUT(S)2we=2Φ(S)SW(S)=\sum_{e\in CUT(S)}2w_e=2\Phi(S)

Hence the price of stability is equal to 1. (Why?)

Proof:

By Lemma proved above, notice that the state of maximum social welfare maximizes the value of the potential function and is, thus, an equilibrium. The theorem follows by the definition of the price of stability.

Theorem: The price of anarchy is at most 2

Proof

Similar to the proof that a simple local search algorithm for solving the MAX-CUT problem has good performance. MAX-CUT is formally defined as follows: Given a graph GG with non-negative weights on the edges, find a partition of the nodes in two set so that the total weight of edges with their endpoints is different sets of the partition is maximized.

Let SeqS_{eq} be a pure Nash equilibrium and uu a node that is at the left of the cut in state SeqS_{eq}. Since SeqS_{eq} is an equilibrium, the player controlling node uu has no incentive to deviate from her strategy.

This means that the total weight of edges in the cut which are incident to uu is at least half the total weight of all edges which are incident to uu. Thus, for every player at the left of the cut, we have:

payoffu(Seq)=eCUT(Seq)Nuwe12eNuwe\text{payoff}_u(S_{eq})=\sum_{e\in CUT(S_{eq})\cap N_u}w_e\ge\frac{1}{2}\sum_{e\in N_u}w_e

Using similar reasoning, we can verify an analogous for the nodes at right of the cut. Summing over all players and using the definition of social welfare, we have

SW(Seq)=uVpayoffu(Seq)12uVeNuwe=eEweSW(S_{eq})=\sum_{u\in V}\text{payoff}_u(S_{eq})\ge\frac{1}{2}\sum_{u\in V}\sum_{e\in N_u}w_e=\sum_{e\in E}w_e

The last equality follows since when we sum over all nodes, we count each edge e=(u,v)e=(u,v) twice since ee belongs to both sets NuN_u and NvN_v. Now, it suffices to observe that 2×eEwe2\times\sum_{e\in E}w_e is a upper bound on the social welfare of any state, including the state SS^* of maximum social welfare. Indeed(一个点的 payoff 最多只能被所有与之相连的边贡献,SW(S)SW(S^*) 不能超过所有点连出去的所有边权之和):

SW(S)=uVpayoffu(S)uVeNuwe=2×eEweSW(S^*)=\sum_{u\in V}\text{payoff}_u(S^*)\le\sum_{u\in V}\sum_{e\in N_u}w_e=2\times\sum_{e\in E}w_e

Thus, we have SW(Seq)12SW(S)SW(S_{eq})\ge\frac{1}{2}SW(S^*) Q. E. D.

Theorem: There exists cut games with PoA exactly 2

example:

a-1-b-1-c-1-d-1-a

ab cd: SW=4

ac bd: SW=8

Network design games

Graph G=(V,E)G=(V,E)

Cost wew_e for edge eEe\in E

  • indicates the cost of establishing the corresponding link in the network

nn player

  • player ii want to connect a source σi\sigma_i to a destination node τi\tau_i.
  • strategies: the different paths that connect node σi\sigma_i with node τi\tau_i.

Cost of player ii at a state SS where the strategy sis_i is used for player ii

costi(S)=esiwefe(S)\text{cost}_i(S)=\sum_{e\in s_i}\frac{w_e}{f_e(S)}

fe(S)f_e(S): 在 SS 状态下,使用 ee 边的玩家总数

Social cost = total cost of all players at a state

SC(S)=icosti(S)=iesiwefe(S)=eEiNi,esiwefe(S)=eEwefe(S)iNi,esi1=eEwe=sum of weights of edges used by at least one player.SC(S)=\sum_i\text{cost}_i(S)\\ =\sum_i\sum_{e\in s_i}\frac{w_e}{f_e(S)}\\ =\sum_{e\in E}\sum_{i\in N_i,e\in s_i}\frac{w_e}{f_e(S)}\\ =\sum_{e\in E}\frac{w_e}{f_e(S)}\sum_{i\in N_i,e\in s_i}1\\ =\sum_{e\in E}w_e\\=\text{sum of weights of edges used by at least one player.}

Alternatively, the total cost of the edges used by at least one player.

Theorem: There exists a network with PoA arbitrarily close to nn

PoA=maxSPNESC(S)SC(S)PoS=minSPNESC(S)SC(S)S:state of minimum social cost1PoSPoAPoA=\max_{S\in PNE}\frac{SC(S)}{SC(S^*)}\\ PoS=\min_{S\in PNE}\frac{SC(S)}{SC(S^*)}\\ S^*:\text{state of minimum social cost}\\ 1\le PoS\le PoA

考虑一种均衡,当有 nn 个玩家,全部都使用下面的路径,每个玩家的损失都是 11, 此时没有玩家有 incentive to 使用上面那条 1+ϵ1+\epsilon 的路径。所以

PoA=1×n1+ϵn×n=n1+ϵnPoA=\frac{1\times n}{\frac{1+\epsilon}{n}\times n}=\frac{n}{1+\epsilon}\rightarrow n

Price of stability

Theorem: there exists a network design game with PoS arbitrarily close to Hn=i=1n1iH_n=\sum_{i=1}^n\frac{1}{i}.

Proof:

SC(S)=1+ϵSC(S)=i=1n1i=HnSC(S^*)=1+\epsilon\\ SC(S)=\sum_{i=1}^n\frac{1}{i}=H_n

Proof via Rosenthal’s potential function

先证明:所有的玩家使用 1i\frac{1}{i} 一步到位的路径确实是纯纳什均衡的。

  • 当所有玩家使用上面那条路径时候,没有 player has incentive to deviate to 1+ϵ1+\epsilon path since 1+ϵ>1i(i=1,)1+\epsilon\gt\frac{1}{i}(\forall i=1,\cdots).

再证明:这个所有玩家使用一步到位的路径的纯纳什均衡是唯一的。只要有人选择 1+ϵ1+\epsilon 的路径,那么就不是纳什均衡的。

  • SS': 假设有的人走 1i1\over i 一步到位的路径,有的人走 00,再走 1+ϵ1+\epsilon 的路径。We will show that SS' is not Pure Nash Equilibrium for every ϵ>0\epsilon\gt0.

  • Consider there are ll players using 1+ϵ1+\epsilon path. Among the players who use the direct edge to τ\tau let ii^* be the player of minimum index.

  • It must be that il+1i^*\le l+1. If ili^*\le l, cost is at least 1l1\over l By deviating the cost would be 1+ϵl+1<1l\frac{1+\epsilon}{l+1}\lt\frac{1}{l}.

  • When i=l+1i^*=l+1 i.e., 1,,l1,\cdots,l-th players using 1+ϵ1+\epsilon edge. The remaining players use direct edge.

    Player ll has cost 1+ϵl\frac{1+\epsilon}{l}. By deviating to the direct yields smaller cost 1l1\over l.

    Therefore SS^* is not PNE.

SC(Seq)Hn×SC(S)PoS=minSPNESC(S)SC(S)SC(Seq)SC(S)HnSC(S_{eq})\le H_n\times SC(S^*)\\ \Rarr PoS=\min_{S\in PNE}\frac{SC(S)}{SC(S^*)}\le\frac{SC(S_{eq})}{SC(S^*)}\le H_n

Rosenthal’s potential is a potential function for network design game

Φ(S)=eEi=1fe(S)wei=eE;fe(S)>0weHfe(S)eE;fe(S)>0weHnSC(S)=eE;fe(S)>0weeE;fe(S)>0weHfe(S)=Φ(S)SC(Seq)Φ(Seq)Φ(S)HnSC(S)\Phi(S)=\sum_{e\in E}\sum_{i=1}^{f_e(S)}\frac{w_e}{i}=\sum_{e\in E;f_e(S)\gt0}w_eH_{f_e(S)}\le\sum_{e\in E;f_e(S)\gt0}w_eH_n\\ SC(S)=\sum_{e\in E;f_e(S)\gt0}w_e\le\sum_{e\in E;f_e(S)\gt0}w_eH_{f_e(S)}=\Phi(S)\\ SC(S_{eq})\le\Phi(S_{eq})\le\Phi(S^*)\le H_nSC(S^*)

S,SS,S' states that differ in the strategy of player ii.

Strategy of player ii: S=(si,si),S=(si,si)S=(s_{-i},s_i),S'=(s_{-i},s_i')

Φ(S)Φ(S)=eE;fe(S)>0weHfe(S)eE;fe(S)>0weHfe(s)()\Phi(S)-\Phi(S')=\sum_{e\in E;f_e(S)\gt0}w_eH_{f_e(S)}-\sum_{e\in E;f_e(S')\gt0}w_eH_{f_e(s')}(*)

4 cases

  1. E1E_1: edges used by ii in both SS and SS'
  2. E2E_2: edges used by ii in SS not in SS'.
  3. E3E_3: edges used by ii in SS' not in SS.
  4. E4E_4: edges neither used by ii in SS nor SS'

()=eE1,fe(S)>0weHfe(S)+eE2,fe(S)>0weHfe(S)+eE3,fe(S)>0weHfe(S)+eE4,fe(S)>0weHfe(S)eE1,fe(S)>0weHfe(S)eE2,fe(S)>0weHfe(S)eE3,fe(S)>0weHfe(S)eE4,fe(S)>0weHfe(S)=eE1,fe(S)>0,fe(S)>0we(Hfe(S)Hfe(S))+eE2,fe(S)>0we(Hfe(S)Hfe(S))+eE3,fe(S)>0we(Hfe(S)Hfe(S))+eE4,fe(S)>0,fe(S)>0we(Hfe(S)Hfe(S))=eE1,fe(S)>0,fe(S)>0(wefe(S)wefe(S))+eE2,fe(S)>0wefe(S)eE3,fe(S)>0wefe(S)0=esiwefe(S)esiwefe(S)=costi(S)costi(S)(*)=\sum_{e\in E_1,f_e(S)\gt0}w_eH_{f_e(S)}+\sum_{e\in E_2,f_e(S)\gt0}w_eH_{f_e(S)}+\sum_{e\in E_3,f_e(S)\gt0}w_eH_{f_e(S)}+\sum_{e\in E_4,f_e(S)\gt0}w_eH_{f_e(S)}\\ -\sum_{e\in E_1,f_e(S')\gt0}w_eH_{f_e(S')}-\sum_{e\in E_2,f_e(S')\gt0}w_eH_{f_e(S')}-\sum_{e\in E_3,f_e(S')\gt0}w_eH_{f_e(S')}-\sum_{e\in E_4,f_e(S')\gt0}w_eH_{f_e(S')}\\ =\sum_{e\in E_1,f_e(S)\gt0,f_e(S')\gt0}w_e(H_{f_e(S)}-H_{f_e(S')})+\sum_{e\in E_2,f_e(S)\gt0}w_e(H_{f_e(S)}-H_{f_e(S')})\\ +\sum_{e\in E_3,f_e(S')\gt0}w_e(H_{f_e(S)}-H_{f_e(S')})+\sum_{e\in E_4,f_e(S)\gt0,f_e(S')\gt0}w_e(H_{f_e(S)}-H_{f_e(S')})\\ =\cancel{\sum_{e\in E_1,f_e(S)\gt0,f_e(S')\gt0}(\frac{w_e}{f_e(S)}-\frac{w_e}{f_e(S')})}+\sum_{e\in E_2,f_e(S)\gt0}\frac{w_e}{f_e(S)}-\sum_{e\in E_3,f_e(S')\gt0}\frac{w_e}{f_e(S')}-\cancel0\\ =\sum_{e\in s_i}\frac{w_e}{f_e(S)}-\sum_{e\in s_i'}\frac{w_e}{f_e(S')}=\text{cost}_i(S)-\text{cost}_i(S')