Today we start to consider other topic than mechanism design.
A road network for sending traffic from location s s s t t t
Latency of the long wide road: 1 1 1
Latency of the short narrow road: x x x x x x
graph TD
1((S))
2((T))
3((A))
4((B))
1-->|short narrow road|3
1-->|long wide road|4
3-->|long wide road|2
4-->|short narrow road|2
Travel time: 1.5 1.5 1 . 5
If authority build a very fast short-cut from A to B:
graph TD
1((S))
2((T))
3((A))
4((B))
1-->|short narrow road|3
1-->|long wide road|4
3-->|long wide road|2
4-->|short narrow road|2
3-->|teleportation|4
All users have an incentive to use the new road
假设只走左边的有 α \alpha α β \beta β 1 − α − β 1-\alpha-\beta 1 − α − β
对于只走左边的时间：( α + ( 1 − α − β ) ) + 1 = 1 − β + 1 = 2 − β (\alpha+(1-\alpha-\beta))+1=1-\beta+1=2-\beta ( α + ( 1 − α − β ) ) + 1 = 1 − β + 1 = 2 − β
同理，对于只走右边的时间：1 + 1 − α = 2 − α 1+1-\alpha=2-\alpha 1 + 1 − α = 2 − α
对于使用传送节点的时间：1 − β + 0 + 1 − α = 2 − α − β 1-\beta+0+1-\alpha=2-\alpha-\beta 1 − β + 0 + 1 − α = 2 − α − β
可以看出使用传送节点对于所有人都是最优选。
New travel time: 2 2 2
Price of anarchy: quantifies inefficiencies
Here, price of anarchy = 4 3 \text{price of anarchy}=\frac{4}{3} price of anarchy = 3 4
One unit of traffic from s s s t t t
graph TD
1((S))
2((T))
1-->|c ( x ) =1|2
1-->|c ( x ) =x|2
Equilibrium: all traffic uses the lower path (x = 100 % x=100\% x = 1 0 0 % 1 1 1
Optimal route (i.e., minimizing average travel time): half traffic through the left path, half traffic from the right path.
Optimal average travel time = 3 4 =\frac{3}{4} = 4 3
Price of anarchy = 4 3 =\frac{4}{3} = 3 4
What if for short path, c ( x ) = x p c(x)=x^p c ( x ) = x p
graph TD
1((S))
2((T))
1-->|c ( x ) =1|2
1-->|c ( x ) =x^p|2
Optimal route: some traffic through the left path, some traffic through the right path.
Average travel time = 1 × ( 1 − x ) + x × x p \text{Average travel time}=1\times(1-x)+x\times x^p Average travel time = 1 × ( 1 − x ) + x × x p Optimal average time = = = = ( 1 p + 1 ) p + 1 p − ( 1 p + 1 ) 1 p + 1 =(\frac{1}{p+1})^\frac{p+1}{p}-(\frac{1}{p+1})^\frac{1}{p}+1 = ( p + 1 1 ) p p + 1 − ( p + 1 1 ) p 1 + 1
Price of anarchy depends on p p p
Two nodes, s s s t t t Two edges between s s s t t t A non-negative traffic rate r r r A cost function c ( ⋅ ) c(\cdot) c ( ⋅ ) Constant cost function equal to c ( r ) c(r) c ( r )
graph TD
1((S))
2((T))
1-->|c ( r )|2
1-->|c ( x )|2
PoA = sup x ≥ 0 { r × c ( r ) x × c ( x ) + ( r − x ) × c ( r ) } = sup 0 ≤ x ≤ r { r × c ( r ) x × c ( x ) + ( r − x ) × c ( r ) } \text{PoA}=\sup_{x\ge0}\{\frac{r\times c(r)}{x\times c(x)+(r-x)\times c(r)}\}=\sup_{0\le x\le r}\{\frac{r\times c(r)}{x\times c(x)+(r-x)\times c(r)}\} PoA = x ≥ 0 sup { x × c ( x ) + ( r − x ) × c ( r ) r × c ( r ) } = 0 ≤ x ≤ r sup { x × c ( x ) + ( r − x ) × c ( r ) r × c ( r ) } ∀ x > r , ∃ x ′ ∈ [ 0 , r ] : x ⋅ c ( x ) + ( r − x ) ⋅ c ( r ) ≥ x ′ ⋅ c ( x ′ ) + ( r − x ′ ) ⋅ c ( r ) \forall x\gt r,\exist x'\in[0,r]:x\cdot c(x)+(r-x)\cdot c(r)\ge x'\cdot c(x')+(r-x')\cdot c(r) ∀ x > r , ∃ x ′ ∈ [ 0 , r ] : x ⋅ c ( x ) + ( r − x ) ⋅ c ( r ) ≥ x ′ ⋅ c ( x ′ ) + ( r − x ′ ) ⋅ c ( r )
To prove this, it suffices to observe that
x ⋅ c ( x ) + ( r − x ) ⋅ c ( r ) = r ⋅ c ( r ) + x ( c ( x ) − c ( r ) ) ≥ r ⋅ c ( r ) = x ′ ⋅ c ( x ′ ) + ( r − x ′ ) ⋅ c ( r ) x\cdot c(x)+(r-x)\cdot c(r)=r\cdot c(r)+x(c(x)-c(r))\ge r\cdot c(r)=x'\cdot c(x')+(r-x')\cdot c(r) x ⋅ c ( x ) + ( r − x ) ⋅ c ( r ) = r ⋅ c ( r ) + x ( c ( x ) − c ( r ) ) ≥ r ⋅ c ( r ) = x ′ ⋅ c ( x ′ ) + ( r − x ′ ) ⋅ c ( r ) x ′ = r ∈ [ 0 , r ] x'=r\in[0,r] x ′ = r ∈ [ 0 , r ]
Price of Anarchy equals:
cost at equilibrium (all routing traffic on the lower path) over
cost of routing a traffic fraction x x x r − x r-x r − x
Family of latency functions C C C
linear latencies: c ( x ) = a x + b c(x)=ax+b c ( x ) = a x + b a , b ≥ 0 a,b\ge0 a , b ≥ 0 quadratic latencies: c ( x ) = a x 2 + b x + c c(x)=ax^2+bx+c c ( x ) = a x 2 + b x + c a , b , c ≥ 0 a,b,c\ge0 a , b , c ≥ 0 polynomial of degree d: c ( x ) = ∑ j = 0 d a j x j c(x)=\sum_{j=0}^da_jx^j c ( x ) = ∑ j = 0 d a j x j a j ≥ 0 a_j\ge0 a j ≥ 0 concave non-decreasing function 上凸非减函数 Let C C C
a ( C ) = sup c ∈ C sup r ≥ 0 sup x ≥ 0 { r × c ( r ) x × c ( x ) + ( r − x ) × c ( r ) } a(C)=\sup_{c\in C}\sup_{r\ge0}\sup_{x\ge0}\{\frac{r\times c(r)}{x\times c(x)+(r-x)\times c(r)}\} a ( C ) = c ∈ C sup r ≥ 0 sup x ≥ 0 sup { x × c ( x ) + ( r − x ) × c ( r ) r × c ( r ) } Application: PoA = 4 3 \text{PoA}=\frac{4}{3} PoA = 3 4
c ( x ) = α x + β c(x)=\alpha x+\beta c ( x ) = α x + β a ( linear ) = sup α , β ≥ 0 sup r ≥ 0 sup x ≥ 0 r ( α r + β ) x ( α x + β ) + ( r − x ) ( α r + β ) a(\text{linear})=\sup_{\alpha,\beta\ge0}\sup_{r\ge0}\sup_{x\ge0}\frac{r(\alpha r+\beta)}{x(\alpha x+\beta)+(r-x)(\alpha r+\beta)} a ( linear ) = sup α , β ≥ 0 sup r ≥ 0 sup x ≥ 0 x ( α x + β ) + ( r − x ) ( α r + β ) r ( α r + β )
derivative of denominator = 0 ⇒ 2 α x + β − α r − β = 0 ⇒ x = r 2 =0\Rarr2\alpha x+\beta-\alpha r-\beta=0\Rarr x=\frac{r}{2} = 0 ⇒ 2 α x + β − α r − β = 0 ⇒ x = 2 r
Thus, the denominator becomes: α r 2 4 + β r 2 + α r 2 2 + β r 2 = 3 4 α r 2 + β r ≥ 3 4 r ( α r + β ) \alpha\frac{r^2}{4}+\frac{\beta r}{2}+\alpha\frac{r^2}{2}+\frac{\beta r}{2}=\frac{3}{4}\alpha r^2+\beta r\ge\frac{3}{4}r(\alpha r+\beta) α 4 r 2 + 2 β r + α 2 r 2 + 2 β r = 4 3 α r 2 + β r ≥ 4 3 r ( α r + β )
所以无序的代价 PoA 最大值是 4 3 \frac{4}{3} 3 4
a ( concave non-decreasing ) = 4 3 a(\text{concave non-decreasing})=\frac{4}{3} a ( concave non-decreasing ) = 3 4 For every concave non-decreasing latency function c c c c ′ c' c ′ c ( r ) = c ′ ( r ) c(r)=c'(r) c ( r ) = c ′ ( r ) r ⋅ c ( r ) x ⋅ c ( x ) + ( r − x ) ⋅ c ( r ) ≤ r ⋅ c ′ ( r ) x ⋅ c ′ ( x ) + ( r − x ) ⋅ c ′ ( r ) \frac{r\cdot c(r)}{x\cdot c(x)+(r-x)\cdot c(r)}\le\frac{r\cdot c'(r)}{x\cdot c'(x)+(r-x)\cdot c'(r)} x ⋅ c ( x ) + ( r − x ) ⋅ c ( r ) r ⋅ c ( r ) ≤ x ⋅ c ′ ( x ) + ( r − x ) ⋅ c ′ ( r ) r ⋅ c ′ ( r )
通过画图可以证明，上凸函数和线性函数 x ⋅ c ( x ) ≥ x ⋅ c ′ ( x ) x\cdot c(x)\ge x\cdot c'(x) x ⋅ c ( x ) ≥ x ⋅ c ′ ( x ) ( r − x ) ⋅ c ( r ) = ( r − x ) ⋅ c ′ ( r ) (r-x)\cdot c(r)=(r-x)\cdot c'(r) ( r − x ) ⋅ c ( r ) = ( r − x ) ⋅ c ′ ( r )
For every set C C C C C C a ( C ) a(C) a ( C )
Selfish routing network: connecting node s s s t t t
Equilibrium flow: traffic travels only on shortest s − t s-t s − t
Volume of r r r s s s t t t
c e c_e c e e e e
f e f_e f e e = ∑ p , e ∈ p f p e=\sum_{p,e\in p}f_p e = ∑ p , e ∈ p f p
p p p s s s t t t G G G
f p f_p f p p p p
Equilibrium condition: For every path p p p s s s t t t f p > 0 f_p\gt0 f p > 0 ∑ e ∈ p c e ( f e ) \sum_{e\in p}c_e(f_e) ∑ e ∈ p c e ( f e )
C ( f ) C(f) C ( f ) f f f
f ∗ f^* f ∗
Cost of a flow:
C ( f ) = ∑ e ∈ E f e × c e ( f e ) C(f)=\sum_{e\in E}f_e\times c_e(f_e) C ( f ) = e ∈ E ∑ f e × c e ( f e ) Assume that f f f f ∗ f^* f ∗
C ( f ) C ( f ∗ ) ≤ a ( C ) \frac{C(f)}{C(f^*)}\le a(C) C ( f ∗ ) C ( f ) ≤ a ( C ) Information we will use in the proof: Why don’t the players use their optimal strategies at equilibrium.
Observation: For a path p p p f p > 0 f_p\gt0 f p > 0 ∑ e ∈ p c e ( f e ) = L \sum_{e\in p}c_e(f_e)=L ∑ e ∈ p c e ( f e ) = L p p p f p ∗ > 0 f^*_p\gt0 f p ∗ > 0 ∑ e ∈ p c e ( f e ) ≥ L \sum_{e\in p}c_e(f_e)\ge L ∑ e ∈ p c e ( f e ) ≥ L
By summing ① for all paths with f p > 0 f_p\gt0 f p > 0 s s s t t t ∑ p : f p > 0 f p ⋅ ∑ e ∈ p c e ( f e ) = ∑ p : f p > 0 L ⋅ f p = r × L \sum_{p:f_p\gt0}f_p\cdot\sum_{e\in p}c_e(f_e)=\sum_{p: f_p\gt0}L\cdot f_p=r\times L ∑ p : f p > 0 f p ⋅ ∑ e ∈ p c e ( f e ) = ∑ p : f p > 0 L ⋅ f p = r × L
By doing the same with ② and all paths with f p ∗ > 0 f^*_p\gt0 f p ∗ > 0 s s s t t t ∑ p : f p ∗ > 0 f p ∗ ⋅ ∑ e ∈ p c e ( f e ) ≥ ∑ p : f p ∗ > 0 f p ∗ L = r × L \sum_{p:f^*_p\gt0}f^*_p\cdot\sum_{e\in p}c_e(f_e)\ge\sum_{p:f^*_p\gt0}f^*_pL=r\times L ∑ p : f p ∗ > 0 f p ∗ ⋅ ∑ e ∈ p c e ( f e ) ≥ ∑ p : f p ∗ > 0 f p ∗ L = r × L
The Left Hand Side of ③ is equal to ∑ p : f p > 0 f p ⋅ ∑ e ∈ p c e ( f e ) \sum_{p:f_p\gt0}f_p\cdot\sum_{e\in p}c_e(f_e) ∑ p : f p > 0 f p ⋅ ∑ e ∈ p c e ( f e )
= ∑ e ∈ E ∑ p : f p > 0 , e ∈ p f p ⋅ c e ( f e ) = ∑ e ∈ E c e ( f e ) ∑ p : f p > 0 , e ∈ p f p =\sum_{e\in E}\sum_{p:f_p\gt0,e\in p}f_p\cdot c_e(f_e)=\sum_{e\in E}c_e(f_e)\sum_{p:f_p\gt0,e\in p}f_p = ∑ e ∈ E ∑ p : f p > 0 , e ∈ p f p ⋅ c e ( f e ) = ∑ e ∈ E c e ( f e ) ∑ p : f p > 0 , e ∈ p f p
The LHS of ④ is equal to ∑ e ∈ p ∑ p : f p ∗ > 0 f p ∗ ⋅ c e ( f e ) \sum_{e\in p}\sum_{p:f^*_p\gt0}f^*_p\cdot c_e(f_e) ∑ e ∈ p ∑ p : f p ∗ > 0 f p ∗ ⋅ c e ( f e )
= ∑ e ∈ E ∑ e ∈ p , p : f p ∗ > 0 f p ∗ c e ( f e ) = ∑ e ∈ E c e ( f e ) ∑ e ∈ p , p : f p ∗ > 0 f p ∗ = ∑ e ∈ E f e ∗ c e ( f e ) =\sum_{e\in E}\sum_{e\in p,p:f^*_p\gt0}f^*_pc_e(f_e)=\sum_{e\in E}c_e(f_e)\sum_{e\in p,p:f^*_p\gt0}f^*_p=\sum_{e\in E}f^*_ec_e(f_e) = ∑ e ∈ E ∑ e ∈ p , p : f p ∗ > 0 f p ∗ c e ( f e ) = ∑ e ∈ E c e ( f e ) ∑ e ∈ p , p : f p ∗ > 0 f p ∗ = ∑ e ∈ E f e ∗ c e ( f e )
From ③ and ④ and their equivalent expressions, we have ∑ e ∈ E ( f e ∗ − f e ) c e ( f e ) ≥ 0 \sum_{e\in E}(f^*_e-f_e)c_e(f_e)\ge0 ∑ e ∈ E ( f e ∗ − f e ) c e ( f e ) ≥ 0
a ( c ) = sup c ∈ C sup r ≥ 0 sup x ≥ 0 r c ( r ) x c ( x ) + ( r − x ) c ( r ) a(c)=\sup_{c\in C}\sup_{r\ge0}\sup_{x\ge0}\frac{rc(r)}{xc(x)+(r-x)c(r)} a ( c ) = sup c ∈ C sup r ≥ 0 sup x ≥ 0 x c ( x ) + ( r − x ) c ( r ) r c ( r )
Thus, using c = c e , r = f e , x = f e ∗ c=c_e,r=f_e,x=f^*_e c = c e , r = f e , x = f e ∗
a ( c ) ≥ f e c e ( f e ) f e ∗ c e ( f e ∗ ) + ( f e − f e ∗ ) c ( f e ) a(c)\ge\frac{f_ec_e(f_e)}{f^*_ec_e(f^*_e)+(f_e-f^*_e)c(f_e)} a ( c ) ≥ f e ∗ c e ( f e ∗ ) + ( f e − f e ∗ ) c ( f e ) f e c e ( f e )
⇒ f e c e ( f e ) ≤ a ( c ) f e ∗ c e ( f e ∗ ) + a ( c ) ( f e − f e ∗ ) c e ( f e ) \Rarr f_ec_e(f_e)\le a(c)f^*_ec_e(f^*_e)+a(c)(f_e-f^*_e)c_e(f_e) ⇒ f e c e ( f e ) ≤ a ( c ) f e ∗ c e ( f e ∗ ) + a ( c ) ( f e − f e ∗ ) c e ( f e )
Summing over all edges, we have
∑ e ∈ E f e c e ( f e ) ≤ a ( c ) ∑ e ∈ E f e ∗ c e ( f e ∗ ) + a ( c ) ∑ e ∈ E ( f e ∗ − f e ) c e ( f e ) ≤ a ( c ) ∑ e ∈ E f e ∗ c e ( f e ∗ ) ⇒ c ( f ) = ∑ p f p ∑ e ∈ p c e ( f e ) = ∑ p ∑ e f p c e ( f e ) = ∑ e f e c e ( f e ) ∴ c ( f ) ≤ a ( c ) ⋅ c ( f ∗ ) \sum_{e\in E}f_ec_e(f_e)\le a(c)\sum_{e\in E}f^*_ec_e(f^*_e)+a(c)\sum_{e\in E}(f^*_e-f_e)c_e(f_e)\\ \le a(c)\sum_{e\in E}f^*_ec_e(f^*_e)\\ \Rarr c(f)=\sum_pf_p\sum_{e\in p}c_e(f_e)=\sum_p\sum_ef_pc_e(f_e)=\sum_ef_ec_e(f_e)\\ \therefore c(f)\le a(c)\cdot c(f^*) e ∈ E ∑ f e c e ( f e ) ≤ a ( c ) e ∈ E ∑ f e ∗ c e ( f e ∗ ) + a ( c ) e ∈ E ∑ ( f e ∗ − f e ) c e ( f e ) ≤ a ( c ) e ∈ E ∑ f e ∗ c e ( f e ∗ ) ⇒ c ( f ) = p ∑ f p e ∈ p ∑ c e ( f e ) = p ∑ e ∑ f p c e ( f e ) = e ∑ f e c e ( f e ) ∴ c ( f ) ≤ a ( c ) ⋅ c ( f ∗ ) 
