Problem $3(20$ points$).$ Let $I=(G=(V,A),(l_a{)}_{\text{a}\text{i}\text{n}\text{A}},(s_i,t_i{)}_{\text{i}\text{i}\text{n}[k]},(r_i{)}_{\text{i}\text{i}\text{n}[k]})$ be a self$-$

ish routing instance with standard latency functions. Suppose we can impose a

non$-$negative toll ${}_{a}0$ on every arc ainA. Each player traversing arc ainA now

experiences a latency of $l_a(x)$ plus $$ times the respective toll ${}_a.$ Here $>0$ is a pa$-$

rameter that reflects the players' sensitivity with respect to the tolls. More formally,

given tolls $=({}_a{)}_{\text{a}\text{i}\text{n}\text{A}},$ we define the combined costs $(c_a^{}{)}_{\text{a}\text{i}\text{n}\text{A}}$ as

$c_a^{}(x)$:$=l_a(x)+*{}_a,$AAainA

As before, we define the $costC(f)$ of a feasible flow $f$ as

$C(f)={\displaystyle \underset{\text{a}\text{i}\text{n}\text{A}}{\overset{?}{}}}{l}_a(f_a)f_a$

In particular, note that the cost function $C$ does not account for the imposed tolls.

We say that the tolls $=({}_a{)}_{\text{a}\text{i}\text{n}\text{A}}$ 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 $(c_a^{}{)}_{\text{a}\text{i}\text{n}\text{A}},$ 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.