Discuss Least Unique Game here

[Neo]

http://www.greylabyrinth.com/puzzles/puzzle.php?puzzle_id=206

Enjoy!
_________________
_{Ad Astra}

[BraveHat]

Seems to me the best strategy is to continually choose 1 and then every once in a while, choose another integer.

We know that if you choose one, there are only four possible out comes: you 1 and the other two 1, you and another 1 and the other a higher number, you and the third person 1 with the other a higher number, and you 1 with the others a higher number. Out of those four, you win with the last one, so you have a 1/4 chance of winning each time you play a 1. With any other integer, you have a 2/9 (or lower)chance of winning, which is slightly lower. So, keep playing the odds, and every once in a while, play a different integer so that your intelligent opponents will not be able to predict what you'll play.

[Chuck]

If I play mostly 1 then another player might catch on and start alternately playing 1 and 2 hoping that the third player will catch on and start alternating between 2 and 1. If they manage that then one of them will always win. I'd then have to change my playing style, probably to alternating between 1 and 2 myself to force the other 1 and 2 player to abandon his strategy.

[Bicho the Inhaler]

The challenge is to figure out exactly with what probability you should play each positive integer on every turn. Yes, I see why you'd play 1 most of the time with a smaller probability of choosing other numbers, but unless you're careful with your probabilities, the other players could make you lose money over time.

Chuck, I'm pretty sure you can prevent anybody "catching onto" your strategy and taking advantage of you if you play appropriately (assuming the other two players don't form a pact against you, which is forbidden by the problem), but I don't have a solution yet.

[Middle Aged Guy]

I'm pretty sure that since the other players are "as rational and capable as you", then whatever strategy you use, they will find the appropriate counter-strategy, so in the long run, everyone will come out even.

But you could try something like this ...

Since the game is repeated indefinitely, it doesn't matter if you lose the first thousand (or ten thousand or hundred million ...) games if that will lead to a strategy which will give you the slightest edge in the long run. So you could use however many turns it takes to estabish a code (say using 1=a, 2=b, 3=c, ... ). It wouldn't take one of the others too long to realise what was going on (... why else would you be using the numbers 1 to 26? Any winning strategy would be based on using 1 and 2 rather than any higher numbers)

Once your code has been used to establish communication with one of the other players, then (as Chuck has suggested), the two of you can collaborate to ensure that in each game one of you plays 1 and the other plays 2, and then you can freeze the third player out. However, this only works till the third player also cracks your code (...or spots any pattern you might be using). The third player can then duplicate your plays and force you to abandon the partnership that has been established!

[mikegoo]

So what happens with a 2 way tie for lowest?... is the money returned or does the house take it or is it a 2 way split?

[Chuck]

The unmatched player would be the winner if two tie.

[mikegoo]

Oh yeah...lowest unique...got stuck on the lowest part (even after reading it 4 times figuring there was something I was missing)

[Chuck]

Even though players can't communicate with each other, I don't see how it would be possible to prevent informal pacts from forming based on playing patterns. The puzzle says the numbers are revealed but doesn't say whether or not we're told which player chose which number. It would make playing patterns harder to detect if the players weren't told who picked each number, but not necessarily impossible. Players could make decisions based on suspected patterns.

If the other two players are playing alternating 1,2 and 2,1 then there's no way I can ever win if I stick to some probabilistic strategy. Each of them would win half the time if I did that. I'd have to try to break their pact by doing the same thing that one of them is doing which would cause the other player to always win. The player I'm duplicating would have to break the pack or get nothing for as long as I'm copying him. He might stick to the pact for awhile hoping that I'll give it up and start duplicating his partner's choices but I can't do that because I'd lose credibility. I'd have to stick it out. Eventually the player I'm copying would have to start copying his partner and I'd start winning. The player now being copied would then have to start copying me to force me to switch my strategy.

Eventually we might settle into a pattern in which each of us wins the whole $3 every third round. The switching player would not win anything in the round in which he switches but would expect to win the following round as the player he copies switches away from him. It would do the third player no good to break the pattern since he can't win on that round anyway and expects to win two rounds down the road. If anyone breaks the pattern then the other two players can go back to 1,2 and 2,1 leaving the pattern breaker with nothing until he reestablishes the pattern.

[LoudmouthLee]

This is a question of EV (Expected Value). Now I'm glad I logged a whole lot of poker playing...

Let's pick an arbitrary large number, say, 1 million. The only way you're going to win this round is with the chance that your two other opponents both pick the same number.

In my opinion (and I have 0 mathematical basis for this right now), the correct answer is to ALWAYS pick #1.

If you pick #1, and your opponents pick #1, it's a 3 way draw.
The only way you can possibly LOSE your dollar is if one player picks one, and another player picks any other abitrary number.

If you continue to pick #1, soon your opponents will begin to pick arbitrary numbers.

Maybe someone with more computer or mathematical ability can help me here...

Player 1 picks the #1 all the time.
Players 2 and 3 pick #1 75% of the time, and #2 25% of the time.

I wonder who wins...
_________________
-LmL

I'm sorry. I have no desire to talk to you.

[Chuck]

If picking one every time is good for me then it should also be good for my opponents so they should also both pick one all the time. But if I see them both picking one all the time then I should switch to playing two and get all of the money.

[LoudmouthLee]

so, prisoners dilemma?
_________________
-LmL

I'm sorry. I have no desire to talk to you.

[thok*]

I wouldn't be surprised if the correct answer was a strategy that limited itself to simply picking 1 and 2.

It also should be clear that if all three people pick a "best strategy" that by symmetry they should all expect to break even in the long run.

[Chuck]

In a two player game, I could pick a mixed strategy that, if played every round, would guarantee me at least my fair share in the long run no matter what my opponent did. That's not the case in this three player game. Due to symmetry, I know my fair share is $1 per play. If one of the other two players always chooses 1 and the other always chooses 2, or if they alternate 1-2 and 2-1, then no mixed strategy will get me anything. I have to depend on their greed and their rational play to get me anything. If they notice that I'm playing some such mixed strategy they could always choose some mix of playing 1 and 2 that would get each of them $1½, on average, and nothing for me. Without communications it might take them awhile but it will be a long game. My strategy would have to depend on what they've been doing in recent rounds.

[dnwq]

The game is zero-sum and symmetric. Does that mean that the best strategy (whatever it is) will necessarily lead to the draw?

Edit: Drawing the normal form, there is (surprisingly) no reason to favour playing 1; the main point is that it is only ever beneficial or no-change whenever your opponents play the same number. Otherwise you always lose $1.

[Chuck]

I suspect that some pattern of play might form in which player take turns winning. If everyone plays the same number every round each would get back his $1. There would be a great temptation to pick another number and take it all. If the players were taking turns winning it all then there would be less temptation to change. You wouldn't change when it was your turn to win and you couldn't win immediately by changing. You'd just change which of the other two players won. They would then have the opportunity to punish you by switching to one of them alternating 1,2 and the other alternating 2,1.

What I have in mind is a three round cycle with players playing:

1st player: 1 1 2
2nd player: 1 2 1
3rd player: 2 1 1

You can't defect when it's your turn to play 2 because you'd give up your win and get $1 instead of $3. If you defect when you should play 1 then you cause someone else to win out of turn and you still get nothing.

Without communication it might take awhile to arrange this. But maybe not too long if the other players reason as I do.

[marcusI]

Judgeing by this discussion, I'd choose three. The odds are good that the other two would both choose 1 or 2 (most likely 1). My three would have at least a 50% chance of winning the first game.

[Chuck]

The other players are assumed to be as rational as you are, so if you come up with a strategy to get more than your fair share they'll be considering using it too. If you choose 3 and one of them also does so then you get nothing.

[marcusI]

[dnwq]

[marcusI]

I thought if I won the first hand it was over.

Okay, re-read the puzzle.

Now I get it. An unending game we are not allowed to quit. Money doesn't
matter. The three of us are in hell. There's no way to win or lose. Our
best strategy is to band together and try to escape.

Definately similar to the prisoners' dilema as LoudmouthLee pointed out.

[Chuck]

Indefinitely doesn't mean forever. We just don't know when the game will end. Maybe we can order pizzas while we play and take breaks for showers and changes of clothes once in awhile, otherwise it really would be hell.

Rational play might always lead to the same deterministic decision but if that decision is to toss coin or roll dice to decide what number to play then we won't always play the same number. If we're basing our decisions on what the other players have done in recent rounds then we'll also make different decisions.

[A-man]

Gentle please...my first post!

I agree with MarcusI's theory on always selecting 3. If the other two players randomly select combinations of 1 and 2 then half of the time they will match each other and 3 will win. Even after they catch onto the strategy what number would they want to switch to? Switching to 3 simply guarentees that they would not be unique. Switching to 4 is greater than 3 and offers no help. Too simple?
_________________
Men are apt to mistake the strength of their feeling for the strength of their argument.

[mith]

Too simple.

Assuming the other players can't communicate even though patterns, they can still play a mixed strategy which minimizes your winnings (and therefore maximizes their own). Against "always pick 3" that strategy is:

P(1) = 1/6
P(2) = 1/6
P(3) = 3/6
P(4) = 1/6

You would then expect to win:

3*(P(1)^2+P(2)^2+P(4)^2) + P(3)^2 = 1/2

Clearly less than the 1 you paid.

You can actually generalize this for any single number strategy (probabilities of 1/(N+3) or 3/(N+3) as above from 1 to N+1, with your expected winnings given as 3/(N+3); so if you insist on picking the same number, you're better off with 1).

Generalizing it to work against a mixed strategy is messy - I think adding the anti-single-number strategies (weighted) might do the trick if not for that last bit in each. It doesn't matter in the always-3 case whether the mixed strategy calls for 4 or 5 or any other higher number - if they both pick higher than 3, you win anyway, even if they aren't the same. But as part of a bigger picture, what they pick does matter.

Assuming that picking the lowest number for that part of the asn mixed strategy is best, you can get a recursive strategy:

S1 = (1,0,0,0,...)
S2 = (.75,.25,0,0,...)
S3 = (.61,.34,.05,0,...)
S4 = (.54,.36,.09,.01,...)
and so on.

The basic idea being that S2 beats S1 (where you only pick 1), S3 beats S2 (and, hopefully, any mixed strategy of 1 and 2 you pick), and so on, though it's far from rigorous. And even though it looks like it converges, it doesn't necessarily converge on a strategy for "you", given that it comes from two players trying to minimize the third's expectation rather than a single player trying to maximize his own.

But, even with all the hand waving there, if I had to guess, I'd say that carrying that recursive process out to the limit at infinity, you'll get a mixed strategy which does no worse than break even against any mixed strategy your opponents use (assuming they use the same mixed strategy, of course), and so it is "optimal" in that sense. I wish I had time to prove/disprove it...

[ChienFou]

How nice to see mith again ::waves hands::

I have a nasty suspicion that the mixed strategy to adopt will be 1 n times as often as 2 n times as often as 3 n times as often as 4 ... and if we take the 112 cycle we can see that 1 is twice as often as 2. I think this might be true if we have a large number of players, so we need to increase n to get fast convergence.

Aarghh! is it one of the "e" problems really well disguised? (Your optimal strategy is to do something e times as often as something else.)

End of rumination. cheers CF

[A-man]

OK. I now see why always choosing 3 (or 2) can be a losing strategy, and choosing 1 may be not better than break even. But in the absence of collusion (three players that will never meet, etc.) consider this scenario; on the first round player A chooses 1, player B chooses 1 and player C chooses 100. Player C wins. What does player A and player B make of player C's choice? Probably confusing at best. But why would player A or player B now ever choose anything but 1? What would be their incentive to choose 2? What would be their incentive to choose 100? Why would either player A or player B be the first to choose something other than 1? And if that is the case, why would player C not always choose something other than 1?
_________________
Men are apt to mistake the strength of their feeling for the strength of their argument.

[Chuck]

If player A and player B never switch away from playing 1 then they'll never get anything and they know this. If I were player A I'd start playing something other than 1. It wouldn't hurt because I was already getting nothing. Then C would be getting nothing and B would get all of the money. I'm hoping that C would find this unacceptable and start playing 1. He'd get nothing but the idea is for him to make B get nothing, find the situation unacceptable, and start playing something else. Then when B changes I'd be back to getting nothing and we start the cycle over again with C getting all of the money.

The player who switches gets nothing immediately but he's hoping to eventually get something by forcing the player who was getting something but now isn't to change because any change might eventually get him something again which is better than getting nothing forever.

[A-man]

Say the first few rounds are 1 1 100. B gets frustrated more quickly than A so the next few rounds are 1 2 100. B is now really frustrated and C is starting to get frustrated and A is living the high life and has no reason to change. The question now is whether B wants to screw A or C. Why would he want to screw C? C is not winning anything! When B is totally frustrated he goes after A and the next few rounds are again 1 1 100. It appears that if A and C are patient enough that B will simply alternate losing to each. Does emotion start playing into this situation more than pure logic?
_________________
Men are apt to mistake the strength of their feeling for the strength of their argument.

[Chuck]

If player B goes back to playing 1 then they're right back where they started except that player B has demonstrated a willingness to switch early. Player A will have less reason to change than before since player B has shown a willingness to do so. If player B switches again then player C has less reason to switch because player B switched back last time and might do so again. For player B to get anything he really needs for player C to switch. He needs to accept getting nothing until C switches. C would know this and realize that he must switch.

The players want to maximize their money, not punish each other for noncooperation. They should punish each other only to convince each other to change playing style, never for revenge.

[A-man]

'punish' is a much more appropriate term then 'screw' (I was at a loss for words - my apologies!)
_________________
Men are apt to mistake the strength of their feeling for the strength of their argument.

[Icarus]

[Chuck]

Since both other players are rational and don't want to always tie each other, they might each decide to toss a coin or roll a die to determine what they do next. Then they won't automatically keep choosing the same number. One of them would have to let the other win the next round but that's better than sticking to a pattern that always loses.

[Arkive]

With players of equal intelligence, and an indefinite number of turns (or the assumption thereof), there is no strategy one could produce that would yield a theoretical advantage. Everyone's obvious choice at the onset of this game becomes this:

Minimize losses.

The puzzle now becomes not trying to figure out how to beat the other two players, but how to reach an understanding with the other players as quickly as possible. Any player of reasonable intelligence would understand that cheating the agreement would only award them a trivial amount compared to the total exchanged in the long run.

With that in mind, any strategies involving numbers chosen below 10 would only lend suspcion to whether that person was trying to "win" the unwinnable. Knowing that, I would choose a very large number, perhaps "56,782" (any large number will do). Then from that point, increment that number by one, until the game is halted, or one of us dies from old age. By choosing a large number, and incrememnting it, the players quickly realize that you are just trying to "break even".

There is a chance another player would adopt this same theory and also play a large number first. Since all players doing this have visibly agreed to split the pot until completion, whatever person played the highest is the one who should continue incrementing as going lower only goes to show an attempt at "winning". There might be some confusion, but within a very short amount of turns (~3), all players *should* be on the same increment.

The only unironed detail might be trying to let whatever folks didn't win early on, cycle a win or two in to make sure everything was truly balanced at the end (if there is one). However, doing so would only raise suspicion that someone is trying to win. I see no system for awarding wins to equal the footing that wouldn't draw suspicion and potentially dork up the whole arrangement. The best hope is that by doing this, you make the game so boring to anyone viewing from the outside that they will stop the charade as soon as possible and let you move on with your existance.

[A-man]

If the goal is to 'minimize loses' then I believe the game will quickly evolve to each player selecting the number 1. There would be no need for complex rotations of numbers or taking turns incrementing choices, etc. Just always choose 1 and enjoy the pizza!
_________________
Men are apt to mistake the strength of their feeling for the strength of their argument.

[jadesmar]

[A-man]

You missed my point. As I stated if the goal was to minimize loses (which is something very different than winning) and every player is just as clever as each other, then why fight it? Why bother to rotate winning - just take every turn as a draw.
_________________
Men are apt to mistake the strength of their feeling for the strength of their argument.

[bhoogter]

It does seem that 'break even' is the only way long run approach, given the symetry. It also seems that picking 3 or higher is more-or-less the same, just betting on your opponents getting the same value. Also, any best distribution pattern would be equally discovered by my opponents.

It seems like the thing any two players would want to do would be to lock out a third, so that they would receive, on average, 1.5 / round. The easiest case is for one to pick 1, and the other 2. Alternate these, depending on the third player, which is always blocked and will never win under this scenario.

However, what if you're the third man out? We need to break up the team. What's the best (er, only) way to do this in this scenario? It seems like greed. If player A and B are teaming up against C, then C just has to make A always win. B will then quickly break this agreement because he isn't winning anymore. B would then want to block A from winning. He couldn't block C, because at this point, C is saying, "You're not winning a thing until you help me. Not at all." B is at this point forced to help out C or never win again. B & C effectively form a team. A blocks one of them.

So, basically, recogizing patterns played, and a lack of communication, block the player with the lowest net return until they form a coallition with you, at which point, you can make up money until you're even again. The other player will always eventually be forced to help you because they want to win (the stated object of the game). They will help you until the blocked player blocks the player with the lowest net return of the other two. Continue this, and you end up with symetry

[Death Mage]

I simply wouldn't wager money on this silly game.

But that hardly helps solving the "puzzle", now does it?
_________________
* These senseless ramblings brought to you by Insanity™. If you just can't figure the dang thing out, it must be Insanity™.
[YOUR AD HERE!]

[KanaPolak*]

Anyone wanna play!?!

I'll pick 3 everytime, assuming no colussion, I win.

A is me, B is you, C is the third dude.
A always = 3
cases:
B>3, C>3 I win
B<3, C<3 I win half the time(good deal)

assuming you and C are not idiots, you will not pick 3 or you will lose to the other that pick '1' or '2'

eventually you'd figure out that you can't beat a '3 player' and both join...

Who would like to play?

[A-man]

That was also one of my first thoughts, but was quickly corrected. The other two players alternating between 1 and 2 will lock you out. That is not collusion, just common sense.
_________________
Men are apt to mistake the strength of their feeling for the strength of their argument.