Mathematical Aspects of Ro-sham-bo,

                         or

          An Argument Against Roster Limits


Historically, ultimate players have used "Ro-sham-bo" or
"rock-paper-scissors" to adjudicate disputes such as line calls,
player substitutions, alcohol appropriation, etc.  However, there
seems to be little understanding of the mathematics behind the method.
In this article, we attempt to address these issues.  We compute the
average length of a ro-sham-bo, and suggest that this naturally leads
to limits on the practical size of an ultimate team.

First, a quick review of the rules of ro-sham-bo.  At every round,
each player "throws" either rock, paper, or scissors.  If only two of
the three throws appear in that interval, then the players who threw
the superior throw continue and the others are eliminated.  If all
three throws appear, or if only one appears, then the round is a tie
and all players participate in the next round.  Throw precedence is
circular (rock "breaks" scissors "cut" paper "covers" rock), so the
game is symmetric.

We consider a game of ro-sham-bo as a finite-state machine, whose
state is the number of players participating.  At each discrete time
interval, there are two options: tie, or win.  In event of a tie, the
number of players remains the same, so we stay in the same state.  If
the round is a win, then the number of players is reduced, and there
is a transition to a lower state.  The game is over when state 1 is
reached, i.e., one player has won.  We can see that the number of
throws necessary to select a winner is equal to the number of ties
plus the number of wins.

Clearly, if there are n players then there are 3^n possible sets of
throws (each player has three choices, players are independent).  A
round results in a win if all players throw one of two throws (2^n-2);
there are three choices for pairs of two throws (RP,PS,SR), so there
are 3*2^n-6 winning sets of throws.  Thus, the probability of a tie is
p(n) = (3*2^n-6)/3^n.  It is easy to show that the average number of
throws with n players will be 1/p(n).

Now, we calculate the probability of k players remaining after an
n-player win.  There are (n,k) ways to choose k players to be on the
winning side, so the probability that n players reduce to k is
(n,k)/(2^n-2).  We can now write a recurrence relation that defines
R(n), the number of throws necessary to choose a winner among n
players:

R(1) = 0        n-1   C(n,k)*R(k)
R(n) = 1/p(n) + Sum( ------------- )
                k=1     (2^n-2)

                          n!
       where  C(n,k) = --------
                       k!(n-k)!

The table below shows R(n) for up to 20 players:

 1    0
 2    1.5
 3    2.25
 4    3.2143
 5    4.4857
 6    6.2198
 7    8.6467
 8   12.1044
 9   17.0919
10   24.3496
11   34.9795
12   50.6250
13   73.7404
14  107.9931
15  158.8684
16  234.5736
17  347.3947
18  515.7294
19  767.1359
20 1142.9032

It is interesting to put this in a more practical light.  Suppose
everyone on an ultimate team is participating (except for one player
-- there's always one who "doesn't do that game"), and that each round
takes 2-3 seconds.  An 18-man team will take about 15 minutes to reach
a decision, a 21-man team about 40 minutes.  At the end of a
tournament, ultimate players generally hang out for a while, but are
not willing to wait several hours to decide on a restaurant.
Similarly, if seven players are in the game, the rest of the team can
choose a beer messenger within five minutes only if there are fourteen
or fewer players on the bench.  Both examples result in an upper limit
of around 21 players on the team; any more would lead to unreasonably
long delays and the team would collapse of its own weight.  Thus
Nature herself has placed a soft upper bound on the size of an
ultimate team.

It should be noted that we have made the assumption that each person's
throws are independent of any other past, present, or future throws.
This is not the case, as shown by the ability of "ro-sham programs" to
beat humans consistently, or by the existence of superstitions
("Nothing beats rock."), of which the latter can be held responsible
for certain teams which have perennially large rosters.  However, for
large numbers of "normal" players, the tendency to "out-think" oneself
should produce, in aggregate, a uniform distribution of throws.

Other interesting facts:

o   For large n, R(n) approaches (1/3)*(3/2)^n, due to the dominance
    of ties in the initial state.

o   For large n, a win will almost always eliminate about half of the
    players.

o   Women seem to be more sensible than men and do not play ro-sham-bo.
    (Hence the use of the masculine pronoun everywhere.)