Rock Paper Scissors for arbitrary odd number of elements

Question

How do I efficiently create a rock-scissors-paper game for n elements, where n is any odd number >=3.

In other words, I want a non-transitive complete ordering of n elements such that each element is greater than (n-1)/2 other elements and each element is lesser than (n-1)/2 other elements.

Answer 1

Assume your items are numbered 0,1,2,...,n-1.

Item i beats item j iff i - j (mod n) > (n-1)/2.

In other words you can rotate the list such that your chosen item is in the middle of the list:

i - (n-1) / 2, ..., i-2, i-1, i, i+1, i+2, ..., i + (n-1) / 2

Then item i beats all the items below it in the list.

A matrix of i vs j would look like this:

  0 1 2 3 4
0 - L L W W
1 W - L L W
2 W W - L L
3 L W W - L
4 L L W W -

This is not the only possibility, but it is probably the simplest. You can construct any matrix that obeys these rules:

• All values on the diagonal are zero.
• The other values are 1 or -1 (win, lose).
• It is a skew symmetric matrix.
• It has exactly (n-1)/2 wins and losses in every row and column.

Here is another more complex example:

  0 1 2 3 4
0 - L W W L
1 W - W L L
2 L L - W W
3 L W L - W
4 W W L L -

Or phrased another way:

0 beats 2 and 3.
1 beats 0 and 2.
2 beats 3 and 4.
3 beats 1 and 4.
4 beats 0 and 1.

In this example it may be possible to relabel the items to give the same logic as in the previous game. I doubt that holds in general though.

Answer 2

Fantastic, thanks!

As another approach (inspired by yours), k beats k+1 (mod n-1), k+2 (mod n-1), etc... for the next (n-1)/2 elements.