4
$\begingroup$

What happens to the Nash equilibria and minimax values of a strategic game, when we take its payoff table and modify all payoffs by raising them to the 3rd power?

My conjecture is that it depends:

  • If, in the original game, all Nash equilibria and minimax points are attained using pure strategies alone - then a positive monotone transformation should have no effect on them. When everything is pure (deterministic), the utility function is ordinal and it is robust to monotone transformation.
  • But if, in the original game, some Nash equilibria / minimax points are attained using mixed strategies - then a non-linear transformation might change them substantially.

For example, in the following zero-sum game:

4 0
0 4
3 3 

The maxinim value is 3 and a maximin strategy for the row player is selecting the bottom row (the column player can guarantee at most 3 by mixing the two columns with equal probability).

But if we raise to the 3rd power:

64 00
00 64
27 27 

Now the minimax value is 32, and a maximin strategy for the row player is mixing the two top rows.

So my question is: In what conditions does a positive monotone transformation on a game's payoff not change its maximin and Nash equilibrium strategies?

$\endgroup$
  • 1
    $\begingroup$ I don't quite understand your question (the last sentence in bold). Do you want to ask, "under what conditions does every positive monotone transformation not change..."? Or, are you looking for "circumstances" involving some relationship between the transformation and the original game... $\endgroup$ – usul Sep 8 '15 at 2:04
  • $\begingroup$ Erel what is the source of your quote? $\endgroup$ – Giskard Sep 8 '15 at 7:38
  • $\begingroup$ @denesp I didn't intend to quote anything - just to emphasize the question. $\endgroup$ – Erel Segal-Halevi Sep 8 '15 at 8:04
3
$\begingroup$

I interpret the question as follows: Suppose we have a finite normal form game (with finitely many players and a finite set of actions for each outcomes). For simplicity, assume a strict ordering of payoffs for each player. That is, the payoff matrix of each player does not contain any identical elements.

We furthermore need to be clear what is meant by a positive monotone transformation of the payoffs. The first option is to transform all payoffs by the same increasing function. The second option is to apply positive monotone transformations to the payoffs of each player separately. I interpret the question as meaning the latter, but the results should also go through for the former.

We want to characterize all Nash equilibria such that in any game resulting from an arbitrary monotone transformation of the payoffs the same strategies are also a Nash equilibrium. Call any Nash equilibrium which fulfills this property "robust to monotone transformations".

With your conjecture, you have pretty much answered the question. The set of Nash equilibria robust to monotone transformations is the set of pure strategy Nash equilibria. Here is a quick sketch of why this is so:

Suppose player i plays a mixed strategy. In this case, the player must be indifferent between all pure strategies in the support of the mixed strategy. This indifference is given by an equation which is a linear combination of payoffs. Since none of these payoffs are equal, we can change any payoff by a small amount to break the indifference. It follows that mixed strategy equilibria are not robust to monotone transformations.

We still need to show that all pure strategy equilibria are robust to monotone transformations. A pure strategy equilibrium is given if all players play their best responses to all other players' strategies. This involves maximizing over a finite set of actions. Given the other players' actions, the actions of player i are in one-to-one correspondence with a set of payoffs. Since the monotone transformation of the payoffs does not change their relative ordering, the set of best responses does not change. Since this holds for every player, the pure strategy Nash equilibrium is robust to monotone transformations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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