Can someone explain to me the proof on page 7/20 of the original paper about potential games (https://www.cs.tau.ac.il/~mansour/sem-game-02-03/monderer-potential-96.pdf)?
It is about why two potentials of a game G can only differ by a constant.
5
1 Answer
$\begingroup$
$\endgroup$
3
This is what it looks like to me: to get $H(y)$, we change strategy profile $z$ into $y$ one player at a time, summing the changes in utility. For any exact potential $P$ (which is actually equation 2.2 with weights $1$), each change in utility is equal to $P(a_{i-1}) - P(a_{i})$. This is a telescoping sum, so $H(y) = P(y) - P(z)$. This didn't depend on which exact potential $P$ we chose, so $P_1(y) - P_1(z) = P_2(y) - P_2(z)$ for all $y$. In other words $P_1(y) = P_2(y) + c$ where $c = P_1(z) - P_2(z)$.
-
$\begingroup$ How do you conclude from P2(y) - P2(z) to P1(y) = P2(y) + c? What I mean is - how did you move from z and y to just y? $\endgroup$ Commented Oct 29, 2021 at 12:20
-
2$\begingroup$ Rearrange $P_1(y) - P_1(z) = P_2(y) - P_2(z)$ as $P_1(y) - P_2(y) = P_1(z) - P_2(z)$. Choose some arbitrary $y$ and call $c = P_1(y) - P_2(y)$. It follows that $P_1(z) - P_2(z) = c$ for every $z$, i.e. $P_1 = P_2 + c$. $\endgroup$– Alex M.Commented Oct 29, 2021 at 12:32
-
$\begingroup$ Ok, I got it now. Thank you so much! $\endgroup$ Commented Oct 29, 2021 at 12:32
HthatP1(y) - P2(y) = c? $\endgroup$