Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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_{a\in 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_{a\in 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?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

No, the set of ordinal potential games is not convex. I will think about an example, but it follows from a little fact that I've yet to get around to publishing:

Theorem: Any convex set of games strictly containing the exact potential games contains a game with no pure Nash equilibrium.

In particular, since every ordinal potential game has a pure Nash equilibrium, convexity of the set thereof would contradict this theorem.

EDIT: Bimatrix games A and B below are ordinal potential games, but the average of these two games is the zero-sum game "matching pennies" which obviously has no pure Nash equilibrium and so is not an ordinal potential game.

Game A:                     Potential A:
 (4,-1)    (0,1)              3    4
(-2,1)    (-2,-1)             2    1

Game B:                     Potential B:
(-2,-1)   (-2,1)              1    2
 (0,1)     (4,-1)             4    3

Matching pennies:           (No potential)
 (1,-1)   (-1,1)
(-1,1)     (1,-1)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.