Problem 2 Let I = (G= (V, A), (la)a=A, (Si, ti)i=[k], (ri)ic[k]) be a self- ish...

Transcribed Image Text:

Problem 2 Let I = (G= (V, A), (la)a=A, (Si, ti)i=[k], (ri)ic[k]) be a self- ish routing instance with standard latency functions. Suppose we can impose a non-negative toll Ta 20 on every arc a E A. Each player traversing arc a € A now experiences a latency of la(x) plus A times the respective toll Ta. Here A> 0 is a pa- rameter that reflects the players' sensitivity with respect to the tolls. More formally, given tolls T = (Ta)aEA, we define the combined costs (ca)aEA as ca(x) = a (x) + A. Ta Va € A. As before, we define the cost C(f) of a feasible flow fas C(f) = Σla(fa) fa. a€A In particular, note that the cost function C does not account for the imposed tolls. We say that the tolls T = (Ta)acA are opt-inducing if there exists a feasible flow f for I such that (i) f is a Nash flow with respect to the combined costs (ca)aEA, and (ii) f is also an optimal flow with respect to C. Derive an algorithm that computes opt-inducing tolls efficiently and prove its cor- rectness. Problem 2 Let I = (G= (V, A), (la)a=A, (Si, ti)i=[k], (ri)ic[k]) be a self- ish routing instance with standard latency functions. Suppose we can impose a non-negative toll Ta 20 on every arc a E A. Each player traversing arc a € A now experiences a latency of la(x) plus A times the respective toll Ta. Here A> 0 is a pa- rameter that reflects the players' sensitivity with respect to the tolls. More formally, given tolls T = (Ta)aEA, we define the combined costs (ca)aEA as ca(x) = a (x) + A. Ta Va € A. As before, we define the cost C(f) of a feasible flow fas C(f) = Σla(fa) fa. a€A In particular, note that the cost function C does not account for the imposed tolls. We say that the tolls T = (Ta)acA are opt-inducing if there exists a feasible flow f for I such that (i) f is a Nash flow with respect to the combined costs (ca)aEA, and (ii) f is also an optimal flow with respect to C. Derive an algorithm that computes opt-inducing tolls efficiently and prove its cor- rectness.

Answer rating: 100% (QA)

Solution Pis a Mash equilibrium Well prove that Ps social cost is at mos... View the full answer