# Weakly acyclic games in game theory

I read that weakly acyclic games are more general than potential games. Potential games are said to have a finite improvement property where each player's payoff function is aligned with a potential function at each stage. Hence, every move a player makes using a best-response strategy increases his payoff and the potential function. However, for weakly acyclic games, it is defined such that only at least one player's payoff function is aligned with the potential function at each stage. However, it doesn't have the finite improvement property.

The mathematical representation of a potential game is:

$$u_i(a_i,a_{-i})-u_i(\hat a_i,a_{-i}) = \phi(a_i,a_{-i})-\phi(\hat a_i,a_{-i}) \forall i \in \mathcal I, \forall a_{-i} \in \mathcal A_{-i}, \forall (a_i,\hat a_i) \in \mathcal A_i \times \mathcal A_i$$

while for a weakly acyclic game:

$$\exists i \in \mathcal I$$, such that $$u_i(a_i,a_{-i})-u_i(\hat a_i,a_{-i}) >0$$ and $$\phi(a_i,a_{-i})-\phi(\hat a_i,a_{-i}) >0, \forall a_{-i} \in \mathcal A_{-i}, \forall (a_i,\hat a_i) \in \mathcal A_i \times \mathcal A_i$$

where $$i$$ is a player in the player set $$\mathcal I$$ while $$a_i,\hat a_i \in$$ $$\mathcal A_i$$ represents a player's action and its action set. $$u_i$$ is the player's payoff and $$\phi$$ is the potential function. $$a_{-i} \in \mathcal A_{-i}$$ represents the actions and the action set, respectively, chosen by the other players not including player $$i$$.

Potential game (left) and Weakly acyclic game (right) The figure above shows a potential game and weakly acyclic game compared side-by-side. There are 3 players with 2 actions {0, 1}. The nodes represent an action profile where the numbers inside are the actions chosen by the three players and the directed links represent an improvement of the payoff function of the player who chose an action and also the potential function. A movement from one node to the next is considered a stage of the game.

My question is: From the weakly acyclic game figure above, am I correct to assume that the loop (represented by the red directed links) only shows an improvement of a player's payoff but that the player whose payoff improved may not be the player whose payoff function is aligned with the potential function?

If my question isn't clear, please let me know so I can make it clearer. Thank you.

• How should one read the graphs? On the right hand side, there is a red dotted arrow pointing from a circle inside of which it says "000" to another circle, in side of which it also says "000," You say that the directed links represent an improvement of the payoff function. But these two circles represent the same list of actions. How can the payoff increase? I must be misunderstanding the graphs. – TMB Feb 2 '15 at 1:02
• Oh goodness. I am sorry for that. I have updated the graph. Thank you for your reply. – Nikki Mino Feb 3 '15 at 0:36

It cannot be that the deviations indicated by dotted red arrows increase not only the deviating player's payoff but also the value of the potential function. Because, if the value of the potential function were increased along each deviation, then we would have to have: $\phi(100)<\phi(110)<\phi(010)<\phi(000)<\phi(100)$, but by transitivity that would imply $\phi(100)<\phi(100)$, which can't be true. The same argument applies whenever a sequence of deviations forms a loop.
• It seems to me that for weakly acyclic games, the deviating player's payoff may not be aligned to the potential function since a loop exists but he/she increases his/her payoff anyway. Based on $\exists i \in \mathcal I$, such that $u_i(a_i,a_{-i})-u_i(\hat a_i,a_{-i}) >0$ and $\phi(a_i,a_{-i})-\phi(\hat a_i,a_{-i}) >0, \forall a_{-i} \in \mathcal A_{-i}, \forall (a_i,\hat a_i) \in \mathcal A_i \times \mathcal A_i$ there should be one at least one player whose payoff function is aligned with the potential function representing the game but didn't deviate. – Nikki Mino Feb 4 '15 at 2:50