How to find potential function for any game?

342 Views Asked by At

I am studying Tim Roughgarden's lecture notes on algorithmic game theory. In chapter 13, he introduces the concept of potential function $$\Phi(f)=\sum_{e\in E}\sum_{i=1}^{f_e}c_e(i)$$

In the context of congestion game, I understand how to calculate it. For example, given 3 edges with different cost functions $c_e(i)$ and flows $f$ along each edge (as shown in the picture below)

enter image description here

The potential function is simply like this (correct me if I am wrong) $$\Phi(f)=c_1(1)+c_1(2)+c_1(3)+c_2(1)+c_2(2)+c_3(1)$$

However, when I further check Wikipedia, they mention without explanation that the potential function for the Battle of the sexes game with cost function $u_i(s_i, s_j) = b_i s_i + w s_i s_j$ is

$$\Phi = b_1 s_1 + b_2 s_2 + w s_1 s_2$$

How do people come up with different potential functions for different game settings?

I wonder if there is a general method for finding the potential function? Or it is just randomly trying things out and discover it?