Atomic selfish routing

3 players: strategies: connect source sis_i with destination tit_i.

Assuming that all edges have latency functions ce(x)=xc_e(x)=x how do the players act?

肯定尽量选不挤的路径。

Load balancing games

Every player has a job and wants to assign it to some machine so that its completion time is minimized

mm parallel machines

  • Machine jj has speed σj\sigma_j
  • If machine jj gets xx jobs, the latency/cost experienced by each of the players/owners of these jobs is xσj\frac{x}{\sigma_j}.

Similar to atomic selfish routing with among nn players who want to route from a common source ss to a common destination tt through mm parallel edges of latency function cj(x)=xσjc_j(x)=\frac{x}{\sigma_j}.

Congestion games

Set NN of nn players, set EE with mm resources

Resource ee has latency function ce:N→R≥0c_e:N\rightarrow\mathbb R_{\ge0}

  • Non-decreasing, denotes the latency caused by the resources to the players who use it.

Player ii has a set of strategies Σi\Sigma_i.

  • Every strategy is a set of resources (denotes the resources used by the player)

State S=(s1,⋯ ,sn)S=(s_1,\cdots,s_n), where player ii selects strategy si∈Σis_i\in\Sigma_i,

Load fe(S)f_e(S) of resource ee at state S=S= number of players who use resource ee at state SS.

Hence, the quantity ce(fe(S))c_e(f_e(S)) denotes the latency incurred by resource ee to the players who use it.

Cost/latency of player ii at state SS:

costi(S)=∑e∈sice(fe(S))\text{cost}_i(S)=\sum_{e\in s_i}c_e(f_e(S))

Every player aims at minimizing own cost

Pure Nash equilibrium: costi≤costi(S−i,s)\text{cost}_i\le\text{cost}_i(S_{-i},s) for every strategy s∈Σis\in\Sigma_i of player ii

Potential functions

Definition: Function Φ:S→R\Phi:\mathbf S\rightarrow\mathbb R is a potential function if for every two states S1S_1 and S2S_2 that differ in the strategy of a single player ii, the differences Φ(S1)−Φ(S2)\Phi(S_1)-\Phi(S_2) and costi(S1)−costi(S2)\text{cost}_i(S_1)-\text{cost}_i(S_2) have the same sign.

Potential games: those admitting a potential function

Theorem: Every potential game have at least one pure Nash equilibrium

Proof

Consider the Nash dynamics graph which has a node for each state of the game and a directed edge from state SS to state S′S' if they differ in the strategy of a single player ii, who improves cost when deviating from the strategy she uses in state SS to the strategy she uses in state S′S'.

By definition of the potential function Φ\Phi, the potential value Φ(S)\Phi(S) is strictly higher than Φ(S′)\Phi(S'). Then, the Nash dynamics graph can not have directed cycles. This implies that there will be a node which is a sink i.e., it has only incoming edges. Let SS be such the state corresponding to this node. Then, no player has an incentive to deviate from SS. Thus, SS is a pure Nash equilibrium.

Rosenthal’s potential function

Theorem: for every congestion games, the function

Φ(S)=∑e∈E∑j=1fe(S)ce(j)\Phi(S)=\sum_{e\in E}\sum_{j=1}^{f_e(S)}c_e(j)

is a potential function.

Proof

We will show that for two states S1,S2S_1,S_2 that different in the strategy of player ii, it holds Φ(S1)−Φ(S2)=costi(S1)−costi(S2)\Phi(S_1)-\Phi(S_2)=\text{cost}_i(S_1)-\text{cost}_i(S_2).

By the definition of Rosenthal’s potential function, we have

Φ(S)−Φ(S′)=∑e∈E∑j=1fe(S)ce(j)−∑e∈E∑j=1fe(S′)ce(j)=∑e∈E(∑j=1fe(S)ce(j)−∑j=1fe(S′)ce(j))=∑e∉si∪si′(∑j=1fe(S)ce(j)−∑j=1fe(S′)ce(j))+∑e∈si∩si′(∑j=1fe(S)ce(j)−∑j=1fe(S′)ce(j))+∑e∈si╲si′(∑j=1fe(S)ce(j)−∑j=1fe(S′)ce(j))+∑e∈si′╲si(∑j=1fe(S)ce(j)−∑j=1fe(S′)ce(j))\Phi(S)-\Phi(S')=\sum_{e\in E}\sum_{j=1}^{f_e(S)}c_e(j)-\sum_{e\in E}\sum_{j=1}^{f_e(S')}c_e(j)\\ =\sum_{e\in E}\left(\sum_{j=1}^{f_e(S)}c_e(j)-\sum_{j=1}^{f_e(S')}c_e(j)\right)\\ =\sum_{e\notin s_i\cup s_i'}\left(\sum_{j=1}^{f_e(S)}c_e(j)-\sum_{j=1}^{f_e(S')}c_e(j)\right)+\sum_{e\in s_i\cap s_i'}\left(\sum_{j=1}^{f_e(S)}c_e(j)-\sum_{j=1}^{f_e(S')}c_e(j)\right)\\ +\sum_{e\in s_i\diagdown s_i'}\left(\sum_{j=1}^{f_e(S)}c_e(j)-\sum_{j=1}^{f_e(S')}c_e(j)\right)+\sum_{e\in s_i'\diagdown s_i}\left(\sum_{j=1}^{f_e(S)}c_e(j)-\sum_{j=1}^{f_e(S')}c_e(j)\right)

Now, we can observe the following

  1. if e∉si∪si′e\notin s_i\cup s_i', then fe(S)=fe(S′)f_e(S)=f_e(S') and hence, ∑j=1fe(S)ce(j)−∑j=1fe(S′)ce(j)=0\sum_{j=1}^{f_e(S)}c_e(j)-\sum_{j=1}^{f_e(S')}c_e(j)=0
  2. if e∈si∩si′e\in s_i\cap s_i', then fe(S)=fe(S′)f_e(S)=f_e(S') and hence, ∑j=1fe(S)ce(j)−∑j=1fe(S′)ce(j)=ce(fe(S))−ce(fe(S′))\sum_{j=1}^{f_e(S)}c_e(j)-\sum_{j=1}^{f_e(S')}c_e(j)=c_e(f_e(S))-c_e(f_e(S'))
  3. if e∈si╲si′e\in s_i\diagdown s_i', then fe(S)=fe(S′)+1f_e(S)=f_e(S')+1 and hence, ∑j=1fe(S)ce(j)−∑j=1fe(S′)ce(j)=ce(fe(S))\sum_{j=1}^{f_e(S)}c_e(j)-\sum_{j=1}^{f_e(S')}c_e(j)=c_e(f_e(S))
  4. if e∈si′╲sie\in s_i'\diagdown s_i, then fe(S)=fe(S′)−1f_e(S)=f_e(S')-1 and hence, ∑j=1fe(S)ce(j)−∑j=1fe(S′)ce(j)=−ce(fe(S′))\sum_{j=1}^{f_e(S)}c_e(j)-\sum_{j=1}^{f_e(S')}c_e(j)=-c_e(f_e(S'))

Thus, we have

Φ(S)−Φ(S′)=∑e∈si∩si′(ce(fe(S))−ce(fe(S′)))+∑e∈si╲si′ce(fe(S))−∑e∈si′╲sice(fe(S′))=∑e∈sice(fe(S))−∑e∈si′ce(fe(S′))=costi(S)−costi(S′)\Phi(S)-\Phi(S')=\sum_{e\in s_i\cap s_i'}(c_e(f_e(S))-c_e(f_e(S')))+\sum_{e\in s_i\diagdown s_i'}c_e(f_e(S))-\sum_{e\in s_i'\diagdown s_i}c_e(f_e(S'))\\ =\sum_{e\in s_i}c_e(f_e(S))-\sum_{e\in s_i'}c_e(f_e(S'))\\ =\text{cost}_i(S)-\text{cost}_i(S')

The social cost

Quantification of the performance of a system that is modeled by a strategic game

Typically SC(S)=∑i∈Ncosti(S)SC(S)=\sum_{i\in N}\text{cost}_i(S)

The state that minimizes the social cost is not necessarily a pure Nash equilibrium.

So equilibrium are suboptimal

How is this sub-optimality quantified? Price of anarchy/Price of stability.

Price of stability/anarchy

PoS=min⁡s∈EQSC(s)SC(s∗)PoA=max⁡s∈EQSC(s)SC(s∗)PoS=\min_{s\in EQ}\frac{SC(s)}{SC(s^*)}\\ PoA=\max_{s\in EQ}\frac{SC(s)}{SC(s^*)}

where s∗s^* denotes the optimal state i.e., one of minimum social cost.

PoS/PoA is an optimistic/pessimistic measure:

  • How close to/far from the optimal social cost can a system/game be due to strategic behavior

Linear Congestion games

Price of stability

Linear congestion games: resources ee has latency function

ce(x)=aex+bec_e(x)=a_ex+b_e

Lemma: The social cost of a linear congestion game and Rosenthal’s potential function value at state SS are connected with the inequalities

SC(S)2≤Φ(S)≤SC(S)\frac{SC(S)}{2}\le\Phi(S)\le SC(S)

Proof

By definition of latency functions in linear congestion games and the definition of the social cost, we have:

SC(S)=∑i∈Ncosti(S)=∑i∈N∑e∈sice(fe(S))=∑e∈Ece(fe(S))×∑i∈N:e∈si1=∑e∈Efe(S)(aefe(S)+be)=∑e∈E(aefe(S)2+fe(S)be)SC(S)=\sum_{i\in N}\text{cost}_i(S)\\ =\sum_{i\in N}\sum_{e\in s_i}c_e(f_e(S))\\ =\sum_{e\in E}c_e(f_e(S))\times\sum_{i\in N:e\in s_i}1\\ =\sum_{e\in E}f_e(S)(a_ef_e(S)+b_e)\\ =\sum_{e\in E}(a_ef_e(S)^2+f_e(S)b_e)

Also, by definition of Rosenthal’s potential function, we have:

Φ(S)=∑e∈E∑j=1fe(S)ce(j)=∑e∈E∑j=1fe(S)(aej+be)=∑e∈E(ae∑j=1fe(S)j+fe(S)be)=∑e∈E(aefe(S)2+fe(S)2+fe(S)be)\Phi(S)=\sum_{e\in E}\sum_{j=1}^{f_e(S)}c_e(j)\\ =\sum_{e\in E}\sum_{j=1}^{f_e(S)}(a_ej+b_e)\\ =\sum_{e\in E}\left(a_e\sum_{j=1}^{f_e(S)}j+f_e(S)b_e\right)\\ =\sum_{e\in E}\left(a_e\frac{f_e(S)^2+f_e(S)}{2}+f_e(S)b_e\right)

To prove the leftmost inequality in the statement of the lemma, it suffice to bound the potential function from below. Working with the equivalent expression for Φ(S)\Phi(S), we have:

Φ(S)=∑e∈E(aefe(S)2+fe(S)2+fe(S)be)≥∑e∈E(aefe(S)22+befe(S))≥∑e∈E(aefe(S)22+befe(S)2)=12∑e∈E(aefe(S)2+fe(S)be)=12SC(S)\Phi(S)=\sum_{e\in E}\left(a_e\frac{f_e(S)^2+f_e(S)}{2}+f_e(S)b_e\right)\\ \ge\sum_{e\in E}\left(a_e\frac{f_e(S)^2}{2}+b_ef_e(S)\right)\\ \ge\sum_{e\in E}\left(a_e\frac{f_e(S)^2}{2}+b_e\frac{f_e(S)}{2}\right)\\ =\frac{1}{2}\sum_{e\in E}(a_ef_e(S)^2+f_e(S)b_e)\\ =\frac{1}{2}SC(S)

For the rightmost inequality, we bound the potential function from above as follows:

Φ(S)=∑e∈E(aefe(S)2+fe(S)2+fe(S)be)≤∑e∈E(aefe(S)2+fe(S)22+fe(S)be)=∑e∈E(aefe(S)2+fe(S)be)=SC(S)\Phi(S)=\sum_{e\in E}\left(a_e\frac{f_e(S)^2+f_e(S)}{2}+f_e(S)b_e\right)\\ \le\sum_{e\in E}\left(a_e\frac{f_e(S)^2+f_e(S)^2}{2}+f_e(S)b_e\right)\\ =\sum_{e\in E}(a_ef_e(S)^2+f_e(S)b_e)\\ =SC(S)

Q. E. D.

Theorem: The PoS of linear congestion games is at most 2.

Proof

We use potential function method, We start from the state S∗S^* of minimum social cost. If it is a pure Nash equilibrium, then the price of stability is 11. Otherwise, we let the players change their strategies and improve their cost until we reach an equilibrium SS. By Lemma above, we have SC(S)≤2Φ(S)SC(S)\le2\Phi(S), By the main property of the potential function, we have that Φ(S)≤Φ(S∗)\Phi(S)\le\Phi(S^*). Finally, again by Lemma above, we have that Φ(S∗)≤SC(S∗)\Phi(S^*)\le SC(S^*). Thus,

SC(S)≤2Φ(S)≤2Φ(S∗)≤2SC(S∗)SC(S)\le2\Phi(S)\le2\Phi(S^*)\le2SC(S^*)

The above bound is not best possible, An upper bound of 1+13≈1.5781+\frac{1}{\sqrt3}\approx 1.578 has been proved.

A lower bound on the price of anarchy

4 player

pure Nash equilibrium

  • Each player uses two edges
  • social cost = 10

optimal state:

  • every player uses her direct edge
  • social cost = 4
  • PoS=52PoS=\frac{5}{2}

A matching upper bound

Theorem: The price of anarchy of linear congestion game is at most 52\frac{5}{2}.

Proof（⚠️难度贼高的证明）

Lemma first

先证明引理 ∀x,y∈N,xy+y≤x23+5y23\forall x,y\in \mathbb N,xy+y\le\frac{x^2}{3}+\frac{5y^2}{3}.

⇔x2+5y2−3xy−3y≥0\Lrarr x^2+5y^2-3xy-3y\ge0

Obviously true if y=0y=0.

If y=1y=1, we need to show that x2−3x+2≥0⇔(x−1)(x−2)≥0x^2-3x+2\ge0\Lrarr(x-1)(x-2)\ge0

显然成立，对于 x=1,2x=1,2，二次函数=0，对于大于 3，小于 0，两项同号。

If y≥2y\ge2, 5y2−3y≥94y25y^2-3y\ge\frac{9}{4}y^2, hence x2+5y2−3xy−3y>x2−3xy+94y2=(x−32y)2≥0x^2+5y^2-3xy-3y\gt x^2-3xy+\frac{9}{4}y^2=(x-\frac{3}{2}y)^2\ge0.

引理证明完毕。（难点一：想出引理并证明）

Now consider a linear congestion game and let S∗=(s1∗,⋯ ,sn∗)S^*=(s_1^*,\cdots,s_n^*) be the state of minimum social cost and S=(s1,⋯ ,sn)S=(s_1,\cdots,s_n) a pure Nash equilibrium. Thus, at state SS, no player ii has an incentive to change her strategy sis_i to si∗s_i^*, i.e., for every player ii, it holds costi(S)≤costi(S−i,si∗)\text{cost}_i(S)\le\text{cost}_i(S_{-i},s_i^*)（这个放缩指的意思是，在一个纳什均衡状态下，某一个智能体单方面改变其策略只能是 social cost 增大）.

Summing over all players, we get

SC(S)=∑i∈Ncosti(S)≤∑i∈Ncosti(S−i,si∗)=∑i∈N∑e∈si∗ce(fe(S−i,si∗))=∑i∈N∑e∈si∗(aefe(S−i,si∗)+be)SC(S)=\sum_{i\in N}\text{cost}_i(S)\\ \le\sum_{i\in N}\text{cost}_i(S_{-i},s_i^*)\\ =\sum_{i\in N}\sum_{e\in s_i^*}c_e(f_e(S_{-i},s_i^*))\\ =\sum_{i\in N}\sum_{e\in s_i^*}(a_ef_e(S_{-i},s_i^*)+b_e)

Notice that for every resource e∈Ee\in E, it holds that fe(S−i,si∗)≤fe(S)+1f_e(S_{-i},s_i^*)\le f_e(S)+1（难点二（放缩）：对于任何一种资源，当一个智能体的策略改变时，该资源的负载最多是之前状态下的负载加 1，取等的条件是：智能体 ii 在策略 sis_i 下没有使用资源 ee, 而在 si′s_i' 策略下使用了资源 ee） since only one player changes her strategy at state (S−i,si∗)(S_{-i},s_i^*) compared to state SS. Thus, we have:

SC(S)≤∑i∈N∑e∈si∗(ae(fe(S)+1)+be)=∑e∈E∑i∈N:e∈si∗(ae(fe(S)+1)+be)=∑e∈Efe(S∗)(ae(fe(S)+1)+be)=∑e∈E(aefe(S∗)fe(S)+aefe(S∗)+befe(S∗))SC(S)\le\sum_{i\in N}\sum_{e\in s_i^*}(a_e(f_e(S)+1)+b_e)\\ =\sum_{e\in E}\sum_{i\in N:e\in s_i^*}(a_e(f_e(S)+1)+b_e)\\ =\sum_{e\in E}f_e(S^*)(a_e(f_e(S)+1)+b_e)\\ =\sum_{e\in E}(a_ef_e(S^*)f_e(S)+a_ef_e(S^*)+b_ef_e(S^*))

By applying Lemma above for x=fe(S),y=fe(S∗)x=f_e(S),y=f_e(S^*), we have:

SC(S)≤∑e∈E(13aefe(S)2+53aefe(S∗)2+befe(S∗))≤13∑e∈E(aefe(S)2+befe(S))+53∑e∈E(aefe(S∗)2+befe(S∗))=13SC(S)+53SC(S∗)SC(S)\le\sum_{e\in E}\left(\frac{1}{3}a_ef_e(S)^2+\frac{5}{3}a_ef_e(S^*)^2+b_ef_e(S^*)\right)\\ \le\frac{1}{3}\sum_{e\in E}(a_ef_e(S)^2+b_ef_e(S))+\frac{5}{3}\sum_{e\in E}(a_ef_e(S^*)^2+b_ef_e(S^*))\\ =\frac{1}{3}SC(S)+\frac{5}{3}SC(S^*)

Thus we conclude that SC(S)≤52SC(S∗)SC(S)\le\frac{5}{2}SC(S^*)

Q. E. D.