EDIT: The key thing that I am wondering about is the linearity of the P2 strategy, not the constancy of P1. (The latter is straightforward.)

Question: Is the following result already known? Or is it a straightforward corollary of some more general principle?

Intuitive version (slightly wrong): In a normal form game, adding a small cost $c$ to a particular action of a player (independently of the action of the opponent) changes the opponent's Nash equilibrium strategy linearly (in the size of $c$) and leaves the player's NE strategy constant.

Formal version: Let $G$ be a two-player normal-form game with actions denoted $i$, $j$ and payoffs $u_1(i,j)$, $u_2(i,j)$. For a fixed action $i_0$ of P1, denote by $G'_c$ the game that is identical to $G$, except $u'_1(i_0, j) := u_1(i_0, j) - c$. Then there is a finite set of exception points $-\infty = e_0 < \dots < e_n = \infty$ such that for every $c_0 \in (e_k, e_{k+1})$ and $\sigma^{c_0} \in \textrm{NE}(G'_{c_0})$, there is a linear mapping $c \in [e_k, e_{k+1}] \mapsto \sigma^c_2$ such that $(\sigma^{c_0}_1, \sigma^c_2) \in \textrm{NE}(G'_c)$ (and the value for $c = c_0$ coincides with $\sigma^{c_0}_2$).

Comments: (1) I know how to prove the statement "from scratch" using the LP formulation of NE (and the notion of basic solutions). But I was wondering whether there is perhaps a more general result that this follows from. (2) It seems something similar holds if we only change a single cell in the payoff matrix. (This will cause a linear change in the relative weights of probabilities in $\sigma_2^{(\, \cdot \, )}$. IE, no longer linear, but still quite simple.)

  • 1
    $\begingroup$ I'm not sure the result is known in this form, but the "phenomenon" is; see Section B in this paper: stat.berkeley.edu/~aldous/157/Papers/goeree.pdf $\endgroup$ Dec 5, 2022 at 23:08
  • $\begingroup$ I should have clarified: The key thing I am wondering about is the linearity of P2 strategy (not the constancy of P1 strategy). (Apologies there, the mistake was in my phrasing. And thanks a lot, this result is useful to know nevertheless.) $\endgroup$ Dec 6, 2022 at 2:15
  • $\begingroup$ The linearity is not that complicated either, the only messy part is dealing with corner cases in which a strategy is played with probability zero. Otherwise it follows directly from the condition that the other players must be indifferent between all pure strategies in the support of a mixed best response. $\endgroup$ Dec 6, 2022 at 9:50
  • $\begingroup$ Just flaggin that I don't see this as resolved yet. (The linearity seemed pretty non-obvious to me. The basic idea is simple, but my current proof --- which involves dealing with the "messy cases" --- is 1.5 pages. Surely that isn't optimal, but I would count that as decently complicated.) $\endgroup$ Dec 8, 2022 at 19:32
  • 1
    $\begingroup$ You are right, I should have chosen my words a bit more carefully. I do think the theorem is somewhat unsurprising in that this is what you get whenever you calculate equilibria in "practice." Of course, this does not give a direct handle on how to deal with all cases in a systematic fashion. $\endgroup$ Dec 9, 2022 at 1:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.