I am learning about selfish routing in game theory from Nisan, Roughgarden, Tardos, Vazirani: Algorithmic Game Theory. Cambridge University
Press (2007)
TL;DR
I am struggling to solve exercise 18.4
Now I'm learning about proofing the existence of Nash Equilibrium in atomic selfish routing using a potential method.
I was able to understand completely the following theorem (18.12):
$(G, r, c)$ be an atomic instance in which every traffic amount $r_i$ is equal to a
common positive value $R$. Then $(G, r, c)$ admits at least one equilibrium flow.
The proof is for $R=1$ but it's quite easy to understand how to do it for any fixed integer.
Now, I am trying to prove a more general theorem (exercise 18.4)
First, they make a recall about affine cost functions: a cost function $c_e$ is affine if it has the
form $a_e (x) + b_e$ ; we always assume that $a_e , b_e ≥ 0.$)
Theorem 18.15: Let $(G,r,c)$ be an atomic instance with affine cost functions. Then $(G,r,c)$ admits at least one equilibrium flow. Define potential function as suggested
$\Phi(f)=\underset{e\in E}{\sum}(c_{e}(f_{e})f_{e}+\underset{i\in S_{e}}{\sum}c_{e}(r_{i})r_{i}),$
where $S_{e}$ denotes the set of players that chose a path in $f$ that includes the edge $e$.
The general idea of the proof is to take an optimal solution for $\Phi$, call it $f$ and show that $f$ is NE by contradiction: assume that $f$ is not NE so a player $i$ can deviate his flow by choosing a different path and forming a new flow $f^*$. now, we need to make the difference and show why it is the difference of the potential function and reach a contradiction to $f$ optimality.
I can't get the equations right (from path difference to potential function difference)
Any suggestions? any help will be appreciated