Consider a puzzle as illustrated below:
$$
A=\left[\begin{array}{cccc}
0 & 1 & 0 & 0\\
0 & 2 & 0 & 0\\
2 & 0 & 0 & 0\\
0 & 0 & 0 &3
\end{array}\right]
$$
where a $0$ indicates that the box in initially empty.
Model the puzzle as a game with
the following specifications:
Boxes with a $0$ are modeled as players in game, i.e., there are $12$ players in the above
game.
Actions of each player $i \in N$ is $\mathcal{A}_i=\{1,2,3,4\}$.
Utility of each player $i \in N$ is $$U_i(a_i,a_{-i})=-(\text{# reps in row})-(\text{# reps in col})-(\text{# reps in block}),$$ where reps means repetitions.
Note that a game is an exact potential game if there is a function $\phi: \mathcal{A}\rightarrow \mathbb{R}$ such that $\forall a_{-i} \in \mathcal{A_{-i}}, \forall {a^{'}}_{i}, {a^{''}}_{i}$
$$\phi({a^{'}}_{i}),a_{-i})-\phi({a^{''}}_{i}),a_{-i})=\mu_{i}({a^{'}}_{i}),a_{-i})-\mu_{i}({a^{''}}_{i}),a_{-i})$$.
(Note $A_{-i}$ simply denotes the actions of all players except $i$ thus $(a_i,a_{-i})$ encompasses actions of all players)
Solution says function: $\phi(a)=\frac{1}{2} \sum_{i \in N} U_{i}(a)$ is a potential function for the game.
I, however, cannot convince myself that this potential function is correct. I have tried many examples as below:
Suppose consider puzzle:
A=$$
A=\left[\begin{array}{cccc}
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 &0
\end{array}\right]
$$
Thus, there are 16 players in the above game.
Note I am calling Player 1's corresponding matrix entry $(1,1)$, Player 2: (1,2), Player 3: (1,3), Player 4:(1,4), Player 5:(2,1), Player 6: (2,2), Player 7: (2,3), Player 8: (2,4), Player 9:(3,1), Player 10: (3,2), Player 11: (3,3), Player 12: (3,4), Player 13: (4,1), Player 14: (4,2), Player 15: (4,3), Player 16: (4,4).
Suppose $1=a_{1}=a_{2}=a_{3}=a_{4}=……a_{15}=a_{16}$.
All players choose number the number 1.
Then we have that payoff for Player 1:
$$U_1(1,1,1,1,……1,1)=-3-3-3=-9$$ as the number 1 is repeated 3 times in Player 1's row, 3 times in Player 1's column, and 3 times in Player 1's block.
Suppose instead that Player 1 chooses number 2, but all other players choose number 1:$$U_1(2,1,1,1,……1,1)=-2-2-2=-6$$ as the number 1 is repeated 2 times in Player 1's row, 2 times in Player 1's column, and 2 times in Player 1's block.
Thus, we see the difference in payoffs is -3.
However, we now calculate the potential function:
Clearly $$\forall i, U_i(1,1,1,1,……1,1)=-3-3-3=-9$$
Thus
$\phi(1,1,1……1)=\frac{1}{2}(16\times-9)=-72$
However, calculating the payoffs for $a'=(2,1,1,1,1…1,1)$ is more complicated:
\begin{align*}
U_1(2,1,….1)=-2-2-2=-6 \\
U_2(2,1,….1)=-2-3-2=-7\\
U_3(2,1,….1)=-2-3-3=-8\\
U_4(2,1,….1)=-2-3-3=-8\\
U_5(2,1,….1)=-3-2-2=-7\\
U_6(2,1,….1)=-3-3-2=-8\\
U_7(2,1,….1)=-3-3-3=-9\\
U_8(2,1,….1)=-3-3-3=-9\\
U_9(2,1,….1)=-3-2-3=-8\\
U_{10}(2,1,….1)=-3-3-3=-9\\
U_{11}(2,1,….1)=-3-3-3=-9\\
U_{12}(2,1,….1)=-3-3-3=-9\\
U_{13}(2,1,….1)=-3-2-3=-8\\
U_{14}(2,1,….1)=-3-3-3=-9\\
U_{15}(2,1,….1)=-3-3-3=-9\\
U_{16}(2,1,….1)=-3-3-3=-9\\
\end{align*}
Thus $\phi(2,1,….1)=\frac{1}{2} \sum_{i \in N} U_{i}(2,1,…1)=\frac{1}{2}(-132)=-66$
Thus, it is not working for me as the difference in the payoffs is $-9-(-6)=-3$ but the difference in the potential functions is: $-72-(-66)=-6$
However, these quantities are supposed to be equal for $\phi$ to be a potential function. Thus, is $\phi(a)=\frac{1}{2} \sum_{i \in N} U_{i}(a)$ not a potential function for the game, despite it being stated as so or am I making a mistake in my calculations or interpretations of anything? Thank you.
Best Answer
The formulation in the problem statement is rather unclear, but from the context of the potential it seems that what they mean by “# reps” is the number of times the player’s number is repeated by other players. So if the player switches to $2$, their payoff goes to $0$ because there are no other $2$s in the row, column or block. The idea behind the potential function and the factor $\frac12$ in it is that the sum of all payoffs counts each pair of matching numbers twice, but that only works if we interpret ‘# reps” accordingly.