Discuss Least Unique Game here

[Chuck]

It makes the solution easier by eliminating collusion.

[A-man]

Very interesting point made by Arkive. I believe that would to at least some extent change a selected strategy. If you were always choosing 1 and the selections were revealed in numerical sequence and the results were consistently 1 1 2 would that imply that the other two players are alternating between 1 and 2 or would that imply that a second player is continually choosing 1 and a third player is continually choosing 2. If you continue to choose 1 then you will never win. If you change to choosing 2 and you then notice the results were consistently 1 2 2 you still would not know what the other two players were choosing and you still would not be winning. The entire idea of 'punishing' a player goes out the window. Maybe at that point you reach the conclusion that the other two players are alternating and then you begin alternating between 1 and 2 yourself. That would then imply that only one of the other two players are consistenly winning but you are still losing. Sorry, I seem to be rambling.
_________________
Men are apt to mistake the strength of their feeling for the strength of their argument.

[Nsof]

They are all at least as rational and capable, which means that whatever strategy (be it statistical, deterministic, anything) someone comes with, the others will either adopt it or find better.
This means that they are all at least as successful as each other which in turn means that the expected earnings of person A equals that of person B which equals that of C and since the total expected earning of all is 0, they all have expected earning of 0.
Which means they might as well all play 1 every turn or better yet read whatever strategy someone here in the GL finds and all play it.

[Fotiman]

How long do we have to wait until the solution is posted? It's been over a month.

[Arkive]

[mukhee353*]

Choosing any integer greater than 3 is strictly dominated.

We can also eliminate all pure strategy Nash Eqms.

As the set of undominated strategies is finite, a mixed Nash Eqm exists. Our aim is to find one MSNE that also fulfills the PBE criteria in the repeated setting.

WLOG consider players to be A, B, C. And strategize from the viewpoint of A.

In each round, A has to act based upon her beliefs of B and C.

If with probability < 1/2, both B and C choose integers greater than "1", then A prefers to choose "1".

If with probability > 1/2, B or C choose "1", then A prefers to choose either "2" or "3" (integer greater than "1").

Thus A mixes strategies implies the probability of B or C choosing "1", is 1/2.

As B and C do not communicate, their choice probabilities are independent.

Hence, the probability of B not choosing "1" is sqrrt(1 - 1/2) = sqrrt (1/2)

Probability of B playing integer "1" = 1 - sqrrt(1/2)

In the symmetrical MSNE,

Probability of A playing integer "1" = 1 - sqrrt(1/2)
Probability of B playing integer "1" = 1 - sqrrt(1/2)
Probability of C playing integer "1" = 1 - sqrrt(1/2)

Let the phrase conditional probability imply conditioning on the event that B or C played "1", including the event that B and C played "1".

If with conditional probability < 1/2, both B and C choose integers greater than "2", then A prefers to choose "2".

If with conditional probability > 1/2, B or C choose "2", then A prefers to choose "3" (integer greater than "2").

Thus A mixes strategies and plays "3" with positive probability implies that the conditional probability of B or C choosing "2" is 1/2.

To get the unconditional probability of either B or C playing "2", multiply the conditional probability with the probability of the event = 1/2.

Thus A mixes strategies and plays "3" with positive probability implies that the unconditional probability of B or C choosing "2" is 1/2 * 1/2 = 1/4.

As B and C do not communicate, their choice probabilities are independent.

Hence, the probability of B not choosing "2" is sqrrt(1/4)

Probability of B playing integer "2" = sqrrt(1/2) - sqrrt(1/4)

In the symmetrical MSNE,

Probability of A playing integer "2" = sqrrt(1/2) - sqrrt(1/4)
Probability of B playing integer "2" = sqrrt(1/2) - sqrrt(1/4)
Probability of C playing integer "2" = sqrrt(1/2) - sqrrt(1/4)

And,

Probability of A playing integer "3" = sqrrt(1/4)
Probability of B playing integer "3" = sqrrt(1/4)
Probability of C playing integer "3" = sqrrt(1/4)

At first, this jars intuition. Notice

Pr(A -> "1") < Pr(A -> "2) < Pr (A -> "3")

However, the play of "1" is the riskiest. Unless both other players play some thing other than "1", you don't win the game, and if one player plays "1", and the other player plays anything other than "1", you lose the game.

The play of "3" allows you to win the game if either of the players tie at any point. If they both play "1" or they both play "2", you win the game. If they both play "3", you draw the game.

To lose the game by playing "3", one opponent has to play "1", and the other opponent has to play "2". It is simple to see how we can find probabilities for which we are truly indifferent.

Now suppose the game played between N players, where N is finite.

The set of integers greater than N is strictly dominated.

Restricting our attention to strategies for playing 1,... N, we get

Prob (play "1") = 1 - (1/2) ^ (1/(N-1))
Prob (play "2") = (1/2) ^ (1/(N-1)) - (1/4) ^ (1/(N-1))
Prob (play "3") = (1/4) ^ (1/(N-1)) - (1/8) ^ (1/(N-1))
and so on
Prob (play ("N") = (1/(2^(N-1)))^ (1/(N-1))

where x ^ Y denotes X raised to the power Y.

Notice that if N goes to infinity, then we no longer have a solution. Everyone plays "1" with probability 1. The problem is that the set of undominated strategies is now infinite. No strategy is strictly dominated any longer. And the logic above no longer applies.

Further notice that as N increases, we have to play longer chains of numbers to remain in equilibrium. And that means we can put less mass on the lower numbers. So the probability of playing "1" keeps decreasing.

Probability of not seeing a "1" in a game = 1/2 * [(1/2) ^ (1/(N-1))]

Perversely, as N increases, the probability of seeing a "1" in a game, increases despite each player putting less probability mass on the lower numbers.

This makes sense when we compare the probability of seeing a "1" when N=2, with N=3. For N=2, the above yields the solution of randomizing between "1" and "2", thus yielding the maximum probability of seeing a "1" in a game = 3/4.

If any of the above conditions do not hold, then your best reply correspondence does not include at least 1 of the strategies. As in the above, you are completely indifferent between all possible combinations of strategies - and hence mixing between all N lowest integers - being strictly better off has to imply that your final payoff is greater than 0.

In other words, any other strategy distribution by your opponents except the one that makes you totally indifferent between lowest integers until N (choosing "1", "2" , ... "N"), always lets you get more than 0 from the game.

Suppose A and B are colluding to the detriment of C. They must some how be hurting C - they have to steal from C to make money. But that implies that C will face strategies different from the above. Contradiction - C makes money when the strategies are any different from the above. The outlined belief distribution is the only one to leave C totally indifferent, and making no money. Thus, there is no other possible eqm.

Or, as the minmax value of the game is 0 and the only pareto optimal point is at this eqm, no other eqm is possible.

[L'lanmal]

Spoilered hint:

The three players each choose their number. I am acting as judge to determine who wins this game. Rather than ask each for their number and then determine the lowest unique responce, I blindfold them, then ask them to raise their hands if they picked the number 1.

If at least one player raises his or her hand, I know the outcome of the game. If at nobody raises his or her hand, I ask about the number 2, etc.

Non-spoilered comment: Surprisingly, if any two players employ the 2 ^-n strategy, the third gets equal returns from always picking the number 1 as he does by employing the same strategy.

[jameseyryan*]

New to this site n i have been thinkin bout this puzzle for a while. I have 2 theories.

1. It would appear that the only way to win is to use a purely random number selection strategy and win by luck. If each of the other players are on the same if not higher level than you, any strategy you pick could be thought up by your opponents and counteracted, as could a counter to the counter etc. If your opponents play to maximize their gains, they will not rest until they are winning every time as that is the maximum possible. so any strategy to benefit you will result in your opponents changing their strategy to beat it. As a result you cannot have a constant strategy or a pattern of strategies as your opponents will figure them out and try to stay one step ahead. This implies that you must select randomly and hope for the best

2. If its not number 1 then i think we need to look more into the phrasing of the rules and the methods of the game. Rule one states that the game goes on indefinitely. If we take that literally this means that it is impossible for a player to run out of money, so either the game is a zero sum game in which case we never really lose or if there is some formula for winning money, you have an unlimited supply(i.e. never really lose). so, your best strategy is to hire someone else to sit in your place and go off and do more important stuff like watch tv or go solve a different puzzle.

This sounds like a more "outside the box" answer than one of simple probability because you can roll a dice six times and expect to get each value once but statistically it doesn't always happen, however in the end as you get closer to infinity, a "count" for each numbers appearance will balance out

[marcellochiodi]

the best strategy must be the same for each player (an equilibrium stategy, maybe reached after a certain number of games) and should be the following:

playing 1 with probability 1/2; playing 2 with probability 1/4; playing 3 with probability 1/8; playing 4 with prob. 1/16; ... playing n with probability (1/2)^n...
(said in an another way: toss a coin: if heads, play 1, otherwise toss another coin and if heads play 2, otherwise toss another coin and if heads play 3 and so on...)
The average gain is zero for each of the player.

With this scheme no one should find convenient to change strategy, unless risking a loose.
I can show the result but I do not know the average evolution of the game (that is : when all players will begin to play according to this scheme (soon, after 10, 100 games?)
or maybe A will try to find an agreement with B to make C loose?
or maybe A,B,C will prefer to remain quite and always everybody plays 1?

a very nice puzzle anyway

[Nsof]

[Chuck]

Someone playing the equilibrium strategy might be willing to risk taking a loss in order to have a chance at a gain.

If someone insists on playing the 1/(2^n) strategy and the other two player catch on then they'll soon each be taking half the money.

[WuTheFWasThat*]

Ultimately, as your opponents are as intelligent as you are, return will be zero no matter what. I believe almost everyone can agree with this. This clearly implies that there really is no winning strategy. However, if we assume no collusion or, rather, no memories of previous games, wavebasher deserves credit for first coming up with the best strategy. But, in the end... let the luckiest man win.

[JeffyBoy*]

The only thing sillier than this puzzle is the fact that I have chosen to waste precious time solving it.

Look, the first rule of winning is, to the furthest extent possible, DONT LOSE. The rules of this game provide one, absolutely guaranteed way to never lose. That is to choose the number 1. Every single time. Any person sitting down to play this game would be have to be a total nudnik to do otherwise, and the parameters of the puzzle forbid this:

[Tomkat]

[Chuck]

The solution is up, but it really tells us how two players can keep a third from gaining an advantage.