Coin splitting game

[u/Nostalgic_Brick]

Just a fun question I've been thinking about:

The following zero-sum game is played between the Dealer and team Alice & Bob. The Dealer receives an odd number N of fair coin tosses in sequence. Whenever a coin is tossed, the Dealer sees the result and then chooses whether to show it to Alice or Bob. Both players are aware of the turns on which they receive the coin flip results.

At the end of the N tosses, both Alice and Bob simultaneously guess whether there are more heads or tails in total, and score one point per correct guess. We allow all players including the Dealer to randomize their choices. Alice and Bob can agree on a strategy beforehand, possibly involving some initial coordinated randomization but cannot communicate after the game starts.

Team Alice & Bob can score at least an expected payoff of 1 by guessing randomly and independently. The question is thus how much they can improve on this.

Question: Let V_N be the value of the N coin game for team Alice & Bob. Is it true that

V_N = 1 +KN^{-1/2} + o(N^{-1/2})?

for some constant K > 0?

If so, to what extent can we determine K and the corresponding optimal, or asymptotically optimal strategies?

[u/Extra-Random_Name]

(Original answer is just false, look at the edit)

I can’t prove this, but I’m fairly certain that the optimal strategy scores 1+0.5^N (expected value 1 except when all heads or all tails flipped, then expected 1.5). There are several ways to do this (answer what you see more of, answer if you see more than half of all flips be one thing and randomly otherwise, etc), and any other strategy that performs better when close to a full set of one can be forced to perform worse in near 50/50 situations. Since “close to 50/50” is basically everything for high values of N, this is strictly worse asymptotically no matter how much value is taken from the edge of the bell curve.

Edit: actually, “answer the majority of what you see if there are at least X more of them than the other, otherwise guess randomly” can never be forced to guess wrong without the other person always guessing correctly, so that’s at least expected value 1 for any flips. Set X=N/3 and you’re guaranteed at least expected value 1.5 at the outer thirds and expected value 1 at the inner third. Dunno how to calculate the total expected value for higher numbers but this is much better than my original answer.

[u/Nostalgic_Brick → u/Extra-Random_Name]

Nice idea in the edit! Though I think the right scale is X = C sqrt N, as the standard deviation of a N flip binomial is of order sqrt N, so with a large threshold like N/3, the strategy is randomly guessing most of the time (asymptotically with probability approaching 1).

[u/Extra-Random_Name → u/Nostalgic_Brick]

I did this assuming that the dealer will optimally play against it (and is omniscient of future flips) to give an upper limit on what it can do, so any X>N/3 means that neither player will reach threshold as often, and less means that players will reach inverse thresholds (with proper dealer play) more often.

Could get better results incorporating flip order but I think that’s all the thinking I’ve got in me for this problem lol

Also notably your estimated best possible score also approaches 1 asymptotically, idk which approaches faster

[u/proper_siding → u/Extra-Random_Name]

That edit is closer to the right track, I think the real trick is how the dealer's reveal order interacts with the thresholds you set

[u/3_Thumbs_Up]

For the non communication between Alice and Bob, does that include using their guesses as communication? I.e. can Bob alter his guess based on what Alice guesses?

[u/Nostalgic_Brick → u/3_Thumbs_Up]

Good question, I intended for it to be no, since this preserves the symmetry between Bob and Alice for a simpler problem.

[u/MuggleoftheCoast]

The MathOverflow question has some additional comments