Today we start to consider other topic than mechanism design.
Review of Braess’ paradoxA road network for sending traffic from location s s s to location t t t
Latency of the long wide road: 1 1 1 hour
Latency of the short narrow road: x x x hours, where x x x is the fraction traffic
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 hours 因为均衡:左边多了会有人到右边,右边多了会有人到左边
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 hours
Price of anarchy: quantifies inefficiencies
Here, price of anarchy = 4 3 \text{price of anarchy}=\frac{4}{3} price of anarchy = 3 4 .
Pigou’s exampleOne unit of traffic from s s s to 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 % , travel time = 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 = = = minimal of average travel 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
Ingredients of a Pigou-like networkTwo nodes, s s s and t t t Two edges between s s s and t t t , called the upper (left) and lower (right) path A non-negative traffic rate r r r A cost function c ( ⋅ ) c(\cdot) c ( ⋅ ) on the lower path Constant cost function equal to c ( r ) c(r) c ( r ) on the upper path
graph TD
1((S))
2((T))
1-->|c ( r )|2
1-->|c ( x )|2
The PoA of a Pigou-like network
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 ) for 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 on the lower path + cost of routing a traffic fraction r − x r-x r − x on the upper path
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 be a set of non-negative, continuous, non-decreasing cost functions:
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 for linear (affine) or concave cost functions.
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 , there is a linear latency function c ′ c' c ′ with c ( r ) = c ′ ( r ) c(r)=c'(r) c ( r ) = c ′ ( r ) , s.t. 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 ) . 分子相等,分母左边比右边小。
The Price of anarchy of selfish routing TheoremFor every set C C C of cost functions, and every selfish routing network with cost functions in C C C , the Price of Anarchy is at most a ( C ) a(C) a ( C ) .
Selfish routing network: connecting node s s s to node t t t
Equilibrium flow: traffic travels only on shortest s − t s-t s − t paths.
Volume of r r r of users who want to route traffic from s s s to t t t .
c e c_e c e : latency function of edge e e e
f e f_e f e : total volume of user who cross edge e = ∑ p , e ∈ p f p e=\sum_{p,e\in p}f_p e = ∑ p , e ∈ p f p
p p p : a path from s s s to t t t in G G G .
f p f_p f p : total volume of user who use path p p p
Equilibrium condition: For every path p p p from s s s to t t t , s.t. f p > 0 f_p\gt0 f p > 0 , the total latency ∑ e ∈ p c e ( f e ) \sum_{e\in p}c_e(f_e) ∑ e ∈ p c e ( f e ) is minimum possible.
C ( f ) C(f) C ( f ) : total cost of set of strategies f f f
f ∗ f^* f ∗ optimal set of strategies i.e. the strategies minimizing the total latency.
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 and f ∗ f^* f ∗ are an equilibrium and optimal flow respectively, then
C ( f ) C ( f ∗ ) ≤ a ( C ) \frac{C(f)}{C(f^*)}\le a(C) C ( f ∗ ) C ( f ) ≤ a ( C ) ProofInformation we will use in the proof: Why don’t the players use their optimal strategies at equilibrium.
Observation: For a path p p p with f p > 0 f_p\gt0 f p > 0 , we have that the latency is minimum possible. i.e. ∑ e ∈ p c e ( f e ) = L \sum_{e\in p}c_e(f_e)=L ∑ e ∈ p c e ( f e ) = L ① which is as low as possible. Meaning that for every path p p p with f p ∗ > 0 f^*_p\gt0 f p ∗ > 0 , We have ∑ 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 from s s s to t t t , we have ∑ 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 from s s s to t t t , we have ∑ 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 ∗ , we have that
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 ∗ )