Puzzles with Rock-Paper-Scissors

[blimix]

Today, I thought of some variants on an otherwise trivial puzzle.

This will be Rock-Paper-Scissors, as played by a mathematician and/or game theorist, rather than (as it is played in real life) a psychological contest of reading your opponent's intentions.

In these puzzles, we will posit that your opponent knows your strategy, and plays optimally for their own benefit. (Assume each player cares only about their own income. No generosity and no spite for the other player.) So if your strategy is to play Rock, your opponent will play Paper. Your saving grace is that you are allowed to use a random ("mixed") strategy.

I hope that even those among us who are not mathematically inclined can intuit that the ideal strategy is to pick randomly from Rock, Paper, and Scissors, with equal chances of each.

But what happens if we throw off the symmetry of the game, not by changing the system, but by introducing different rewards for different wins?

Problem 1: Good old Rock. The payout from the loser to the winner is as follows: $9 if the winner throws Rock; $3 if the winner throws Scissors; $1 if the winner throws Paper.

Now you will lose by keeping the probabilities equal: Your opponent would throw Rock and count on winning much more to Scissors than they would lose to Paper. And you couldn't just throw Paper in anticipation of them throwing Rock, because they get to know your strategy, and they would just throw Scissors instead.

What strategy can you employ, that your opponent can't beat even if they know what it is?

(If you said, "The only winning move is not to play," then congratulations on being a smart-ass. Now find a real answer.)

Hint: How do you make a strategy that your opponent cannot beat? A good path is to formulate your strategy such that all of your opponent's choices are equally good. If you leave them with one clearly better choice, then your strategy still has room to improve: You could make their best choice a little worse, at the cost of making their worst choice a little better, which is a good trade for you. Once you've given them no good reason to prefer one move over another, you've probably minimized their winnings — and your losses.

Problem 2: On the House. The payouts are the same as in problem 1, but instead of coming from the loser, they come from the bank. Does your strategy change, and if so, how?

I won't screen comments, so beware of spoilers if you read them. I'll post my answers in a day or two.

Some white space, in case you only clicked through to read the hint, but do not want to see answers in the comments:

Comments

[roamin_umpire]

1) I believe that playing each piece proportional to its potential winnings is ideal. In this case, Rock 9/13 of the time, Scissors 3/13, and paper 1/13...

Hm. Except that doesn't work. He still plays Rock all the time and wins an average of $2 per round. ($27 - $1 over 13 rounds.)

Gonna have to think some more...

2) This one's easier. I alternate Scissors and Rock. If at any point my opponent does not reciprocate with Rock and Scissors in alternating parity, I switch back to the optimal strategy from #1. We each make $4.50 per round, which is as good as it gets.

[blimix]

Yeah, I thought the tit-for-tat strategy for number 2 would win it too. And, like you, I intuited that you couldn't possibly do better than half the total available money from Rock. And yet, there really are better solutions to be found. Keep trying!

[blimix]

Oh, and your idea for #1 was also the first one that occurred to me. A very natural thought!

[alanj]

1) In an optimal strategy, all my opponents moves are going to have the same EV, and since it's a symmetric zero-sum game, that EV will be zero. If my probabilities are R, S, P, then if he throws rock he gets 9S - P, if he throws scissors he gets 3P - 9R, if he throws paper he gets R - 3S; all of those are set to zero, and also of course R + S + P = 1; solving, we get R = 3/13, S = 1/13, P = 9/13.

Intuitively, you rarely throw scissors because it gets so heavily punished by rock, but the rarity of scissors means paper is very safe so that becomes the dominant throw.

2) My first thought was the tit-for-tat alternating rock/scissors thing, but that assumes this is a repeated-play scenario with evolving strategies. If we're playing once and I declare my strategy is (0.5, 0.5, 0), then my opponent just throws rock and I get nothing; if I declare that I'm throwing scissors first, or rock first, then he just plays to beat me.

However, you're specifying that I get to declare my strategy first, and my opponent responds to maximize his EV, and in this particular non-zero-sum game that's a huge advantage for me.

I'm going to throw paper just enough to make scissors his best throw, and throw rock the rest of the time to cash in on his scissors. My strategy is (0.75-epsilon, 0, 0.25+epsilon), he will always throw scissors because it is 4*epsilon better than throwing rock, and my EV is 9*(0.75-epsilon) = $6.75 - 9*epsilon, while he only gets $0.75 + 3*epsilon. I have no proof that this is optimal but it seems pretty damn good.

[blimix]

Woohoo! Those are exactly the answers I got.

[roesser.livejournal.com]

Never throw scissors… you could poke someone's eye out.

[icarusfallen8.livejournal.com]

Would throwing Rocks or Paper be any worse?

[(Anonymous)]

No, you'd have the least to loss and the most to gain by throwing Rocks or Papers. Though the paper cuts could get pretty nasty and one should always make sure they are without sin before casting the first stone.

[roesser.livejournal.com]

That last post was mine, I forgot to log in.

[aprivatefox.livejournal.com]

I don't know what the optimal strategy is, but it's provably a strategy that ties in the long term:

1) There is no difference between the players in the game, including who goes first - both players move simultaneously and have equivalent scoring.
2) Therefore, any strategy player A could follow, player B could also follow.
3) Assume there exists an optimal strategy. By 1) and 2) above, the strategy is optimal for player A and player B.
4) RPS as described is a zero-sum game.
5) Players have perfect knowledge of each others' strategies
6) By 5) above, if there is an optimal strategy, and player A employs it, then player B is also aware of it.
7) By 3) and 6), player B is now aware of the optimal strategy.
8) If the strategy is optimal, it is by definition better than all other strategies.
9) By 7) and 8), player B should switch to this strategy.
10) By 9), if there exists an optimal strategy, then both players A and B will use it.
11) By 4) and 10), If both players use the same strategy, the best score that can be arrived at is a draw.

My formal proof skills are a little rusty, but I believe that proves that if an optimal strategy exists, it must be a strategy that yields a draw.

[blimix.livejournal.com]

While intuition certainly suggests that the best you can do is a tie, I think the leap from point 8 to point 9 doesn't quite hold in either problem, and point 4 clearly doesn't hold for problem 2.

The problem with points 8-9 is that the two players are in different situations: One of them is looking for a general sort of "best strategy" for the game, and the other only needs the strategy that is the best response to the first player's strategy. So they might well use different "optimal" strategies.

[aprivatefox.livejournal.com]

I still don't think that holds on Problem 1.

You said that the opponent wants to maximize their own income, same as you. So, if your strategy gives a result better than net-tie, then your opponent must be losing money. In which case their best move is to switch to your strategy, which is clearly better than theirs.

Point 4 is only applicable to the first problem, though, that's true. I suspect that for problem 2, the optimal strategy will result in both players playing "swingy" games at random, so both players maximize extraction from the bank in all scenarios.

[blimix.livejournal.com]

I agree with you regarding problem 1. Once you invoke point 4 (as you just did), point 9 then becomes convincing.

Oh, and while it doesn't matter much in practical terms, point 8 is technically incorrect. An optimal strategy is at least as good as all other strategies, but not necessarily better. (Player B will come to know this if player A does their job right.)

[aprivatefox.livejournal.com]

OK, that's true. Point 8 should more properly be "a strategy in the set of optimal strategies can have no better strategy," making it a cheap corrollary to prove "two strategies in the set of optimal strategies must always tie in the long term."

[kirin]

Okay, here's an informal thought process for problem 1, which I feel is probably missing something. Just some gut-level reasoning. No time for rigor right now.

First thought: you never want to lose big, so never throw scissors. You opponent will know that's part of your strategy, and never throw rock.

We can't throw the remaining two possibilities with any pattern, or the opponent will know it and counter. So we pick Paper or Rock randomly.

This looks pretty good. The obvious counter to random Paper/Rock is random Scissors/Paper. But that leaves a random result matrix with entries for you of -1 / 0 / +9 / -3. A clear win for you.

But that win means the opponent should be doing something different. Why should their reasoning be different from yours? So what if they play random Paper/Rock too. Then it's 0 / +1 / -1 / 0, an obvious tie. Which, yeah, ought to be as good as it gets due to symmetry, but it does satisfy the question as a strategy your opponent cannot *beat*. I think.

No wait. They can always throw paper, making it 0 / 0 / -1 / -1. Hmmmm.

[don radlauer (from livejournal.com)]

Problem 2 is relatively easy, IMO. Since the bank is paying all the bonuses, we want every play to result in the maximum $9.00 payout for a rock-breaks-scissors victory. The best way to ensure this is to play cooperatively, with each player alternately playing rock and scissors. Thus, if I start with rock and you play scissors, the next round I will play scissors and you will play rock. Assuming that both players are smart enough to figure this out, it should be easy to set up this cooperative (if boring) mode of play even if verbal communication isn't allowed - at worst, it would take a few rounds to get the rhythm going.

[blimix.livejournal.com]

This is a good solution, and is exactly what I thought it would turn out to be, before I put pen to paper.

But it turns out that with a different strategy, you can average better than $4.50 per round! (It clearly won't be fair to your opponent.)