A Note on Mixed-Nash Implementation

Abstract

This note considers (complete information) Nash-implementation when mixed strategies are properly accounted for and the outcome space is infinite. We first construct an example in which preferences over lotteries fail the Archemedian axiom and show that, even under the classical sufficient conditions for implementation, the canonical mechanism for implementation fails: there exists a mixed-Nash equilibrium in which the outcome is undesirable with probability one. We then prove that the canonical mechanism works if Bernoulli utilities are bounded.

1 Setup

Our setup and notation are standard in implementation theory; the reader is referred to Maskin (1999) or Maskin and Sjostrom (2002, MS hereafter) for details. The environment is a tuple $(A,N,\mathrm{\Theta })$, where $A$ is a set of outcomes, $N:=\{1,\mathrm{\dots },n\}$ is a finite set of agents/players, and $\mathrm{\Theta }$ is a set of possible states of the world. $A$ and $\mathrm{\Theta }$ are arbitrary topological spaces. Throughout, we treat any topological space, $X$, as a measurable space with its Borel sigma-field and restrict our attention to the set of Borel probability measures, denoted $\mathrm{\Delta }(X)$. Product spaces are endowed with the product topology while the space of Reals is endowed with its usual topology. All functions are assumed to be measurable.

Each agent $i$ has a von Neumann-Morgenstern (vNM) utility function, $u_i:A\times \mathrm{\Theta }\to ℝ$. Agent $i$’s lower contour set at $(a,\theta )\in A\times \mathrm{\Theta }$ is $L_i(a,\theta ):=\{b\in A|u_i(b,\theta )\le u_i(a,\theta )\}$. A social choice rule (SCR) is a function $F:\mathrm{\Theta }\to 2^A\backslash \{\mathrm{\varnothing }\}$, i.e. a non-empty-valued correspondence. A social choice function (SCF) is a single-valued SCR, i.e. a function $f:\mathrm{\Theta }\to A$. A SCR $F$ is (Maskin) monotonic if for all $(a,\theta ,{\theta }^{\prime })\in A\times \mathrm{\Theta }\times \mathrm{\Theta }$ the following is true: if $a\in F(\theta )$ and $L_i(a,\theta )\subseteq L_i(a,{\theta }^{\prime })$ for all $i\in N$, then $a\in F({\theta }^{\prime })$. A SCR $F$ satisfies no veto power (NVP) if for all $(a,j,\theta )\in A\times \mathbb{N}\times \mathrm{\Theta }$: if $u_i(a,\theta )\ge u_i(b,\theta )$ for all $b\in A$ and all $i\ne j$, then $a\in F(\theta )$.

A mechanism (or game form) is a pair $\mathrm{\Gamma }=(M,g)$ where $M={\times }_{i\in N}{M}_i$ and each $M_i$ is the message space for player $i$ and $g:{\times }_{i\in N}{M}_i\to A$ is an outcome function. We denote a message of player $i$ by $m_i$ and a profile of messages by $m$. We assume that each player $i$’s preferences over lotteries are represented by a utility function $U_i:\mathrm{\Delta }(A)\to \overline{ℝ}$, such that for any probability measure, $P\in \mathrm{\Delta }(A)$, $U_i(P)={\int }_A{u}_i(a)𝑑P(a)$. Pure- and mixed-strategy Nash equilibria are defined in the usual way.

A mechanism $\mathrm{\Gamma }$ implements a SCR $F$ in mixed-strategy Nash equilibrium, or simply MSNE-implements $F$, if at each state $\theta$ the game induced by $\mathrm{\Gamma }$ satisfies: (1) for all $a\in F(\theta )$, there exists a pure Nash equilibrium $m^{\ast }$ such that $g(m^{\ast })=a$, and (2) in any mixed-Nash equilibrium $\mu \equiv {({\mu }_i)}_{i\in N}\in {\times }_{i\in N}\mathrm{\Delta }(M_i)$, $\mu (m)>0⟹g(m)\in F(\theta )$. A SCR $F$ is MSNE-implementable if there exists a mechanism which MSNE-implements $F$. Note that we use a slightly less demanding notion than that of Maskin 1999 (p. 25): instead of condition (2) in Maskin, we only require that $g(m)\in F(\theta )$ for all $m$ such that $\mu (m)>0$.  In other words, we ignore outcomes that are undesirable but occur with $0$ probability.  This will make no difference if $A$ is countable.

2 A counter-example to MSNE implementation

The classic result (Maskin, 1999) on Nash implementation says that a monotonic SCR is implementable if it satisfies NVP and there are three or more players. The mechanism in Maskin 1999 works insofar as one considers pure-strategy implementation. MS provide a canonical mechanism to obtain MSNE-implementation.

In this section, we construct an example in which MSNE-implementation cannot be achieved by the mechanism proposed by MS. The reason we focus on the MS mechanism is because we are not aware of any other canonical mechanism in the literature that achieves MSNE-implementation when the MS mechanism cannot. The key feature of our example is a failure of continuity of preferences over lotteries; more precisely, the Archemedian axiom is violated. We suspect, but have not proved, that in our example MSNE-implementation is impossible.

The MS mechanism is as follows (readers should consult MS for details). For each player $i$,

$$M_i=A\times \mathrm{\Theta }\times \{{\alpha }_i\mid {\alpha }_i:A\times \mathrm{\Theta }\to A\text{ and }{\alpha }_i(a,\theta )\in L_i(a,\theta )\text{ for all }(a,\theta )\}\times \mathbb{N}.$$

There are three Rules governing outcomes:

Rule (i): If there is $j\in N$ s.t. $m_i=(a,\theta ,\cdot ,1)$ for all $i\ne j,$ $a\in F(\theta )$ and $n^j=1$, take $g(m)=a$.

Rule (ii): If there is $j\in N$ s.t. $m_i=(a,\theta ,\cdot ,1)$ for all $i\ne j,$ $a\in F(\theta )$ and $n^j>1$ take $g(m)={\alpha }_j(a,\theta )$.

Rule (iii): If neither (i) nor (ii) applies, then $g(m)=a_{i_{\ast }},$where $i_{\ast }=\max \left\{i\mid n^i={\max }_j{n}^j\right\}$ and $m_{i_{\ast }}=(a_{i_{\ast }},\cdot ,\cdot ,\cdot )$

MS assert that, with three or more players, the above mechanism MSNE-implements any monotonic SCR satisfying NVP. MS only provide a formal argument for mixed-Nash equilbria with finite support. We will show through a counter-example that implementation fails when one considers all mixed-Nash equilibria, including those with infinite support. In fact, in our counter-example the MSNE is “bad” in a strong sense because all points in the support yield undesirable outcomes.

The counter-example is as follows. Assume three players $i=1,2,3$. The set of outcomes is $A={\mathbb{N}}^{\ast }\cup \{a\}\cup \{b\}$. There are two states of the world, $\mathrm{\Theta }=\{\theta ,{\theta }^{\prime }\}$. The SCF is defined by $f(\theta )=a$ and $f({\theta }^{\prime })=b$. Fix any probability distribution $\mu \in \mathrm{\Delta }({\mathbb{N}}^{\ast })$ such that $\mu (k)>0$ for all $k\in {\mathbb{N}}^{\ast }$. We now stipulate some conditions on preferences over lotteries. We do this in terms of the Bernoulli utility functions $u_i:A\to ℝ$; recall that preferences over lotteries are represented by $U_i(\cdot )$ such that for any $P\in \mathrm{\Delta }(A)$, $U_i(P)=\sum _{x\in A}P(x)u_i(x)$. Our first requirement is that at state $\theta$:

1. $\forall k\in {\mathbb{N}}^{\ast }:u_1(k,\theta )=u_2(k,\theta )=-\frac{k}{\mu (k)}$.

2. $\forall k\in {\mathbb{N}}^{\ast }:u_3(k,\theta )=u_3(a,\theta )=u_3(b,\theta )$.

3. .

The second requirement is that at state ${\theta }^{\prime }$:

1. $\forall k\in {\mathbb{N}}^{\ast }:u_3(k,{\theta }^{\prime })>u_3(b,{\theta }^{\prime })=u_3(a,{\theta }^{\prime })$

2. $u_1(1,{\theta }^{\prime })\le u_1(b,{\theta }^{\prime })$.

The third requirement is that

$$\arg \underset{x\in A}{\max }{u}_1(x,\theta )=\arg \underset{x\in A}{\max }{u}_2(x,\theta )=\{a\}\text{ and }\arg \underset{x\in A}{\max }{u}_1(x,{\theta }^{\prime })=\arg \underset{x\in A}{\max }{u}_2(x,{\theta }^{\prime })=\{b\}.$$

This condition ensures that $f$ satisfies NVP. Note that the $f$ is Maskin-monotonic because of the following two observations:

• $u_3(k,\theta )=u_3(a,\theta )$and $u_3(k,{\theta }^{\prime })>u_3(a,{\theta }^{\prime })$;

• $u_1(1,{\theta }^{\prime })\le u_1(b,{\theta }^{\prime })$ and .

Now consider MS’s mechanism and assume the true state is $\theta$. Consider the following profile of mixed strategies: for $i=1,2:{\mu }_i$is such that ${\mu }_i\left(({\theta }^{\prime },b,{\alpha }_i(\cdot ,\cdot ),1)\right)=1$, while ${\mu }_3\left(({\theta }^{\prime },b_k,{\alpha }_3(\cdot ,\cdot ),k)\right)=\mu (k)$ where ${\alpha }_i(\cdot ,\cdot )\in L_i(\cdot ,\cdot )$ satisfies ${\alpha }_i(b,{\theta }^{\prime })\equiv b$ for all $i=1,2,3$. In addition, $b_1=b$ and for $k>1:b_k=k$. So in this profile, players 1 and 2 are playing pure strategies and claiming that the state is ${\theta }^{\prime }$, although the true state is $\theta$, and requesting outcome $b\ne f(\theta )$; player 3 is playing a mixed strategy where he always claims the state is ${\theta }^{\prime }$, but only puts probability $\mu (1)$ on the pure strategy that $1$ and $2$ are playing.  We will argue that this profile is an MSNE at $\theta$.

Obviously, player $3$ has no incentive to deviate (he is indifferent between any outcome). Consider player $i=1,2$. Note that if player $i$ sticks to the equilibrium strategy, then with probability $\mu (1)$, we fall into Rule (i) while with probability $1-\mu (1)$ we fall into Rule (ii). When we fall into Rule (ii), the outcome is $b$ because of the specification of player 3’s proposed function ${\alpha }_3(\cdot ,\cdot )$. Hence, $i$’s expected payoff is

$$\mu (1)u_i(b,\theta )+\sum _{k=2}^{\mathrm{\infty }}\mu (k)\times u_i(b,\theta )=u_i(b,\theta ).$$

If player $i$ deviates to $m_i^{\prime }=(\widehat{\theta },\widehat{b},\widehat{\alpha },\widehat{k})\ne ({\theta }^{\prime },b,\alpha ,1)$, with probability ${\sum }_{k=\widehat{k}+1}^{\mathrm{\infty }}\mu (k)$ we fall into Rule (iii) and player $3$ is the “dictator” who chooses outcome $b_k=k$.  Hence $i$’s expected payoff from the deviation is bounded from above by

${\displaystyle \sum _{k=1}^{\widehat{k}}}\mu (k)\underset{c\in A}{\max }{u}_i(c,\theta )+{\displaystyle \sum _{k=\widehat{k}+1}^{\mathrm{\infty }}}\mu (k)\times u_i(k,\theta )={\displaystyle \sum _{k=1}^{\widehat{k}}}\mu (k)u_i(a,\theta )+{\displaystyle \sum _{k=\widehat{k}+1}^{\mathrm{\infty }}}\mu (k)\times \left(-{\displaystyle \frac{k}{\mu (k)}}\right)=-\mathrm{\infty }.$

So player $i$ has no incentive to deviate, proving that the mixed strategy profile is indeed an equilibrium.

Note in addition that $m\in Supp(\mu )\Rightarrow g(m)=b\ne a=f(\theta )$, hence any point in the support of $\mu$ yields an undesirable outcome at $\theta$.

Remark 1.

The example uses quite crucially a representation of preferences where the Bernoulli utility function $u_i$ for $i=1,2$ is unbounded below (at state $\theta$).  Thus, these agents’ preferences over lotteries do not satisfy the Archimedean Axiom. Note that this is generally the case in implementation theory when the outcome space is augmented with transfers that are unbounded and agents have quasi-linear utilities in the transfers. As we will show below, unboundedness of the Bernoulli utilities is necessary for failure of MSNE-implementation.

3 Bounded utilities are sufficient for MSNE implementation

In this section, we prove that if the Bernoulli utilities are bounded, then the MS mechanisms achieves MSNE implementation.

Assumption 1.

For any $i$ and any $\theta$, there exists $M\ge 0$ such that $M\ge u_i(\cdot ,\theta )\ge -M$.

Note that this Assumption was violated by the counter-example above.

Remark 2.

The assumption is trivially satisfied if the outcome space is finite.  The assumption is also satisfied if one requires that preferences over lotteries satisfy the Archimedean Axiom (and don’t restrict the space of lotteries), given the vNM representation.

Theorem 1.

Assume $n\ge 3$. Under Assumption 1, any monotonic SCR satisfying NVP is MSNE-implementable.

The rest of the section is devoted to the proof of this Theorem. It is easy to see, as usual, that “truthful messages” form a desirable pure Nash equilibrium, so we will only prove that there are no undesirable mixed equilibria.  Let $\mu \equiv {({\mu }_i)}_{i\in N}$ be a (mixed) Nash equilibrium when the true state is ${\theta }^{\prime }$, and fix any realization $m^{\ast }\equiv {(m_i^{\ast })}_{i\in N}$such that $\mu (m^{\ast })>0$.  We must show that $g(m^{\ast })\in F({\theta }^{\prime })$.

Suppose first that $m^{\ast }$ is a realization such that there is $j$ for which

$$\text{for all }i\ne j:m_i^{\ast }=(a,\theta ,\cdot ,1)\text{, }a\in F(\theta )\text{ while }{n}^j=1$$

but that the profile $\theta$ differs from the true profile that is ${\theta }^{\prime }$. From Rule (i), the equilibrium outcome is $a\in F(\theta )$. For any player $i$, consider a sequence of ${\{b_i^k\}}_{k=1}^{\mathrm{\infty }}$ such that ${lim}_{k\to \mathrm{\infty }}{u}_i(b_i^k,{\theta }^{\prime })=\underset{x\in A}{sup}{u}_i(x,{\theta }^{\prime })$. Now imagine that player $i$ plays $m_i^k=(b_i^k,\theta ,{\alpha }_i^k(\cdot ,\cdot ),k)$ where ${lim}_{k\to \mathrm{\infty }}{u}_i({\alpha }_i^k(\tilde{a},\tilde{\theta }),{\theta }^{\prime })=\underset{x\in L_i(\tilde{a},\tilde{\theta })}{sup}{u}_i(x,{\theta }^{\prime })$ for all $(\tilde{a},\tilde{\theta })\in A\times \mathrm{\Theta }$. In the sequel, we show that if for some $b\in L_i(a,\theta )$, we have $u_i(b,{\theta }^{\prime })>u_i(a,{\theta }^{\prime }),$ then, for $k$ large enough (and under Assumption $1$ made above) player $i$ is better off using $m_i^k$ rather than $m_i^{\ast }$ against ${\mu }_{-i}$, which contradicts the assumption that $\mu$ is a Nash equilibrium. We conclude that

$$\text{for all }i\text{, }{L}_i(a,\theta )\subseteq L_i(a,{\theta }^{\prime }).$$

Hence, since $F$ is monotonic and $a\in F(\theta )$, we have $a\in F({\theta }^{\prime })$ as required.

So let us assume that for some $b\in L_i(a,\theta )$, we have $u_i(b,{\theta }^{\prime })>u_i(a,{\theta }^{\prime }),$and let us show that for $k$ large enough, player $i$ is better off using $m_i^k$ rather than $m_i^{\ast }$ against ${\mu }_{-i}$.

Claim 1.

${lim}_{k\to \mathrm{\infty }}{u}_i(g(m_i^k,m_{-i}^{\ast }),{\theta }^{\prime })>u_i(g(m_i^{\ast },m_{-i}^{\ast }),{\theta }^{\prime })$.

Proof.

Either $(m_i^k,m_{-i}^{\ast })$ falls into Rule (ii) for all $k>1$, or it falls into Rule (iii) for all $k>1$. If $(m_i^k,m_{-i}^{\ast })$ falls into Rule (ii) for all $k>1$, it follows that

$\underset{k\to \mathrm{\infty }}{lim}{u}_i(g(m_i^k,m_{-i}^{\ast }),{\theta }^{\prime })$ $=$ $\underset{k\to \mathrm{\infty }}{lim}{u}_i({\alpha }_i^k(a,\theta ),{\theta }^{\prime })$

$=$ $\underset{x\in L_i(a,\theta )}{sup}{u}_i(x,{\theta }^{\prime })\ge u_i(b,{\theta }^{\prime })>u_i(a,{\theta }^{\prime })=u_i(g(m_i^{\ast },m_{-i}^{\ast }),{\theta }^{\prime })=a$

where the first inequality comes from the fact that $b\in L_i(a,\theta )$. On the other hand, if $(m_i^k,m_{-i}^{\ast })$ falls into Rule (iii) for all $k>1$, it follows that

$$\underset{k\to \mathrm{\infty }}{lim}{u}_i(g(m_i^k,{\widehat{s}}_{-i}),{\theta }^{\prime })=\underset{x\in A}{sup}{u}_i(x,{\theta }^{\prime })\ge u_i(b,{\theta }^{\prime })>u_i(a,{\theta }^{\prime })=u_i(g(m_i^{\ast },m_{-i}^{\ast }),{\theta }^{\prime })\text{.}$$

Claim 2.

For any realization ${\widehat{m}}_{-i}$ of ${\mu }_{-i}$, ${\{u_i(g(m_i^k,{\widehat{m}}_{-i}),{\theta }^{\prime })\}}_{k>1}$ converges and ${lim}_{k\to \mathrm{\infty }}{u}_i(g(m_i^k,{\widehat{m}}_{-i}),{\theta }^{\prime })\ge u_i(g(m_i^{\ast },{\widehat{m}}_{-i}),{\theta }^{\prime })$.

Proof.

Fix any ${\widehat{m}}_{-i}$.  Consider the case where $(m_i^{\ast },{\widehat{m}}_{-i})$ falls into Rule (i), and let $g(m_i^{\ast },{\widehat{m}}_{-i})=\widehat{a}$. In such a case, for $k>1$, $(m_i^k,{\widehat{m}}_{-i})$ falls either into Rule (ii) or into Rule (iii). If for some $k>1$, $(m_i^k,{\widehat{m}}_{-i})$ falls into Rule (ii), we must have that for all $k>1$, $(m_i^k,{\widehat{m}}_{-i})$ falls into Rule (ii) and hence, $g(m_i^k,{\widehat{m}}_{-i})={\alpha }_i^k(\widehat{a},\widehat{\theta })$ for some $\widehat{\theta }$ s.t. $\widehat{a}\in F(\widehat{\theta })$. By definition of ${\alpha }_i^k(\cdot ,\cdot )$,

$$\underset{k\to \mathrm{\infty }}{lim}{u}_i(g(m_i^k,{\widehat{m}}_{-i}),{\theta }^{\prime })=\underset{x\in L_i(\widehat{a},\widehat{\theta })}{sup}{u}_i(x,{\theta }^{\prime })\ge u_i(\widehat{a},{\theta }^{\prime })=u_i(g(m_i^{\ast },{\widehat{m}}_{-i}),{\theta }^{\prime }).$$

Next, suppose that for some $k>1$, $(m_i^k,{\widehat{m}}_{-i})$ falls into Rule (iii). Then we must have that for all $k>1$, $(m_i^k,{\widehat{m}}_{-i})$ falls into Rule (iii) and hence, $g(m_i^k,{\widehat{m}}_{-i})=b_i^k$. Thus,

$$\underset{k\to \mathrm{\infty }}{lim}{u}_i(g(m_i^k,{\widehat{m}}_{-i}),{\theta }^{\prime })=\underset{x\in A}{sup}{u}_i(x,{\theta }^{\prime })\ge u_i(g(m_i^{\ast },{\widehat{m}}_{-i}),{\theta }^{\prime }).$$

Finally, whenever $(m_i^{\ast },{\widehat{m}}_{-i})$ falls into Rule (ii) or (iii), for $k$large enough, $(m_i^k,{\widehat{m}}_{-i})$ falls into Rule (iii) and $g(m_i^k,{\widehat{m}}_{-i})=b_i^k$. Hence, a similar reasoning as above applies.    

The following Lemma is useful, which is where we first use Assumption 1:

Lemma 1.

$\underset{k\to \mathrm{\infty }}{lim}{\displaystyle \underset{{\widehat{m}}_{-i}}{\int }}{u}_i(g(m_i^k,{\widehat{m}}_{-i}),{\theta }^{\prime })𝑑{\mu }_{-i}={\displaystyle \underset{{\widehat{m}}_{-i}}{\int }}\underset{k\to \mathrm{\infty }}{lim}{u}_i(g(m_i^k,{\widehat{m}}_{-i}),{\theta }^{\prime })d{\mu }_{-i}$.

Proof.

Given Assumption 1 and the pointwise convergence from Claim 2, this is an application of the Lebesgue dominated convergence theorem.    

We complete the argument by now observing that

$\underset{k\to \mathrm{\infty }}{lim\; inf}{\displaystyle \underset{{\widehat{m}}_{-i}}{\int }}{u}_i(g(m_i^k,{\widehat{m}}_{-i}),{\theta }^{\prime })𝑑{\mu }_{-i}$ $={\displaystyle \underset{{\widehat{m}}_{-i}}{\int }}\underset{k\to \mathrm{\infty }}{lim}{u}_i(g(m_i^k,{\widehat{m}}_{-i}),{\theta }^{\prime })d{\mu }_{-i}>{\displaystyle \underset{{\widehat{m}}_{-i}}{\int }}{u}_i(g(m_i^{\ast },{\widehat{m}}_{-i}),{\theta }^{\prime })𝑑{\mu }_{-i},$

where the equality is by Lemma $1$ and the strict inequality is by Claims $1$ and $2$ combined with the fact that ${\mu }_{-i}\left(m_{-i}^{\ast }\right)>0$ and that, by Assumption 1, $\underset{{\widehat{m}}_{-i}}{\int }{u}_i(g(m_i^{\ast },{\widehat{m}}_{-i}),{\theta }^{\prime })𝑑{\mu }_{-i}$ is finite. This implies that for $k$ large enough,

$$\underset{{\widehat{m}}_{-i}}{\int }{u}_i(g(m_i^k,{\widehat{m}}_{-i}),{\theta }^{\prime })𝑑{\mu }_{-i}>\underset{{\widehat{m}}_{-i}}{\int }{u}_i(g(m_i^{\ast },{\widehat{m}}_{-i}),{\theta }^{\prime })𝑑{\mu }_{-i},$$

and hence player $i$ is better off using $m_i^k$ rather than $m_i^{\ast }$ against ${\mu }_{-i}$, a contradiction.

Finally, in case $m^{\ast }$ falls into Rule (ii) or Rule (iii) and $g\left(m^{\ast }\right)=a$, a similar reasoning as above can be used to show that if $a$ is not the most prefered outcome at ${\theta }^{\prime }$ for at least $n-1$ players, then there is some player $i$ for whom $m_i^k$ is a profitable deviation. Hence, by NVP, we must also have $a\in F({\theta }^{\prime })$.

4 Concluding remarks

Remark 3.

Based on the proof of Theorem 1, it is clear that we can extend the argument to all objective correlated equilibria (CE).  In other words, if $\mu$ is a CE at ${\theta }^{\prime }$ and $\mu \left(m^{\ast }\right)>0$, then $g\left(m^{\ast }\right)\in F\left({\theta }^{\prime }\right)$, using only the assumptions for Nash implementation.

On the other hand, since the set of all action profiles played with positive probability by some subjective correlated equilibrium is a superset of the set of correlated rationalizable action profiles (Brandenburger and Dekel (1987)), the results of Bergemann, Morris, and Tercieux (2011) imply that the assumptions in Theorem 1 are not enough to ensure implementation in subjective correlated equilibria.

Remark 4.

Although we have assumed here that preferences over lotteries have a vNM representation, note that the proof of Theorem 1 proceeds by showing that for an any opponents’ pure strategy profile, we can find a strategy that dominates the equilibrium strategy for the relevant player (as was also noted by MS). Therefore, it appears that one needs only minimal assumptions on preferences over lotteries for MSNE-implementation. We are currently developing this point.