ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
January 10th, 2018 at 3:07:08 PM permalink
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?
Last edited by: ThatDonGuy on Jan 10, 2018
FCBLComish
FCBLComish
  • Threads: 3
  • Posts: 549
Joined: Apr 11, 2010
January 10th, 2018 at 5:01:22 PM permalink
S Strategy- Pry D's hand open. Count coins. Choose the name number of coins. Profit!

:)
Beware, I work for the dark side.... We have cookies
Doc
Doc
  • Threads: 46
  • Posts: 7287
Joined: Feb 27, 2010
January 10th, 2018 at 6:32:39 PM permalink
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.
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
January 10th, 2018 at 6:53:27 PM permalink
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
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
January 11th, 2018 at 2:48:46 PM permalink
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.
1MatterToMotion
1MatterToMotion
  • Threads: 0
  • Posts: 181
Joined: Nov 27, 2017
January 12th, 2018 at 2:41:17 PM permalink
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?
Never make a bet that you wouldn't take, yourself.
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
January 12th, 2018 at 3:15:11 PM permalink
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.
Romes
Romes
  • Threads: 29
  • Posts: 5600
Joined: Jul 22, 2014
January 12th, 2018 at 11:57:26 PM permalink
Comedy Option: Hold all the coins (to make your hand heavier)... Knock S out and take his coins.
Playing it correctly means you've already won.
1MatterToMotion
1MatterToMotion
  • Threads: 0
  • Posts: 181
Joined: Nov 27, 2017
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
January 13th, 2018 at 2:26:28 PM permalink
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?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
January 13th, 2018 at 3:47:27 PM permalink
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).
1MatterToMotion
1MatterToMotion
  • Threads: 0
  • Posts: 181
Joined: Nov 27, 2017
January 13th, 2018 at 5:39:18 PM permalink
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?
Never make a bet that you wouldn't take, yourself.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
January 13th, 2018 at 5:54:46 PM permalink
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.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
January 15th, 2018 at 2:27:28 PM permalink
I'm close...
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
January 15th, 2018 at 2:40:10 PM permalink
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.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
January 15th, 2018 at 3:33:53 PM permalink
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 1D 2D 3D 4D 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 1D 2D 3D 4D 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)
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
January 15th, 2018 at 4:20:30 PM permalink
I did think the amount won or lost was the total of all coins bet. However, this was my event matrix:

D 1D 2D 3D 4D 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.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
January 15th, 2018 at 5:54:11 PM permalink
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.
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
January 15th, 2018 at 7:30:33 PM permalink
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?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
1MatterToMotion
1MatterToMotion
  • Threads: 0
  • Posts: 181
Joined: Nov 27, 2017
January 15th, 2018 at 8:03:26 PM permalink
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?
Never make a bet that you wouldn't take, yourself.
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
January 16th, 2018 at 6:20:15 AM permalink
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?)
1MatterToMotion
1MatterToMotion
  • Threads: 0
  • Posts: 181
Joined: Nov 27, 2017
January 16th, 2018 at 8:13:11 AM permalink
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.
Never make a bet that you wouldn't take, yourself.
  • Jump to: