Hi,

So imagine a 100 coin game.

The game has 3 players. The players simultaneously each pick a distinctive integer between 0 - 100. The players get the amount of coins equal to the amount of numbers closest to his or her number.

So player 1 picks 10, player 2 picks 11, and player 3 picks 12.

Now player 1 gets 10 coins (1-10), player 2 1 coin (11) and player 3 89 coins (12-100).

How would you proceed in finding out what the nash equilibrium of this game would be? Furthermore, what would happen if first player 1 decides, then player 2 then player 3?

Can you explain this a bit more to avoid any confusion?

If they select a<=b<= c in the order of lowest to highest then they get what?

Or give more random examples with more numbers.

Are you giving the first guy the distance to 0, the second guy the distance to the first guy and the third guy (in order of lowest to higher i mean) the distance to 100?

Your example is kind of singular ie 10,11,12 is crazy tight for random example to make it hard to imagine what you meant with 100% confidence.

I like the attention to detail. OP?

The OP is unambiguous. For each number that is closer to your chosen number than to either of the other two chosen numbers, you win a coin.

This type of problem is very popular in game theory. There are many applications and examples. One is the theory of voting.

Think of there being a spectrum of opinions on a subject. Say there are 100 voters each with a different view. Label the views numerically 1-100. Candidates take a "position" on the subject reflected by a specific numerical label. Each voter then votes for the candidate whose position is closest to their own. (Ties are split in theory.)

Suppose there are three candidates and they take positions 40, 65, and 80. If I didn't screw up simple arithmetic, Candidate 40 will receive 52 votes (voters 1-52), Candidate 65 will receive 20 votes (voters 53-72), and Candidate 80 will receive 28 votes (voters 73-100).

Anyway, these games have been well-studied in game theory.

Sure but its interesting how you just made it a lot more clear for likely the majority of people with the addition of a couple of words. It is still left to know if the coins accumulated by all 3 are always 101, if the equidistant ones when they exist are split or multiply counted or not counted at all because they strictly are not closer to any one alone when equidistant to 2 (the example doesnt offer such opportunity to see what happens there)!

Yes it may be strictly self sufficient if one is super strict in the definition but it doesnt hurt to be extra safe. You include more people in the discussion that way and the thread doesnt spend 4 days inactive if some clarification is introduced.

Yes, there is this contradiction in the OP. If nobody wins in the equidistant cases then it is not necessarily a 101 coin game.

Assuming there is a continuous version, where they choose from 0 to 1 and equidistant are awarded to all sides not split, to avoid any ambiguities and harder but not essentially illuminating anything math, then lets propose each selects 0.25, 0.5 and 0.75 with 1/3 chance each. Can you exploit that strategy if you are the third guy say and the other 2 play like that?

Havent tried yet anything rigorous yet just proposed that as a starting trial.

Otherwise start from assuming and 2 have 2 distributions f1 and f2 and try to exploit with an f3 and see what this tells you. You can

By symmetry all 3 must have the same strategy right?


It is not clear why the order they play would matter either. I mean the information of what they did is not available or it would be a straightforward math problem so why does that matter?


We may want to consider splitting the equidistant too in case this goes to voting problems or whatever system that all value to be awarded is fixed. That may alter things a bit in the proposal i made to make it a continuous distribution strategy to avoid the split problems (ie when they choose the same which will happen very often actually that way suggested). On the other hand it may not matter to make it continuous it is not obvious without work if the avg comes the same.

Try also this. Say the first 2 choose uniform from 0 to 1. What can the 3rd do to defeat that?

Or rather make the suggestion points a,1/2 and 1-a and the probabilities to be there p, 1-2p, p respectively. With a, p to be determined.

Something similar to the Hotelling game with 3 players it would seem;

https://www.econstor.eu/bitstream/10.../724875824.pdf

http://econpapers.repec.org/paper/ul...013_2f1745.htm (try external pdf link there)


https://en.wikipedia.org/wiki/Hotelling%27s_law

If it's a 100 coin game shouldn't you be picking numbers from 1-100, inclusive? Also, I would assume ties get split so that all 100 coins get distributed every time.

It should be clear that a non-mixed strategy can be exploited. So we're looking for a mixed strategy. I'm guessing the solution is a Uniform mixed strategy that picks each of the 100 numbers with equal probability, 1/100. I suspect any other probability distribution that has a "bump" in it can be exploited along the same lines that a non-mixed strategy that picks the same number every time.

If player 1 and player 2 both play a Uniform mixed strategy, can you think of a strategy player 3 could play that would exploit players 1 and 2? i.e. a strategy where player 3 expects to win more than a third of the 100 coins?


PairTheBoard

Choosing 50 would win over 50 coins on average against 2 uniform opponents.

So much for that idea.

PairTheBoard

Are people not understanding that you want to "crowd the middle"? I cannot believe that a uniform distribution over the entire range can possibly be part of an equilibrium set of strategies.

Work through the successive moves game if you need further insight into these types of games.

Depends on what happens when both players pick the exact same number. If they both wind up rat****ing each other when that happens then you could easily win by picking 0.51 each time.

TomCowley crushed my "Uniform" idea with his post. It's fairly easy to see that he's right. If Uniform were optimum then there should be no strategy that could exploit two players playing Uniform.



PairTheBoard

Yes this is why i had already moved to a different but still symmetric distribution around 50 (or 1/2 in the Hotelling type version i tried).

If however now each one of the 2 picks 0.5 some fraction of the time say 1-2p and a or 1-a some fraction p each then the 3rd guy that tries to go to a bit above 0.5 or a bit below always will be often sandwiched between the 2 scoring way below 0.3 these times and it might start looking ok now (or the continued distribution version that may not be going all the way to the corners).

You want to go near the corners (but not at the corners) some times to eliminate the exploitation of the 3rd guy always going a bit above 0.5 or a bit below and easily capturing the vast majority of that 1/2 side (eg like some 0.50-epsilon type thing always). Now you have defended against that. You have also avoided splitting the same 1/2 if both first and second had selected 0.5 at the same time.

Just read the papers i linked also. Give the voters or consumers some utility function that goes like minus the distance from each vendor ie -c*|x-xi| where x is the location of the consumer and xi , ie x1,x2,x3 the 3 positions of the 3 "vendors". Then assign each vendor a payoff from such utility profile population.

But you give one of the guys an incentive to scoot closer to the center.

This element appears to make the game ill-posed. For example, in a two player game, the obvious strategy is to pick 50 all the time because you've protected half of the coins no matter what your opponent does, UNLESS he also picks 50. In which case... I don't know what happens.

With three players, your opponents would need to cooperate with each other (one goes high the other goes low) in order to exploit you if you just picked 50 all the time.

Yeah. The players don't choose randomly. They would play GTO and all pick 50 causing a stalemate every time. There was no rule specified to fix this.

Say instead you let players take turns. This causes a problem too. So player A picks 50, player B tries to pick 50 but is told it is taken so he picks 51, player C ends up picking picks 49. Player A loses big.

Just specify that ties are split as whosnext suggests. In a 2 player game where they both pick 50 they both get half of each coin, adding to 50 apiece.




PairTheBoard

If 2 players picked 50 every time (ties split), the 3rd player would exploit them by playing 51. The 3rd player wins 50 while the other 2 split the other 50 for 25 apiece.

PairTheBoard

Using masque's continuous model, suppose 2 players both choose randomly according to the probability density p(x). And suppose the 3rd player chooses according to pdf q(x). How would you calculate the EV for the three players in terms of p(x) and q(x)? Some kind of integrals?

PairTheBoard

As I said, these types of problems have been well-studied. Don't get hung up on the possibility of ties. It is not the intent of these problems to worry about ties. Think of any tied "voter" as splitting her vote between the candidates who are equidistant from her view.

"Split votes" are not only germane to candidates who take the exact same position. They can occur in any discrete game like this. Suppose the candidate positions are 20,40,60. Then the voters at 30 and 50 "split" their vote between two candidates.

P.S. In case this is of interest to anyone, I believe that OP may have posted this in advance of a job interview. He heard this problem may be asked in the interview so wanted to get some thoughts from the forum ahead of time.

Typically the interview would ask the successive move discrete version of the problem first. If the interviewee aced that fairly easy question, then they ask the simultaneous move discrete version.

They do not expect the interviewee to completely solve that version on the fly in the interview, but the interviewers are interested in how the interviewee thinks about the problem.

Thanks. I expected that would be the assumption that would be applied, but I missed that it was already stated.

Are we just counting wins or are we counting average coins?

I'm sure they have been. But I've not seen a solution, so I'm treating it like a puzzle to solve.

Ties seem pretty relevant to the two player case. So it at least appears that it could be relevant to solving the problem.

I've heard a fair number of these interview problems, but I have not heard this one before.