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$
4
  • 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$ Dec 6, 2014 at 17:50
  • $\begingroup$ Do you know the answer if A is symmetric? $\endgroup$
    – domotorp
    Dec 8, 2014 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, 2014 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, 2014 at 9:21

2 Answers 2

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$
5
  • $\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, 2014 at 23:30
  • $\begingroup$ Yes, you are right, I will see if I can correct this later. $\endgroup$
    – Giskard
    Dec 9, 2014 at 1:24
  • $\begingroup$ @RB Example updated! $\endgroup$
    – domotorp
    Dec 9, 2014 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, 2014 at 9:11
  • 1
    $\begingroup$ @RB I've sent him the new question. $\endgroup$
    – domotorp
    Dec 31, 2014 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.