I didn’t catch that post. It would be interesting to solve for optimum strategy here. Almost certainly a mixed strategy, both for selecting and for accusing. The specifics of length of game, cost/benefit of false/true accusation, and the final evaluation (do points matter or it it just win/lose) all go into it.
I suspect there would be times when one would pick a low roll so as not to get accused but also prevent a worst-case roll. I also suspect those are times when one should always accuse, regardless of roll.
Let’s look at a relatively simple game along these lines:
Person A either cheats an outcome or rolls a d4. Then person B either accuses, or doesn’t. If person B accuses, the game ends immediately, with person B winning (losing) if their accusation was correct (incorrect). Otherwise, repeat a second time. At the end, assuming person B accused neither time, person A wins if the total sum is at least 6. (Note that person A has a lower bound of a winrate of 3/8ths simply by never cheating.)
Let’s look at the second round first.
First subcase: the first roll (legitimate or uncaught) was 1. Trivial win for person B. Second subcase: the first roll was 2. Subgame tree is as follows:
The resulting equlibria are:
Person A always rolls.
Person B allows 1-3, and either always calls 4, or calls 4 1⁄4 of the time.
Either way, expected value is −1/2 for Person A, which makes sense given person A plays randomly (1/4 die rolls win for person A).
Third subcase: the first roll was 3. Simplified subgame tree is as follows:
There are 5 (five) equlibria for this one:
Person A always plays randomly.
Person B always allows 1 and 2, and either always calls both 3 and 4, or always calls one of 3 or 4 and allows the other 50% of the time, or 50⁄50 allows 3/calls 4 or allows 4/calls 3, or 50⁄50 allows both / calls both.
Overall expected value is 0, which makes sense given person A plays randomly (2/4 die rolls win for person A).
Fourth subcase: the first roll was 4. I’m not going to enumerate the equlibria here, as there are 40 of them (!). Suffice to say, the result is, yet again, person A always playing randomly, with person B allowing 1 and calling 2-4 always or probabilistically in various combinations, with an expected value of +1/2.
And then the first round:
Overall equlibria are:
Person A plays randomly 3⁄4 of the time, cheats 3 3/16th of the time, and cheats 4 1/16th of the time.
Person B always allows 1 and 2, and does one of two mixes of calling/allowing 3 and 4. (0 | 5⁄32 | 7⁄16 | 13⁄32, or 5⁄32 | 0 | 9⁄32 | 9⁄16 of call/call | call/allow | allow/call | allow/allow).
Either way, expected value for person A is −5/32.
Tl;DR:
This (over)simplified game agrees with your intuition. There are mixed strategies on both sides, and cases where you ‘may as well’ always call, and cases where you want to cheat to a value below the max value.
(Most of this was done with http://app.test.logos.bg/ - it’s quite a handy tool for small games, although note that it doesn’t compute equilibria for single giant games. You need to break them down into smaller pieces, or fiddle with the browser debugger to remove the hard-coded 22 node limit.)
The other player gets to determine your next dice roll (again, either manually or randomly).
Could you elaborate here?
Alice cheats and say she got a 6. Bob calls her on it. Is it now Bob’s turn, and hence effectively a result of 0? Or is it still Alice’s turn? If the latter, what happens if Alice cheats again?
I’m not sure how you avoid the stalemate of both players ‘always’ cheating and both players ‘always’ calling out the other player.
Instead of dice, a shuffled deck of playing cards would work better. To determine your dice roll, just pull two cards from a shuffled deck of cards without revealing them to anyone but yourself, then for posterity you put those two cards face down on top of that deck.
How do you go from a d52 and a d51 to a single potentially-loaded d2? I don’t see what to do with said cards.
Ignore the suit of the cards. So you can draw a 1 (Ace) through 13 (King). Pulling two cards is a range of 2 to 26. Divide by 2 and add 1 means you get the same roll distribution as rolling two dice.
That’s not the same roll distribution as rolling two dice[1]. For instance, rolling a 14 (pulling 2 kings) has a probability of 4∗352∗51≈0.0045249, not 17∗7≈0.020408[2].
(The actual distribution is weird. It’s not even symmetrical, due to the division (and associated floor). Rounding to even/odd would help this, but would cause other issues.)
This also supposes you shuffle every draw. If you don’t, things get worse (e.g. you can’t ‘roll’ a 14 at all if at least 3 kings have already been drawn).
====
Fundamentally: you’re pulling out 2 cards from the deck. There are 52 possible choices for the first card, and 51 for the second card. This means that you have 52*51 possibilities. Without rejection sampling this means that you’re necessarily limited to probabilities that are a multiple of 152∗51. Meanwhile, rolling N S-sided dice and getting exactly e.g. N occurs with a probability of 1NS. As N and S are both integers, and 52=2*2*13, and 51=3*17, the only combinations of dice you can handle without rejection sampling are:
...and even then many of these don’t actually involve both cards. For instance, to get 2d2 with 2 pulled cards ignore the second card and just look at the suit of the first card.
Alice and Bob won’t always cheat because they will get good rolls sometimes that will look like cheats but won’t be.
Wait, do you mean:
Decide to cheat or not cheat, then if not cheating do a random roll, or
Do a random roll, and then decide to cheat or not?
I was assuming 1, but your argument is more suited for 2...
import itertools
import fractions
import collections
cards = list(range(1, 14))*4
dice_results = collections.Counter(a+b for a in range(1, 8) for b in range(1, 8))
dice_denom = sum(dice_results.values())
card_results = collections.Counter((a+b)//2+1 for a, b in itertools.permutations(cards, r=2))
card_denom = sum(card_results.values())
for val in range(2, 15):
print(val, fractions.Fraction(card_results[val], card_denom), fractions.Fraction(dice_results[val], dice_denom), sep='\t')
[edited]
I didn’t catch that post. It would be interesting to solve for optimum strategy here. Almost certainly a mixed strategy, both for selecting and for accusing. The specifics of length of game, cost/benefit of false/true accusation, and the final evaluation (do points matter or it it just win/lose) all go into it.
I suspect there would be times when one would pick a low roll so as not to get accused but also prevent a worst-case roll. I also suspect those are times when one should always accuse, regardless of roll.
Let’s look at a relatively simple game along these lines:
Person A either cheats an outcome or rolls a d4. Then person B either accuses, or doesn’t. If person B accuses, the game ends immediately, with person B winning (losing) if their accusation was correct (incorrect). Otherwise, repeat a second time. At the end, assuming person B accused neither time, person A wins if the total sum is at least 6. (Note that person A has a lower bound of a winrate of 3/8ths simply by never cheating.)
Let’s look at the second round first.
First subcase: the first roll (legitimate or uncaught) was 1. Trivial win for person B.
Second subcase: the first roll was 2. Subgame tree is as follows:
The resulting equlibria are:
Person A always rolls.
Person B allows 1-3, and either always calls 4, or calls 4 1⁄4 of the time.
Either way, expected value is −1/2 for Person A, which makes sense given person A plays randomly (1/4 die rolls win for person A).
Third subcase: the first roll was 3. Simplified subgame tree is as follows:
There are 5 (five) equlibria for this one:
Person A always plays randomly.
Person B always allows 1 and 2, and either always calls both 3 and 4, or always calls one of 3 or 4 and allows the other 50% of the time, or 50⁄50 allows 3/calls 4 or allows 4/calls 3, or 50⁄50 allows both / calls both.
Overall expected value is 0, which makes sense given person A plays randomly (2/4 die rolls win for person A).
Fourth subcase: the first roll was 4. I’m not going to enumerate the equlibria here, as there are 40 of them (!). Suffice to say, the result is, yet again, person A always playing randomly, with person B allowing 1 and calling 2-4 always or probabilistically in various combinations, with an expected value of +1/2.
And then the first round:
Overall equlibria are:
Person A plays randomly 3⁄4 of the time, cheats 3 3/16th of the time, and cheats 4 1/16th of the time.
Person B always allows 1 and 2, and does one of two mixes of calling/allowing 3 and 4. (0 | 5⁄32 | 7⁄16 | 13⁄32, or 5⁄32 | 0 | 9⁄32 | 9⁄16 of call/call | call/allow | allow/call | allow/allow).
Either way, expected value for person A is −5/32.
Tl;DR:
This (over)simplified game agrees with your intuition. There are mixed strategies on both sides, and cases where you ‘may as well’ always call, and cases where you want to cheat to a value below the max value.
(Most of this was done with http://app.test.logos.bg/ - it’s quite a handy tool for small games, although note that it doesn’t compute equilibria for single giant games. You need to break them down into smaller pieces, or fiddle with the browser debugger to remove the hard-coded 22 node limit.)
What’s the drawback to always accusing here?
[edited]
Interesting.
Could you elaborate here?
Alice cheats and say she got a 6. Bob calls her on it. Is it now Bob’s turn, and hence effectively a result of 0? Or is it still Alice’s turn? If the latter, what happens if Alice cheats again?
I’m not sure how you avoid the stalemate of both players ‘always’ cheating and both players ‘always’ calling out the other player.
How do you go from a d52 and a d51 to a single potentially-loaded d2? I don’t see what to do with said cards.
[edited]
That’s not the same roll distribution as rolling two dice[1]. For instance, rolling a 14 (pulling 2 kings) has a probability of 4∗352∗51≈0.0045249, not 17∗7≈0.020408[2].
(The actual distribution is weird. It’s not even symmetrical, due to the division (and associated floor). Rounding to even/odd would help this, but would cause other issues.)
This also supposes you shuffle every draw. If you don’t, things get worse (e.g. you can’t ‘roll’ a 14 at all if at least 3 kings have already been drawn).
====
Fundamentally: you’re pulling out 2 cards from the deck. There are 52 possible choices for the first card, and 51 for the second card. This means that you have 52*51 possibilities. Without rejection sampling this means that you’re necessarily limited to probabilities that are a multiple of 152∗51. Meanwhile, rolling N S-sided dice and getting exactly e.g. N occurs with a probability of 1NS. As N and S are both integers, and 52=2*2*13, and 51=3*17, the only combinations of dice you can handle without rejection sampling are:
Nd1[3]
1d2, 1d3, 1d4, 1d13, 1d17, 1d26, …, 1d(52*51)
2d2
...and even then many of these don’t actually involve both cards. For instance, to get 2d2 with 2 pulled cards ignore the second card and just look at the suit of the first card.
Wait, do you mean:
Decide to cheat or not cheat, then if not cheating do a random roll, or
Do a random roll, and then decide to cheat or not?
I was assuming 1, but your argument is more suited for 2...
Aside from rolling a strange combination of a strangely-labelled d52 and a strangely-labelled d51, or somesuch.
This is somewhat trivial, but I figured it was worth mentioning.