h a l f b a k e r y
Veni, vidi, teenie weenie yellow polka dot bikini.
add, search, annotate, link, view, overview, recent, by name, random
news, help, about, links, report a problem
or get an account
To play 21s you get a group of 6-15 people in a room and have them close their eyes. The object is to count to 21, one number at a time, without anyone speaking over anyone else. You have to sense when no one is going to speak and say the appropriate number. If two or more people go for it at the same
time you start over.
Now take that game to the crowd at a sports stadium, perhaps as a prelude to kick off. Participants have to scream the number so everyone can hear it. Silence but for the numbers emanating from the distance and the collective sighs when 2 (or likely more) people mess it up.
The only problem is the type of people that go to sports matches are commonly the type of people who would take enjoyment in spoiling the game. Give it time to become a commonplace tradition (a few decades) and the spoilers will be less inclined to spoil.
However, the temptation to be a part of the winning crowd would be too much to keep you quiet and failure would be commonplace.
But imagine the day they succeed! Imagine filling your lungs and screaming at the top of your voice "TWENTY ONE!" and the crowd going flippin' wild!
||This sounds like an exercise for a tutorial in statistical analysis or traffic arrival rate in telecoms...
||Okay folk, for this game of 21s, you all keep quiet, and I count to 21. We all win.
||Ah yes, that would certainly work, but where would be the sense of achievement?
||Most suitable sporting events might include the Olympics, Wimbledon's centre court, and maybe a cricket ground, but cricket supporters are about as loutish as football or rugby's.
||//Wimbledon's centre court// ... I'm thinking you get ejected before you get to 4 ...
||What, were you watching the San Diego / Indianapolis game last weekend?
||Should this not have been posted by
||What happened in the San Diego / Indianapolis game last weekend?
||I ought to work out the statistics on
this. Basically, a lot depends on the
time it takes to utter each number, and
on how you judge whether two numbers
are "overlapping". For example, if
someone says "ten" and then someone
says "eleven" immediately afterwards, it
is very difficult to tell exactly where the
"nnnn" of "ten" ended or the "eh" of
||OK. So, for the sake of argument,
suppose it takes 0.5s to utter each
number (a fair average, allowing for a
discernable gap). What next?
||Well, let's suppose that we divide time
into half-second windows (this
quantization shouldn't affect the answer
too much). In each window, each
person has the option to remain silent,
or to shout out the next number in the
sequence. If two people shout in the
same window, the game is void, yes?
||OK. Suppose we have N people in the
crowd. Suppose also that they are all
equally likely to shout a number.
Suppose also that each person adjusts
their behaviour so that the probability
of their shouting a number in any given
window is P. What is the optimal value
of P, given N?
||Well, if P is very, very small (P<<1/N)
then the probability of two shouts
coinciding is also small, and hence the
game will be "won" every time. The
only problem is that, for very small P's,
the time taken to complete the game
will be very long (imagine a thousand
people, where each person has only a
one in ten million probability of
shouting in any one interval; there will
be an average of one shout every three
hours, and it will take 60 hours to finish
||If P is larger, then of course games will
proceed faster, but most games will be
"lost" because of coinciding shouts.
||So, suppose we want to find P (given N)
such that the average time to complete
a "winning" game is minimized.
||Let me go away and think about that.
||OK. I've thought. The following
statistics are quick and dirty but
approximately correct. We have to
assume that P < 1/N for them to work.
||So, consider any one utterance. What is
the probability that it is "killed" (and the
game voided) by another utterance in
the same quantum of time? Well, as
long as P <1/N, that probability (which
we'll call K) is roughly NP.
||So, what is the probability that a game
gets through all 21 numbers without
failing? It is obviously (1-K)^21.
||How long will it take to get through
each game? Here, we have to make a
simplification, by assuming that, if a
game "fails", it gets *on average* half
way through before it does so. (This
just makes the maths easier). So, on
average, each game goes from 1 to 10
||With this assumption, the average game
requires 10 utterances. On average,
there will be NP utterances in each
"quantum" of time, so the average game
will last for 10/NP quanta of time.
||So, the probability of a game
succeeding is (1-K)^21, and the
average time taken for a game to run
(either losing or winning) is 10/NP.
||To have a 50% chance of winning a
game, we need to run 0.5/[(1-K)^21]
games, which will take a total time (T)
||T=(10/NP) x (0.5/[(1-K)^21] quanta of
||We want to find P, given N, such that T
is minimized. Remember that:
||T=(10/NP) x (0.5/[1-NP]^21)
||OK. Time to go away and think again.
||OK, back again. A little calculus would
give us a function that would find the P
necessary to minimize T for any given
||However, a little calculus is a dangerous
thing. Instead, we can start by trying to
find the optimal value of NP, since this
term appears as an entity in the
|| Calculation gives the following (each
line gives the value of NP, and the
corresponding value of T):
||In fact, the minimum value of T comes
at NP=0.045 (where T=292).
||So now, we can apply this to a real
situation. Average attendance at major
league games is, say, 10,000 people (ie,
N=10,000). At such a game, if we want
NP=0.045, each person should have a
probability P of shouting in every
=4.5 x 10^-6.
||or once in about 0.2 million "quanta".
Since we defined a "quantum" as 0.5
seconds, it follows that each person
should shout, on average, once every
0.1 million seconds, or once every 27
||In this way, there will be a "win" at the
earliest possible opportunity, and it will
typically take 292 quanta of time, or
146 seconds, or about two and half
||How would you do this in practice?
Even easier!! Upon entering the
stadium, each person picks a random
number between 1 and 100,000. They
then count seconds, in their head,
starting with that number. If a
person gets to 100,000 they shout the
next number in the
||Of course, this makes a few
assumptions about human behaviour.
It assumes that everyone picks a truly
random number and counts at roughly
the right speed, doesn't cheat, and isn't
influenced by other utterances or by
unseemly (but random) silent pauses.
||Statisticians conferences would be the
place to try this out.
||If you ignore all the other rubbish, then //Well, as long as P <1/N, that probability (which we'll call K) is roughly NP.//
||Please report to the Clay Institute to collect your <places pinky in mouth> ONE MILLION dollars.
||It's very kind, but I'm too busy applying
the viscothixotropic theory of custard to
an axiom-free solution of Goldbach's
||The main point is that there is a simple
strategy whereby the game of "Stadium21"
is easily winnable by a large crowd of
||Uncle Petros would be so proud! I disagree with the view that it is a //simple strategy//.
||Quite so, but what would the Parrot say?
||The biggest difference between game theory and decision theory (which you are proposing) is that game theory relies on the *interaction* between participants. Not enough attention has been paid to the fact that information relevant to the entire game is accessed at differing time intervals for each participant. The speed of sound, and the stadium size, are effecting different participants in different ways. This situation does not exist in the // 6-15 people in a room and have them close their eyes// scenario. You would either, have to eliminate the "speed of sound"/"distance" part (as you have done), or reformulate the strategy including the varying rate of information transfer for individual players. The solution you propose is less game theory and more decision based algorithm. I would imagine Guedj's parrot would say something along those lines.
||Although the model doesn't take into
account several subtleties (such as the
speed of sound, the size of stadium,
and the position of the judge who is
listening for the shouts, which could
be factored in but would make the
maths more complex), I believe that is a
||The cornerstones of game theory are
that (a) participants try to achieve the
optimal outcome for themselves
(regardless of whether this is for the
common good) (b) participants play to a
set of rules imposed by the game (c)
participants do not know in advance the
intentions of other players and (d)
participants can benefit by taking into
account the *likely* intentions of other
players (usually by assuming that the
other players have the same goals as
||My model fits all of these criteria. Each
player's goal is to see the game
completed; the rules are that no two
utterances must overlap; each player
has no idea when another player will
utter; and each player must estimate
the likelihood that another will utter.
||The optimal solution is when all players
utter rarely enough to give the greatest
chance of completing a game, in the
shortest possible time. In what way is
this not game theory? Unless each
player is familiar with the habits of the
other players, what information could
they use in order to implement decision
||I've just done some more thinking on
this, and I'm pretty sure that my
strategy (which I argue is game theory)
is the optimal solution (aside from the
corrections for speed of sound etc).
||The players are all equivalent or, more
importantly, have no prior means for
distinguishing amongst themselves, and
therefore must consider themselves to
be equivalent. Under these conditions,
and barring any prior agreement
between the players, the *optimal*
strategy will result in a random
distribution of utterances across time.
If players try to develop a rule to avoid
randomness (for example "if no one has
uttered for three seconds, then utter"),
then this will lead to clustering of
||Therefore, randomly-timed utterances
are the optimal solution (without
collusion), and my
algorithm allows a way for all players to
calculate the average frequency with
which they should utter in order to
achieve the best outcome.
||[boys'parks] all that you say is true, but
depends upon strategies either agreed
in advance, or evolved further into the
game. However, I maintain that, for a
crowd of previously unconnected
individuals, the a priori strategy I
proposed is the best one.
||In reality, of course, two factors will
||(1) most people will not be aware of this
optimal strategy, and hence will not
follow it. Nevertheless, this is equally
true in all game theory: the optimal
result depends upon all players being
intelligent and independently
converging upon the same, optimal,
||(2) as you point out, better strategies
are available if the crowd discusses or
organizes amongst itself, up to the
point of electing 21 individuals and
having them count from 1 to 21 in
order. However, bring 10,000 people
together "cold" and ask them to start
playing without preamble, and my
strategy will be optimal.
||In any case, my point was that the game
is by no means "practically impossible"
as the subtitle says: a crowd of people
can win the game in under three
minutes, just by guessing how many
other people are around and then each
adjusting their tendency to utter
||True enough. However, some
parameters still apply even after
iteration. It's unlikely that a complete
consensus will be reached within three
minutes (a handful of tries at most),
so it's likelier that (as you proposed)
local groups will form, each involving
perhaps a hundred people. (I'm
guessing that one central individual will
be readily visible and audible by a
hundred neighbours, thereby defining a
locally coordinated cluster).
||In this case, then, we have perhaps a
hundred local clusters in the stadium,
and each cluster can behave like a
single indivudual, independent of its
||In this situation, we still want to aim for
0.045 "utterances" per unit time (or
0.09 utterances per second, if the
quantum of time is 0.5s and if we
ignore the speed of sound). In this
case, all we have done is effectively
reduce "N" from 10,000 to 100. Each
group should therefore make an
utterance (through its spokesperson)
once every 1100 seconds or so. Unless
there is long-range coordination
between groups, the best strategy will
be for each group to utter at a random
time (but still averaging only one
utterance per group per 1100 seconds).
the average time to complete a game
successfully will be the same - about
2-3 minutes on average.
||Clearly, a "Mexican wave" strategy could
evolve, but this requires coordination
over longer distances (for example, to
avoid two simultaneous starts, or a
wave running in two directions from
one starting point). Once this degree of
coordination evolves, the game ceases
to become interesting.
||<waves palm over top of head, with bemused look on face, whilst blowing out of mouth>
||If this were a statisticians' conference, of
course, you've had been more logical and
started with 0, [theleo]