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=A1timesldotstimesAn and payoff functions ui is called an exact potential game if there exists a potential function Phi such that:
forallainAforallai,biinAiPhi(bi,ai)Phi(ai,ai)=ui(bi,ai)ui(ai,ai)



A game is a general (ordinal) potential game if there exists a potential function Phi such that:
forallainAforallai,biinAisgn(Phi(bi,ai)Phi(ai,ai))=sgn(ui(bi,ai)ui(ai,ai))



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 ui and ui respectively, for each player i. For any 0leqpleq1, 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 upi(cdot)=(1p)ui(cdot)+pui(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