Problem $2(20$ points$).$ Let $=(N,(x_i{)}_{\text{i}\text{i}\text{n}\text{N}},(c_i{)}_{\text{i}\text{i}\text{n}\text{N}})$ be a symmetric network conges$-$

tion game. That is$,$ given a directed graph $G=(V,E)$ with source node $s$ and target

node $t,$ every player iinN has strategy set $x_i=P,$ where Psube$2^E$ is the set of

all $($simple$)s,t-$paths in $G.$ Further, assume that the cost functions $(c_e{)}_{\text{e}\text{i}\text{n}\text{E}}$ are non$-$

negative and non$-$decreasing. Let $n=|N|$ and $m=|E|$ be the number of players

and resources, respectively.

Give an algorithm that computes a pure Nash equilibrium of $$ in time polynomial

in $n$ and $m.($Hint: Recall that a minimizer of Rosenthal's potential is a Nash equi$-$

librium.$)$