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)$

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

2 Answers 2

Reset to default
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.

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .