Here's one for you, Wiz...

Here's a chance to get back one of the N + 3 or so beers you supposedly owe me...I've got a gaming theory problem I can't seem to solve.

Two players, S and D, each hold anywhere from one to five ooins in their hands.
They reveal the coins simultaneously.
S wins all of the coins if they both have the same number.
D wins all of the coins if they have different numbers.
What is D's strategy?
Correction from the original, which asked for S's strategy, which I can figure out

My thinking:
Let p(n) be the probability that D holds n coins.
If n is the number that S holds, the expected value is -n p(n) + n (1 - p(n)) = n (1 - 2 p(n))
1 - 2 p(1) = 2 - 4 p(2) -> p(2) = 1/2 p(1) + 1/4
1 - 2 p(1) = 3 - 6 p(3) -> p(3) = 1/3 p(1) + 1/3
1 - 2 p(1) = 4 - 8 p(4) -> p(4) = 1/4 p(1) + 3/8
1 - 2 p(1) = 5 - 10 p(5) -> p(5) = 1/5 p(1) + 2/5

1 = p(1) + p(2) + p(3) + p(4) + p(5)
1 = (1 + 1/2 + 1/3 + 1/4 + 1/5) p(1) + (1/4 + 1/3 + 3/8 + 2/5)
1 - (1/4 + 1/3 + 3/8 + 2/5) = (1 + 1/2 + 1/3 + 1/4 + 1/5) p(1)

(120 - 30 - 40 - 45 - 48) / 120 = p(1) (120 + 60 + 40 + 30 + 24) / 120
p(1) = -43 / 274
Er, shouldn't p(1) > 0?

S Strategy- Pry D's hand open. Count coins. Choose the name number of coins. Profit!

:)

Quote: ThatDonGuy

...
What is S's strategy?

My thinking:
Let p(n) be the probability that S holds n coins.
...

If you are discussing the strategy to be preferred by player S, then the number of coins held by that player is not a probabilistic event. It is deterministic and determined by player S each time. I think using conventional statistical calculations based on these "probabilities" will lead you astray. You need a different approach to developing a strategy for S, perhaps something related to whether player D will follow some particular strategy.


I encounter the same error in my own thinking when I am working a challenging Sudoku problem. I find myself thinking, "What is the probability that the 3 is in this row of the block, based on the number of locations where it is still possible for the 3 to be found?" The location of the numbers in the solution to a specific Sudoku problem is not a probabilistic variable, and I get annoyed with myself each time I catch that I am thinking that way.

Quote: Doc

If you are discussing the strategy to be preferred by player S, then the number of coins held by that player is not a probabilistic event. It is deterministic and determined by player S each time. I think using conventional statistical calculations based on these "probabilities" will lead you astray. You need a different approach to developing a strategy for S, perhaps something related to whether player D will follow some particular strategy.

The "standard" way to calculate strategy is, assume that the strategy is, you play a particular number a fixed fraction of the time, then determine the expected values of each of the possible opponents' plays (in terms of the probabilities) and then calculate what the fractions would have to be in order for the expected values of each of the opponent's plays to be the same.

As an example, instead of the plays being anything from 1 to 5, let the only choices for each player be 1 and 10.
Let S's strategy be, play 1 coin x (e.g. 1/3) of the time, and 10 coins the other (1-x) of the time.
If D plays 1, S's expected value is 1 * x - 10 * (1 - x) = 11x - 10
If D plays 10, S's expected value is -1 * x + 10 * (1 - x) = 10 - 11x
These are equal when x = 10/11, so S's strategy is to play 1 coin 10/11 of the time and 10 coins 1/11 of the time

On the other hand, let D's strategy be to play 1 coin y of the time, and 10 coins the other (1-y) of the time
If S plays 1, D's expected value is -1 * y + 1 * (1 - y) = 1 - 2y
If S plays 10, D's expected value is 10 * y - 10 * (1 - y) = 20y - 10
These are equal when y = 1/2, so D plays 1 coin 1/2 of the time and 10 coins 1/2 of the time

Me again...I did a little brute force number crunching on the possible distributions for the selection probabilities for D to get the best return based on the five possible plays for S (i.e. the one where the lowest of the five ERs is best, breaking ties by the best second-lowest ER, then third-lowest ER, and so on), and I got something close to {0, 17 / 154, 37 / 154, 47 / 154, 53 / 154}. "Coincidentally," if you limit D's selections to 2 through 5 and do an equilibrium calculation, you get the same numbers.

However, there are still two problems with this, and I have a feeling they are related:
1. If S uses his calculated strategy, this has a positive return for D, rather than it being zero-sum.
2. I assume S should realize that D will not play 1, so it makes no sense for S to play 1 either, since S would always lose.

Quote: ThatDonGuy

However, there are still two problems with this, and I have a feeling they are related:
1. If S uses his calculated strategy, this has a positive return for D, rather than it being zero-sum.
2. I assume S should realize that D will not play 1, so it makes no sense for S to play 1 either, since S would always lose.

1. You mean rather than a symmetrical game? Or coins out of nowhere?
2. But if S(ame) doesn't play 1 coin, then D(ifferent) should play it all the time, and never lose?

Quote: 1MatterToMotion

1. You mean rather than a symmetrical game? Or coins out of nowhere?
2. But if S(ame) doesn't play 1 coin, then D(ifferent) should play it all the time, and never lose?

But then, S will play 1 all the time, and never lose, but then, D will never play 1, and never lose, so S should never play 1, but...
Isn't that all part of game theory?

Besides, even if it is symmetrical, it may not be zero-sum.
Change the rules so both S and D can play anywhere from 2 to 5 coins.
S's strategy is to play 2, 3, 4, or 5 with frequency 30/77, 20/77, 15/77, and 12/77, respectively
D's strategy is to play 2, 3, 4, or 5 with frequency 17/154, 37/154, 47/154, and 53/154, respectively.
D's ER is +120/77.

Comedy Option: Hold all the coins (to make your hand heavier)... Knock S out and take his coins.

https://math.stackexchange.com/questions/2603039/two-players-each-hold-from-one-to-five-coins-s-wins-all-if-the-same-number-but

What determines the number of coins each has? Do they get to choose? 20% each possibility? I think the answer depends on that.

By "winning all the coins" is it the total number in the game or just those played the last game?

Quote: Wizard

What determines the number of coins each has? Do they get to choose? 20% each possibility? I think the answer depends on that.

By "winning all the coins" is it the total number in the game or just those played the last game?

Each player selects his own number.

The winner gets all of the loser's coins played (i.e. if S plays 3 and D plays 4, D gets all seven coins - the four he played, and the three S played).

Quote: ThatDonGuy

Each player selects his own number.

Off hand, I wonder about the strategies when each selects the other's number for the other. Or would that be silly?

Quote: ThatDonGuy

Each player selects his own number.

The winner gets all of the loser's coins played (i.e. if S plays 3 and D plays 4, D gets all seven coins - the four he played, and the three S played).

Thanks. Initially, I thought the players started with random numbers of coins from 1 to 5 and had to choose how many to play from there. I get the problem now. Good problem. Now comes the tough part of answering it.

I'm close...

D's strategy should be to pick x coins with the following probabilities:

Pr(1)=77/548
Pr(2)=107/548
Pr(3)=117/548
Pr(4)=122/548
Pr(5)=125/548

D has an expected win of 3.640510949 coins no matter how S plays.

Quote: Wizard

D's strategy should be to pick x coins with the following probabilities:

Pr(1)=77/548
Pr(2)=107/548
Pr(3)=117/548
Pr(4)=122/548
Pr(5)=125/548

D has an expected win of 3.640510949 coins no matter how S plays.

I think you misunderstand the problem - either that, or I misunderstand what you mean by "expected win."

Here is the result matrix:

	D 1	D 2	D 3	D 4	D 5
S 1	(1,-1)	(-1,1)	(-1,1)	(-1,1)	(-1,1)
S 2	(-2,2)	(2,-2)	(-2,2)	(-2,2)	(-2,2)
S 3	(-3,3)	(-3,3)	(3,-3)	(-3,3)	(-3,3)
S 4	(-4,4)	(-4,4)	(-4,4)	(4,-4)	(-4,4)
S 5	(-5,5)	(-5,5)	(-5,5)	(-5,5)	(5,-5)

Each row is one of S's plays, each column is one of D's plays, and the values are (S's result, D's result).

I have a feeling you read the problem as:

	D 1	D 2	D 3	D 4	D 5
S 1	(2,0)	(0,3)	(0,4)	(0,5)	(0,6)
S 2	(0,3)	(4,0)	(0,5)	(0,6)	(0,7)
S 3	(0,4)	(0,5)	(6,0)	(0,7)	(0,8)
S 4	(0,5)	(0,6)	(0,7)	(8,0)	(0,9)
S 5	(0,6)	(0,7)	(0,8)	(0,9)	(10,0)

I did think the amount won or lost was the total of all coins bet. However, this was my event matrix:

	D 1	D 2	D 3	D 4	D 5
S 1	(2,-2	(-3,3)	(-4,4)	(-5,5)	(-6,6)
S 2	(-3,3)	(4,-4)	(-5,5)	(-6,6)	(-7,7)
S 3	(-4,4)	(-5,5)	(6,-6)	(-7,7)	(-8,8)
S 4	(-5,5)	(-6,6)	(-7,7)	(8,-8)	(-9,9)
S 5	(-6,6)	(-7,7)	(-8,8)	(-9,9)	(10,-10)

In your problem, using the same matrix algebra technique, I get a negative value of player D picking 1 coin.

So now let's say that player D never picks 1 coin, when what is his optimal strategy? I get

P(1)=0
P(2)=17/154
P(3) = 37/154
P(4)=47/154
P(5) = 53/154

I show player S will lose 1 unit by picking 1 and 1.558441558, on average, by picking anything else. So, player 1 will simply always pick and lose 1. I'm sure there are other probability mixtures that will keep player S always picking 1.

This doesn't seem as elegant as the problem I first answered and think I either misunderstand what is being asked still or made a mistake somewhere.

Quote: Wizard

In your problem, using the same matrix algebra technique, I get a negative value of player D picking 1 coin.

So now let's say that player D never picks 1 coin, when what is his optimal strategy? I get

P(1)=0
P(2)=17/154
P(3) = 37/154
P(4)=47/154
P(5) = 53/154

I show player S will lose 1 unit by picking 1 and 1.558441558, on average, by picking anything else. So, player 1 will simply always pick and lose 1. I'm sure there are other probability mixtures that will keep player S always picking 1.

This doesn't seem as elegant as the problem I first answered and think I either misunderstand what is being asked still or made a mistake somewhere.

I get a negative value as well, and when I tried using brute force on the possible values for the probabilities of D's choices, I got the numbers you got,

1MatterToMotion posted a link to StackExchange where somebody solved the problem by noticing, like you did, that no matter what D did, as long as D did not pick 1, S's optimal strategy was to always pick 1.

Until I looked into this problem, I thought that these types of games were all zero-sum.

Glad to hear we agree. I suggest you ask it the way I interpreted the problem next time.

How many beers will you deduct from my tab?

Quote: ThatDonGuy

Until I looked into this problem, I thought that these types of games were all zero-sum.

Just out of curiosity. What does zero-sum mean here to you? Fair?

Quote: Wizard

Glad to hear we agree. I suggest you ask it the way I interpreted the problem next time.

How many beers will you deduct from my tab?

Give one to 1MatterToMotion

Spreaking of whom...

Quote: 1MatterToMotion

Just out of curiosity. What does zero-sum mean here to you? Fair?

"Here," it means both sides' expected return = 0; I suppose you can call that "fair."

Er, but that's not what zero-sum means, does it? (It means "the sum of the gains/losses over all players = 0," doesn't it?)

Quote: ThatDonGuy

Give one to 1MatterToMotion

No, not really. I was a little confused, and sought out another perspective. The guy there took a couple of whacks at it before settling on an answer a few hours later. I used essentially your wording of it to, perhaps, allow for as many interpretations as possible. At first, he thought it was about winning as often as possible. And then something about 0, 1/4, 1/3, 3/8, 1/24 for D's p's.