6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Giskard Feb 12 '16 at 10:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Shane Feb 13 '16 at 13:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Giskard Feb 15 '16 at 15:08
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Giskard Jan 30 '16 at 10:36
  • $\begingroup$ This is both smart and impressively simple. Thanks! $\endgroup$ – Shane Feb 1 '16 at 15:37

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.