Saturday, 3 April 2010

Is the convex combination of two potential games a potential game?

My question: is the set of potential games closed under convex combinations?



An n player game with action set $A = A_1 times ldots times A_n$ and payoff functions $u_i$ is called an exact potential game if there exists a potential function $Phi$ such that:
$$forall_{ain A} forall_{a_{i},b_{i}in A_{i}} Phi(b_{i},a_{-i})-Phi(a_{i},a_{-i}) = u_{i}(b_{i},a_{-i})-u_{i}(a_{i},a_{-i})$$



A game is a general (ordinal) potential game if there exists a potential function $Phi$ such that:
$$forall_{ain A} forall_{a_{i},b_{i}in A_{i}} sgn(Phi(b_{i},a_{-i})-Phi(a_{i},a_{-i})) = sgn(u_{i}(b_{i},a_{-i})-u_{i}(a_{i},a_{-i}))$$



Potential games are interesting because they always have pure strategy Nash equilibria: in particular, a sequence of best-responses must eventually converge to one.



Say that we have two games on the same action set, with utility functions $u_i$ and $u'_i$ respectively, for each player $i$. For any $0 leq p leq 1$, there is a convex combination of these two games, again on the same action set, where the utility function for each player $i$ is now $u^p_i(cdot) = (1-p)u_i(cdot) + pu'_i(cdot)$.



Clearly, the convex combination of two exact potential games is also an exact potential game: just take the same convex combination of the two potential functions.



But is it possible to have two (general) potential games such that their convex combination is not a potential game?

No comments:

Post a Comment