<p>Let $BR=(BR_1,BR_2,BR_3,...)$ denote the best response mapping. This gives a mapping given message vector $m$. (For any $BR_i$ only the messages of non $i$ players are used to derive the best response mapping.)</p>

<p>Let $m^* = (m_1^*,m_2^*,m_3^*,...)$ denote the symmetric equilibrium. As it is an equilibrium, for any $i$ you have $BR_i(m^*) = m_i^*$, so
$$
BR(m^*) = m^*.
$$
Suppose we have a non truth-telling equilibrium $m'$. As this is an equilibrium
$$
BR(m') = m'
$$
so
$$
\forall i\in N: m_i' = \theta_i + \gamma \sum_{j \ne i} (\theta_j-m_j').
$$
Rearranging this
$$
\forall i\in N: 0 = \theta_i - m_i' + \gamma \sum_{j \ne i} (\theta_j-m_j').
$$
Adding up all the equations yields
\begin{eqnarray*}
0 &amp; = &amp; \sum_i (\theta_i - m_i') + \gamma \sum_i \sum_{j \ne i} (\theta_j-m_j')
\\
0 &amp; = &amp; \sum_i (\theta_i - m_i') + \gamma \cdot (n-1) \cdot  \sum_i (\theta_i - m_i') \\
0 &amp; = &amp; (1 + \gamma \cdot (n-1)) \cdot \sum_i (\theta_i - m_i')  .
\end{eqnarray*}
There are two ways this can hold. Either $\sum_i (\theta_i - m_i') = 0$ or $\gamma = -\frac{1}{n-1}$. </p>

<p>Case 1. Suppose $\sum_i (\theta_i - m_i') = 0$. Then from
\begin{eqnarray*}
m_i' &amp; = &amp; \theta_i + \gamma \sum_{j \ne i} (\theta_j-m_j') \\
m_i' - \theta_i &amp; = &amp; \gamma \sum_{j \ne i} (\theta_j-m_j') \\
(m_i' - \theta_i) - \gamma \cdot (m_i' - \theta_i)  &amp; = &amp;  \gamma \cdot (\theta_i - m_i') + \gamma \sum_{j \ne i} (\theta_j-m_j') \\
(1 - \gamma) \cdot (m_i' - \theta_i) &amp; = &amp; \gamma \sum_{j} (\theta_j-m_j') = 0.
\end{eqnarray*}
In the truth-telling equilibrium this is true for all $i \in N$. If $\gamma = 1$ non truth-telling equilibria are also possible for any number of players, e.g. $n-1$ players reporting their type $+1$ and one player reporting her type $-n+1$. If $\gamma &lt; 1$ and the equilibrium is non truth-telling then this is not possible.</p>

<p>Case 2.
Suppose $\gamma = -\frac{1}{n-1}$.  <br> Let $x_i$ denote $\theta_i - m_i'$, so the equation system
$$
\forall i\in N: 0 = \theta_i - m_i' + \gamma \sum_{j \ne i} (\theta_j-m_j')
$$
becomes
$$
\forall i\in N: 0 = x_i + \gamma \sum_{j \ne i} x_j.
$$
For $\gamma = -\frac{1}{n-1}$ the matrix representation of this equation system is invertible so there is only a single solution, and $\forall i: x_i = 0$ is clearly a solution. This means that the only equilibrium is the truth-telling equilibrium.</p>

CC BY-SA 3.0
2016-01-30T10:36:32.573Z
@Shane Having thought about this it is as you point out true that $BR$ is not a contraction if $\gamma > \frac{1}{n-1}$. I can offer a linear algebra based proof instead.
Giskard
CC BY-SA 3.0
2016-02-01T15:37:33.603Z
This is both smart and impressively simple. Thanks!
Shane
CC BY-SA 3.0
2016-01-29T17:54:39.017Z
2016-01-30T16:21:21.827Z
2016-01-30T16:21:21.827Z
Giskard
<p>In an auction setting with interdependent values, let $\theta_i$ denote the type of player $i$ and $m_i$ that player's message (a bid, essentially). I have calculated the best response function as:
$$m_i^* = \theta_i + \gamma \sum_{j \ne i} (\theta_j-m_j)$$
Obviously, then, truth-telling by all parties ($m_k = \theta_k$ for all $k$) is a symmetric BNE, regardless of $\gamma$. I want to also argue that it is the unique BNE. If $\gamma = 1$, it seems like there would be assymetric BNE if there are only two players in which one player's positive misreport ($m_i - \theta_i$) would equal the other player's negative misreport ($\theta_j - m_j$). If $\gamma&lt;1$, it looks like the truth-telling BNE is unique, but how would I prove that?</p>

<p>Also, so far I have not used a common prior assumption. Do I need it here to argue the existence of the truth-telling BNE, or to argue it's uniqueness? If so, we can suppose $\theta_i$ is drawn i.i.d. uniformly from $[0,1]$.</p>

CC BY-SA 3.0
2016-02-12T10:13:02.500Z
I would like to use this model to demonstrate a technique to someone. Could you give me a reference or let me know where I can find the model from which you arrived at this best response function?
Giskard
CC BY-SA 3.0
2016-02-13T13:53:27.037Z
Have a look at _Robust Implementation in Direct Mechanisms_, 2009, by Bergemann and Morris. I should mention that your argument below is complete only if the action spaces are unbounded. If they're bounded, you're technically just proving that no _interior_ non-truth-telling BNE exists. In that setting, the only way I know how to get uniqueness is through a contraction property, as you proposed originally. The BR above is a contraction if $\gamma<\frac{1}{n-1}$, with $n$ the number of players.
Shane
CC BY-SA 3.0
2016-02-15T15:08:33.647Z
Thank you for the paper. Having just read I would like to point out that Bergemann and Morris also look at the cases where $\gamma < \frac{1}{n-1}$ and where $\gamma > \frac{1}{n-1}$ separately. (Middle of page 1182.) And in fact they later also invoke contractions for the first case.
Giskard
<game-theory><nash-equilibrium><auctions><bayesian-game>
Arguing uniqueness of Bayes-Nash equilibrium in an auction setting
Shane
# Arguing uniqueness of Bayes-Nash equilibrium in an auction setting

(Asked by: username_0 on 2016-01-29)

In an auction setting with interdependent values, let $\theta\_i$ denote the type of player $i$ and $m\_i$ that player's message (a bid, essentially). I have calculated the best response function as:
$$m\_i^\* = \theta\_i + \gamma \sum\_{j \ne i} (\theta\_j-m\_j)$$
Obviously, then, truth-telling by all parties ($m\_k = \theta\_k$ for all $k$) is a symmetric BNE, regardless of $\gamma$. I want to also argue that it is the unique BNE. If $\gamma = 1$, it seems like there would be assymetric BNE if there are only two players in which one player's positive misreport ($m\_i - \theta\_i$) would equal the other player's negative misreport ($\theta\_j - m\_j$). If $\gamma<1$, it looks like the truth-telling BNE is unique, but how would I prove that?

Also, so far I have not used a common prior assumption. Do I need it here to argue the existence of the truth-telling BNE, or to argue it's uniqueness? If so, we can suppose $\theta\_i$ is drawn i.i.d. uniformly from $[0,1]$.

**Tags:** game-theory, nash-equilibrium, auctions, bayesian-game

> **Comments:**
> **username_1**: I would like to use this model to demonstrate a technique to someone. Could you give me a reference or let me know where I can find the model from which you arrived at this best response function?  
> **username_0**: Have a look at _Robust Implementation in Direct Mechanisms_, 2009, by Bergemann and Morris. I should mention that your argument below is complete only if the action spaces are unbounded. If they're bounded, you're technically just proving that no _interior_ non-truth-telling BNE exists. In that setting, the only way I know how to get uniqueness is through a contraction property, as you proposed originally. The BR above is a contraction if $\gamma<\frac{1}{n-1}$, with $n$ the number of players.  
> **username_1**: Thank you for the paper. Having just read I would like to point out that Bergemann and Morris also look at the cases where $\gamma < \frac{1}{n-1}$ and where $\gamma > \frac{1}{n-1}$ separately. (Middle of page 1182.) And in fact they later also invoke contractions for the first case.  

---

## 1 answers

### Answer by username_1 on 2016-01-29. Score: 3 | Accepted answer

Let $BR=(BR\_1,BR\_2,BR\_3,...)$ denote the best response mapping. This gives a mapping given message vector $m$. (For any $BR\_i$ only the messages of non $i$ players are used to derive the best response mapping.)

Let $m^\* = (m\_1^\*,m\_2^\*,m\_3^\*,...)$ denote the symmetric equilibrium. As it is an equilibrium, for any $i$ you have $BR\_i(m^\*) = m\_i^\*$, so
$$
BR(m^\*) = m^\*.
$$
Suppose we have a non truth-telling equilibrium $m'$. As this is an equilibrium
$$
BR(m') = m'
$$
so
$$
\forall i\in N: m\_i' = \theta\_i + \gamma \sum\_{j \ne i} (\theta\_j-m\_j').
$$
Rearranging this
$$
\forall i\in N: 0 = \theta\_i - m\_i' + \gamma \sum\_{j \ne i} (\theta\_j-m\_j').
$$
Adding up all the equations yields
\begin{eqnarray\*}
0 & = & \sum\_i (\theta\_i - m\_i') + \gamma \sum\_i \sum\_{j \ne i} (\theta\_j-m\_j')
\\
0 & = & \sum\_i (\theta\_i - m\_i') + \gamma \cdot (n-1) \cdot \sum\_i (\theta\_i - m\_i') \\
0 & = & (1 + \gamma \cdot (n-1)) \cdot \sum\_i (\theta\_i - m\_i') .
\end{eqnarray\*}
There are two ways this can hold. Either $\sum\_i (\theta\_i - m\_i') = 0$ or $\gamma = -\frac{1}{n-1}$.

Case 1. Suppose $\sum\_i (\theta\_i - m\_i') = 0$. Then from
\begin{eqnarray\*}
m\_i' & = & \theta\_i + \gamma \sum\_{j \ne i} (\theta\_j-m\_j') \\
m\_i' - \theta\_i & = & \gamma \sum\_{j \ne i} (\theta\_j-m\_j') \\
(m\_i' - \theta\_i) - \gamma \cdot (m\_i' - \theta\_i) & = & \gamma \cdot (\theta\_i - m\_i') + \gamma \sum\_{j \ne i} (\theta\_j-m\_j') \\
(1 - \gamma) \cdot (m\_i' - \theta\_i) & = & \gamma \sum\_{j} (\theta\_j-m\_j') = 0.
\end{eqnarray\*}
In the truth-telling equilibrium this is true for all $i \in N$. If $\gamma = 1$ non truth-telling equilibria are also possible for any number of players, e.g. $n-1$ players reporting their type $+1$ and one player reporting her type $-n+1$. If $\gamma < 1$ and the equilibrium is non truth-telling then this is not possible.

Case 2.
Suppose $\gamma = -\frac{1}{n-1}$.   
 Let $x\_i$ denote $\theta\_i - m\_i'$, so the equation system
$$
\forall i\in N: 0 = \theta\_i - m\_i' + \gamma \sum\_{j \ne i} (\theta\_j-m\_j')
$$
becomes
$$
\forall i\in N: 0 = x\_i + \gamma \sum\_{j \ne i} x\_j.
$$
For $\gamma = -\frac{1}{n-1}$ the matrix representation of this equation system is invertible so there is only a single solution, and $\forall i: x\_i = 0$ is clearly a solution. This means that the only equilibrium is the truth-telling equilibrium.

> **Comments:**
> **username_1**: @username_0 Having thought about this it is as you point out true that $BR$ is not a contraction if $\gamma > \frac{1}{n-1}$. I can offer a linear algebra based proof instead.  
> **username_0**: This is both smart and impressively simple. Thanks!  

---

