4
$\begingroup$

While playing ``rock paper scissors'' with my daughter it became obvious that she wanted to add a few elements to the game, Specifically the fox and the well. A bit later we added the match and the fly.

Since I wanted it to be a balanced tournament, the completed game looked like this:

the game we came up with

Although there is only one orientation of the $K_3$ (complete graph on three vertices) which is balanced, and the same seems to hold for $K_5$, this is definitively not the case for $K_7$. In fact, writing the above graph as a matrix:

$ \left(\begin{array}{rrrrrrr} \mathit{Rock} & \mathit{Paper} & \mathit{Scissors} & \mathit{Fox} & \mathit{Well} & \mathit{Match} & \mathit{Fly} \\ 0 & -1 & 1 & 1 & -1 & 1 & -1 \\ 1 & 0 & -1 & -1 & 1 & -1 & 1 \\ -1 & 1 & 0 & 1 & -1 & 1 & -1 \\ -1 & 1 & -1 & 0 & 1 & -1 & 1 \\ 1 & -1 & 1 & -1 & 0 & 1 & -1 \\ -1 & 1 & -1 & 1 & -1 & 0 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 0 \end{array}\right)$

one sees that many chunks of columns are similar: the three entries of the fox, well, match and fly columns are either identical or reversed.

In order to make things more random, I thought of using a Hadamard matrix of size 8. First remove first row and column (those which are, for the standard way of writing Hadamard matrices full with 1). Then permute the rows so that the diagonal entries are all -1. Finally set the diagonal to 0 (i.e. add the identity matrix). There are a few candidates (I guess they are all isomorphic), one looks like this:

$ \left(\begin{array}{rrrrrrr} 0 & -1 & 1 & -1 & 1 & 1 & -1 \\ 1 & 0 & -1 & -1 & -1 & 1 & 1 \\ -1 & 1 & 0 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 0 & -1 & -1 & -1 \\ -1 & 1 & -1 & 1 & 0 & 1 & -1 \\ -1 & -1 & 1 & 1 & -1 & 0 & 1 \\ 1 & -1 & -1 & 1 & 1 & -1 & 0 \end{array}\right) $

The resulting matrix gives an orientation of $K_7$ which is balanced. Furthermore, the columns do not have this tendency to have many entries which are identical or reversed. Here is the corresponding graph:

a tournament based on a Hadamard matrix

There are [up to isomorphisms] only 3 possible games on 7 elements: the number of non-isomorphic balanced orientation of $K_{2n+1}$, is given here. See the paper Rock-Paper-Scissors and borromean rings by Chamberland and Herman.

Although it seems to me that this solution is optimal (see below) for the 7 elements game, moving up to a nine elements game, I was wondering how to quantify the quality of the graph. Basically if $F$ is the matrix of the first game, then $F^tF$ is not very uniform. Whereas if $S$ is the matrix of the second game, then $S^tS$ takes the same value everywhere except on the diagonal. Hence a measure of how optimal (how unpredictable) the game is, would be to look at how the matrix $M^tM$ deviates from a matrix with all non-diagonal coefficients equal.

My primary question is:

Question: What are [other] possible ways to measure the deviation from [some form] of ideal game? i.e. what are possible definitions of optimal?

Actually, a friend of mine pointed out, that, when the number of elements is big, it is still a fun game even when the nodes are not all balanced. Indeed, if one element is stronger (in the sense that it wins against more elements than it loses), than one might be tempted to pick it. But then, it still loses against a few others, so you might tempted to pick them. And so on. Still I don't want to go primarily in this direction because: (1) I don't think it's easy to quantify; (2) My feeling is that such games reduce to a part of the whole.

So a secondary question would be:

Question: What are possible ways to measure the deviation from [some form] of ideal game in the unbalanced version?

I was thinking about stationary measures for a random walk, but I guess there are more clever ways to go around...

$\endgroup$

0

You must log in to answer this question.