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. aA 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.