Potential Game

def. Potential Game. A game is a potential game iff there exists a potential function that satisfies the following, for any player $i$ that changes their strategy from $s_i\to s_i^{\prime }$:

$$\underset{\text{Change in Potential}}{\underbrace{\varphi (s_i^{\prime },{\vec{s}}_{-i})-\varphi (s_i,{\vec{s}}_{-i})}}=\underset{\text{Change in Cost}}{\underbrace{c_i(s_i^{\prime },\overrightarrow{s_{-i}})-c_i(s_i,\overrightarrow{s_{-i}})}}$$

def. This function $\Phi (s_i,{\vec{s}}_{-i})$ is a potential function.

• ${\vec{s}}_{-i}$ denotes the strategies of the remaining players.

thm. Potential Games always has a PNE. Namely, for convex potential functions that have a global minima, that minima is the equilibrium.

• This NE is also achievable; let the system run, and it will reach NE (best-response dynamics)
• Every local minimum of the potential function is a NE Intuition. Consider:

1. When a player improves their strategy to reduce their own costs, the potential decreases
2. This repeats until nobody can switch their strategy

An example of potential game analaysis for computing NE is Traffic Routing