Homework 5 Questions

Exercise 11.2 (H) Prove that if $C$ is the set of nonnegative, nondecreasing, and concave cost functions, then $\alpha (C)=\frac{4}{3}$ . CourseNana.COM

  CourseNana.COM

Exercise 11.3 For a positive integer $p$, let $C_p$ denote the set of polynomials with nonnegative coefficients and degree at most p: $Cp=\{\sum _{i=0}^p{a}_i{x}^i:a_0,...,a_p\ge 0\}$. CourseNana.COM

(a) Prove that the Pigou bound of the singleton set $\{x^p\}$ is increasing in $p$. CourseNana.COM

(b) Prove that the Pigou bound of the set $\{a{x}^i:a\ge 0,i\in \{0,1,2...,p\}\}$ is the same as that of the set$\{x^p\}$. CourseNana.COM

(c) (H) Prove that Pigou bound of $C_p$ is the same as that of the set$\{x^p\}$. CourseNana.COM

  CourseNana.COM

Problem 11.2 In this problem we consider an alternative objective function, that of minimizing the maximum travel time CourseNana.COM

$ma{x}_{P\in \mathcal{P}:f_p>0}?\sum _{e\in P}{c}_e(f_e)$ CourseNana.COM

of a flow $f$. The price of anarchy (POA) with respect to this objective is then defined as the ratio between the maximum cost of an equilibrium flow and that of a flow with minimum-possible maximum cost. We assume throughout this problem that there is one origin, one destination, one unit of traffic, and affine cost functions (of the form $c_e(x)=a_{e}x+b_e$ for $a_e,b_e\ge 0$). CourseNana.COM

(a) Prove that in networks with only two vertices $o$ and $d$, and any number of parallel edges, the POA with respect to the maximum cost objective is 1. CourseNana.COM

(b) (H) Prove that the POA with respect to the maximum cost objective can be as large as $4/3$. CourseNana.COM

(c) (H) Prove that the POA with respect to the maximum cost objective is never larger than $4/3$. CourseNana.COM

  CourseNana.COM

Exercise 12.3 Prove that the following statement is equivalent to Theorem 12.1: If $f^{\ast }$ is a minimum-cost flow in a selfish routing network with cost functions $c$ and $f$ is an equilibrium flow in the same network with cost functions $c̃$, where $c̃(x)$ is defined as $c_e(x/2)/2$, then CourseNana.COM

$\tilde{C}(f)\le C(f^{\ast })$ CourseNana.COM

The notation $\tilde{C}$ and $C$ refers to the cost of a flow (11.3) with the cost functions $\tilde{c}$ and $c$, respectively. CourseNana.COM