4
$\begingroup$

EDIT: rewritting the question to linear algebra to make it more accessible.

Denote by $\Delta([n])$ the set of all probability distributions over $\{1,2,\ldots,n\}$, that is: $$\Delta([n])=\{x\in[0,1]^n\mid \sum_{i=1}^n x_i=1\}$$

Let $A\in [0,1]^{n\times n}$ be a matrix, and let $x,y,z\in \Delta([n])$.

Does the following conditions:

  1. $\forall r\in\Delta([n]): r^tAy\leq x^tAy$
  2. $\forall r\in\Delta([n]): x^tA^tr\leq x^tA^ty$
  3. $\forall r\in\Delta([n]): r^tAz \leq \ \ z^tAz,\ \ z^tA^tr\ \ \leq \ \ z^tA^tz$
  4. $\forall i\in[n]: x_i+y_i > 0, z_i > 0$

Imply that $$x^t(A+A^t)y\geq z^t(A+A^t)z$$?


For example, if

$A= \left( \begin{array}{ccc} 0.3 & 0.6 \\ 0.4 & 0.2 \\ \end{array} \right) $

Then $z=\left( \begin{array}{ccc} 0.8 \\ 0.2 \\ \end{array} \right)$ , $x=\left( \begin{array}{ccc} 1 \\ 0 \\ \end{array} \right)$ , $y=\left( \begin{array}{ccc} 0 \\ 1 \\ \end{array} \right)$

Satisfy the conditions and $$x^tAy+x^tA^ty = 0.6 + 0.4 > 0.36 + 0.36 = z^tAz\ + z^tA^tz$$


Notice that if condition (4) isn't true, then the claim doesn't hold, e.g.:

$A= \left( \begin{array}{ccc} 1 & 0 \\ 0 & 1 \\ \end{array} \right) $

And $z=\left( \begin{array}{ccc} 1 \\ 0 \\ \end{array} \right)$ , $x=y=\left( \begin{array}{ccc} 0.5 \\ 0.5 \\ \end{array} \right)$

$\endgroup$
  • 2
    $\begingroup$ You might try this question at economics.stackexchange.com, which just recently entered public beta. There seem to be quite a few mathematically literate people there, and they are perhaps more likely to have the relevant expertise. $\endgroup$ – Paul Siegel Dec 6 '14 at 17:50
  • $\begingroup$ Do you know the answer if A is symmetric? $\endgroup$ – domotorp Dec 8 '14 at 22:15
  • $\begingroup$ Also, am I right that the condition on $x$ and $y$ is the same? Just transpose condition (2) and swap $x$ and $y$, you get condition (1). $\endgroup$ – domotorp Dec 9 '14 at 8:52
  • $\begingroup$ @domotorp - condition (1) means that $x$ is in the best-response of $y$, and condition (2) vice versa. $\endgroup$ – R B Dec 9 '14 at 9:21
3
+50
$\begingroup$

I am the aforementioned economist. I figured out a counterexample for the non-singular case:

Let $$ A = \left( \begin{array}{ccc} 0 & 7 & 0 \\ 7 & 0 & 0 \\ 3 & 3 & 1 \end{array} \right) $$

$$ z = \left( \begin{array}{ccc} \frac{1}{3}, & \frac{1}{3}, & \frac{1}{3} \end{array} \right) $$

$$ x = \left( \begin{array}{ccc} \frac 15, & 0, & \frac45 \end{array} \right) $$

$$ y = \left( \begin{array}{ccc} 0, & \frac 15, & \frac45 \end{array} \right) $$

The expected payoff is $2\cdot \frac 73$ in the symmetric equilibrium and $\frac 75 + \frac 75$ in the other one. As far as I can tell there is no 2x2 non-singular counterexample.

$\endgroup$
  • $\begingroup$ Hmm, it seems that $Az=(\frac{4}{3},\frac{4}{3},2)$, so $z$ doesn't seem to be an equilibrium. Am I missing something? $\endgroup$ – R B Dec 8 '14 at 23:30
  • $\begingroup$ Yes, you are right, I will see if I can correct this later. $\endgroup$ – Giskard Dec 9 '14 at 1:24
  • $\begingroup$ @RB Example updated! $\endgroup$ – domotorp Dec 9 '14 at 8:54
  • $\begingroup$ @domotorp - you (and your brother !) have been very helpful in this question. Care to look at this one :) ? $\endgroup$ – R B Dec 31 '14 at 9:11
  • 1
    $\begingroup$ @RB I've sent him the new question. $\endgroup$ – domotorp Dec 31 '14 at 12:47
1
$\begingroup$

Let

$A= \left( \begin{array}{ccc} 1 & 0 \\ 1 & 0 \\ \end{array} \right) $.

Then any $x, y, z$ satisfy the conditions, so it is easy to make a counterexample. We get a more challenging question if we suppose that $A$ is non-singular, in this case there is a unique $z$ that satisfies the conditions.

(Solution by my brother who is an economist.)

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