4
$\begingroup$

My setting is the following.

I have a sequence of games $\lbrace G_n \rbrace$ in which the strategy space is $S=[0,1]^2$, there are two players $(I=\lbrace 1,2 \rbrace)$, and payoff functions are given by the continuous (no other restrictions so far) functions $U_i^n(x_1,x_2)$ for each player $i=1,2$. That is, each game is defined by $G_n = (U^n, S,I)$.

Now, I know that the payoff functions $U_i^n$ converge pointwise to a (discontinuous) limit $U_i$. I therefore write down the 'limit game' $G = (U,S,I). $ We can write down a correspondence that maps a game to its nash equilibria. Call that correspondence $EQ$, and we define, for a particular game $G_n$, that $EQ(G_n) = \lbrace (s_{n1}^*, s_{n2}^*), (s_{n1}^{**},s_{n2}^{**}) \dots\rbrace $ where the right hand side is the set of (potentially infiite) nash equilibria for the game $G_n$ and, generically, we allow each equilibrium strategy $s_{ni}$ to be a mixed strategy. That is, a probability measure over $[0,1].$

I then analysed the limit game, and have found a unique mixed strategy nash equilibria in that game. That is, $EQ(G) = \lbrace (s_1^*, s_2^*) \rbrace$.

I do not have closed form solutions for the equilibria, $\lbrace (s_{n1}^*, s_{n2}^*), (s_{n1}^{**},s_{n2}^{**}) \dots\rbrace $, of the games in the sequence $\lbrace G_n \rbrace$. Naturally, though, I would like to say something about how the equilibria converge to the equilibrium of the limit game.

My questions are (to start) as follows.

  • Given the pointwise convergence of payoff functions $U^n \rightarrow U$, in what sense can I say the games $\lbrace G_n \rbrace $ converge to the limit game $G$?
  • What conditions do I need on the equilibrium correspondence $EQ$ so that I can say something about the convergence of the equilibrium strategies? That is, am I able, with some argument, to establish that there exists a sequence of equilibria that converges to the equilibrium of the limit game in some sense. That is, $\lbrace (s_{n1}^*, s_{n2}^*)\rbrace_{n=1}^\infty \rightarrow \lbrace (s_{1}^*, s_{2}^*)\rbrace$, perhaps in the weak sense, perhaps in the strong sense, or perhaps in some other sense.

Any help or references are greatly appreciated.

Edit: clarified the notation and question.

$\endgroup$
  • $\begingroup$ There is some inconsistency in your notation, in particular, you use the same notation for a sequence of equilibria as for a sequence of games. Also, please clarify what uniform convergence of equilibria means. $\endgroup$ – Michael Greinecker Mar 21 '18 at 9:45
  • $\begingroup$ Hi Michael, I have rewritten my question to hopefully make it clearer. Thinking of the (mixed strategy) equilibiria as probability density functions, they can converge uniformly in the normal sense of functional uniform convergence. Or, thinking of the equilibria as measures, they can converge in the weak sense $(\int_{[0,1]} f d(s_n) \rightarrow \int_{[0,1]} f d(s)$ for every nicely behaved $f$). I have used the latter interpretation, but if its better to think of mixed strategies as p.d.f's, then I can change it. $\endgroup$ – user434180 Mar 21 '18 at 10:24
  • $\begingroup$ In general, there is no reason why there should exist Nash equilibria in mixed strategies that admit a density with respect to some distribution, so weak convergence would be more natural. In that case, the space of mixed strategy-profiles is compact and you will obtain a convergent subsequence. Maybe you can manually show that such a convergent sequence must converge to your candidate limit equilibrium. $\endgroup$ – Michael Greinecker Mar 21 '18 at 13:22
  • $\begingroup$ Thanks Michael. Given the uniqueness of the equilibrium of the limit game, can I not conclude that the convergent subsequence converges exactly to that limit? I do not exactly see what you mean by 'manually show'. As in, derive actual analytic expressions for the mixed strategy equilibria and check convergence? Because I have spent much time on that and it doesn't seem doable. Hence I am trying to give a more abstract argument. Thanks again for your help. $\endgroup$ – user434180 Mar 21 '18 at 13:30
  • 1
    $\begingroup$ The equilibrium correspondence will be upper hemicontinuous if you index games by the continuous payoff functions with the topology of uniform convergence (using the $\sup$-norm, basically). I could write down a prove I you want. But your convergence is not to a continuous function and is pointwise, not uniform. Pointwise convergence is much less well-behaved. $\endgroup$ – Michael Greinecker Mar 22 '18 at 5:22
2
$\begingroup$

This is just an extended remark:

Let $\Delta$ be the space of Borel probability measures on $[0,1]$. An equilibrium can be represented as an element of $\Delta^2=\Delta\times\Delta$. A two player game with continuous payoff-functions with action spaces $[0,1]$ can be viewed as an element of $C[0,1]^2\times C[0,1]^2$, where $C[0,1]^2$ is the space of continuous functions (here representing payoff functions) from $[0,1]^2=[0,1]\times[0,1]$ to the reals, endowed with the topology of uniform convergence, given by the $\sup$-norm $\|\cdot\|_\infty$ defined by $$\|f\|_\infty=\sup_{x\in [0,1]} |f(x)|=\max_{x\in [0,1]} |f(x)|.$$ One defines $C[0,1]$ similarly.

There is also a well-behaved metrizable compact topology on $\Delta$, the topology of weak convergence (or weak*-topology); the coarsest topology such that the function $\mu\mapsto\int f~\mathrm d\mu$ is continuous for each $f\in C[0,1]$. In this context, convergence in this topology is convergence of cumulative distribution functions at continuity points. We let $\Delta^*$ be the set of Borel probability measures on $[0,1]\times [0,1]$, similarly endowed with the topology of weak convergence.

We can then define an equilibrium correspondence $$\eta:C[0,1]^2\times C[0,1]^2\to 2^{\Delta\times\Delta}$$ such that $\eta(v,u)$ is the set of equilibria given the payoff-functions $u$ and $v$. The correspondence has nonempty values by a theorem of Glicksberg. Since $\Delta\times\Delta$ is compact, we can show that $\eta$ is upper hemicontinuous by showing it has a closed graph. The function $p:\Delta\times\Delta\to\Delta^*$ that maps mixed strategies to their independent product is continuous (see Billingsley's book on weak convergence). It follows, using a bit of analysis, that the "expected payoff"-function $k_i:\Delta\times\Delta\times C[0,1]^2\to\mathbb{R}$ is continuous for $i=1,2$. Now for each $\mu\in\Delta$, let $$E_\mu^1 \{(v,u,\nu,\tau)\in \Delta\times\Delta\times C[0,1]^2\times C[0,1]^2\mid k_1(\nu,\tau,v)\geq k_1(\mu,\tau,v)\}$$ and $$E_\mu^2 \{(v,u,\nu,\tau)\in \Delta\times\Delta\times C[0,1]^2\times C[0,1]^2\mid k_2(\nu,\tau,u)\geq k_1(\nu,\mu,u)\}.$$ Each of these sets is closed and the graph of $\eta$ is simply $$\bigcap_{\mu\in\Delta}E_\mu^1\cap \bigcap_{\mu\in\Delta}E_\mu^2,$$ a closed set, so $\eta$ is upper hemicontinuous.

Now this doesn't tell us anything about what happens if payoff functions converge pointwise and not uniformly!!! The only useful information is that strategy spaces are compact, so there will still be a convergent subsequence. If you can show that this subsequence must converge to your candidate equilibrium- this will require making use of the details of the game, you should be good to go.

$\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.