Something about game theory (I think?)

Taken from my microblog, because it's slightly (but only slightly) long form.

I was in the beach the other day when something occurred to me.

In middle school, when no-one had a coin handy and you needed to do some coin-toss decision, people would «throw Even Odd». The protocol is as follows: two parties (usually not collaborating) pick "Even" or "Odd". Then, on the count of three, the two parties will "throw" a number (rock-paper-scissors style), the winner being whoever guessed the parity of the sum correctly.

(A moment to parse that last sentence.)

It's pretty intuitive* that no matter how you play you don't have much control over the outcome, unless you know exactly how the other player will act. As long as the two players are adversarial, it might as well be random.

• Read: I don't know the math to prove this. I know just enough about Game Theory to know that this is about Game Theory, of which I know nothing of.

So what if you were missing a die, rather than a coin? Could you use a similar protocol to throw some number, rather than a binary yes or no?

As far as I can tell, yes, by having two players throwing a number (between 0 and N --- say, 0 to 4), and taking the sum modulo N.

For one, the distribution of the possible sums (modulo N) is always balanced. Or, according to this Python script, this holds for N in 2...100, and that's a lot of fingers. So you're not more likely to get some outcomes, overall.

On the other hand, I don't think any of the players has a way to bias the outcome; this to me is clearer if you think of the game as one of the players picking the value and the other one offsetting it (with wrap-around). Whatever one player picks, the other one can offset the value to wherever they want.

Likewise, if one of the player has a particular bias, the other player can shift that bias wherever; of course the first player can then shift *their* bias and so on, and so the game doesn't have an equilibrium.

Of course, psychological factors might come into play; I'd bet that people wanting a low value would intuitively throw a low number as well.

I'd like to see how a formal proof of this goes; if you know game theory and are so inclined, shoot me an email! (You can find my email on the home page.)

🏞

That was the original post. Since then I've Googled for whether (a+b mod N) is uniformly distributed for any N, if a and b are uniformly distributed between 0 and N, and the answer is yes.

The proof is simple and I feel I ought to have got there. I reproduce it below:

(Let's see how well I can write math with unicode...)

A ~ UniformInteger[0, N) 
B ~ UniformInteger[0, N)

Pr[A + B = c] = Σ(b=0; N-1; Pr[A = c - b ⋀ B = b]) =     # c - b is understood to be mod N (such that -1 → N-1)
              = Σ(b=0; N-1; Pr[A = c - b].Pr[B = b]) =   # Both players make their choices independently
              = Σ(b=0; N-1; 1/N . Pr[B = b]) =
              = 1/N . Σ(b=0; N-1; Pr[B = b]) =           # Total probability is 1...
              = 1/N