6
$\begingroup$

Let $\Delta \subset \mathbb R^n$ be the locus of vectors whose entries are nonnegative and sum to $1$.

For $M$ an $n\times n$ matrix over $\mathbb R$, let $x_M \in \Delta$ be the vector $x$ that maximizes $\min_{ y \in \Delta} x^T M y$. (For generic $M$, this vector will be unique.)

Let $|\operatorname{supp}(x_M)|$ be the number of entries of $x_M$ are nonzero.

Is the expectation of $|\operatorname{supp}(x_M)|$ for $M$ a random matrix with all entries independent and identically distributed with the uniform distribution on $[-1,1]$, greater than the expectation of $|\operatorname{supp}(x_M)|$ for $M$ a random skew-symmetric matrix with all entries above the diagonal independent and identically distributed with the uniform distribution on $[-1,1]$?


I'm happy to consider variants of the problem, like using the entropy instead of the size of the support and using Gaussian instead of uniform distributions.


The only thing I know about this problem is that for $n=2$, the answer is yes, because for $M$ a skew-symmetric $2\times 2$ matrix, $x_M$ is always $(1,0)$ or $(0,1)$ depending on if the upper-right entry of $M$ is positive or negative, so $|\operatorname{supp}(x_M)|$ is always $1$, whereas if $M$ is not skew-symmetric, $|\operatorname{supp}(x_M)|=2$ with positive probability, for instance if $M = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ with $a > b < d > c < a$.


The game-theoretic background/interpretation is as follows.

Consider a competitive game with two players where each player simultaneously chooses one of $n$ strategies, and the outcome is determined by those choices.

The matrix entry $M_{ij}$ denotes the payoff of the first player if the first player chooses the $i$th strategy and the second player chooses the $j$th strategy. For example, we could consider a game with a random element where each player has a chance of winning given their strategy and the other player's. We could define the payoff to be the chance of winning, maybe after subtracting $1/2$ to make it symmetric around $0$. Because the game is perfectly competitive, the second player's payoff is given by $M_{ij}$.

$\Delta$ is the set of possible mixed strategies, where a player chooses one of the $n$ possible (pure) strategies randomly according to some probability distribution. The expected payoff given mixed strategies $x$ and $y$ is $x^T M y$.

In game theory, the optimal strategy is defined as a mixed strategy that maximizes your payoff even if the other player chooses the best possible response against you (a Nash equilibrium strategy, although this special case was defined earlier by von Neumann). Because the game is perfectly competitive, maximizing the second player's payoff is the same as minimizing the first player's. Thus the payoff of any strategy $x$ for the first player, given that the second player chooses an optimal response, is $\min_{y \in \Delta} x^T M y$, and the overall optimal strategy is the $x$ that maximizes this.

The support of the vector $x$ is then the number of pure strategies that the first player must randomly choose between. The larger this number, the more complicated a mixed strategy they are playing.

Finally, the game is symmetric if the first player's payoff given that they choose the strategy $i$ and the second player chose $j$ is the same as the second player's payoff if the second player chose $i$ and the first chose $j$. In other words $M_{ij} = - M_{ji}$.

The question is whether this symmetry leads to less complicated strategies. This was inspired by thinking about some actual competitive two-player games which have more or less symmetric forms (like playing two copies of the same character against each other, instead of two different characters) and noticing that the more symmetric ones seem to have simpler strategies, where more possible options are ignored.

$\endgroup$
2
  • $\begingroup$ Could you explain the connection between the questions and games & strategies in the title, or point to some background material? $\endgroup$ Aug 3 '21 at 0:58
  • 1
    $\begingroup$ @BrianHopkins Sure, see the edited version. $\endgroup$
    – Will Sawin
    Aug 3 '21 at 1:19
1
$\begingroup$

Apparently not much have been said in the literature about this question. You can consult:

  1. Brandl, Florian. "The distribution of optimal strategies in symmetric zero-sum games." Games and Economic Behavior 104 (2017): 674-680.
  2. Jonasson, Johan. "On the optimal strategy in a random game." Electronic Communications in Probability 9 (2004): 132-139.

Eilon

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