[smeatish]

OK, now add a third hot dog stand. What's the nash equilibrium now?

With 3 hot dog stands, they have an incentive to spread out - if you're in the middle of the other two, then you move to the outer side of one of the other two to capture everyone on that side of the beach. This repeats - there is no stable equilibrium.

[eric-hu]

Assuming the 3 hot dog stands start out with spacing to allow for equal coverage, their positions are -2/3, 0, 2/3. Everyone gets 2/3, 1/3rd on each side.

The two on the outside have an incentive to move towards 0 because they can take more market share without losing any. The one in the middle does not want to move to either outside area until moving means he can have more market share than what he currently has.

If the rightmost player decided to move inward from 2/3 to 0.5, he'd have 0.75 market share (out of 2). The middle player would have 1/3 + 1/4 = 7/12 or 0.58. It still wouldn't be in his interest to become the rightmost player, as his upper market share limit would be 0.5 (a little less).

However, there's already an incentive to move to the right player's location, causing the locations to be (-2/3, 0.5, 0.5). The left player gets 1/3 + (2/3 + 0.5)/2 = 1/3 + 1/3 + 1/4 = 11/12 or 0.91. The remainder, 1.09, is split equally among the other two to 0.545 each. Only the left player has incentive to move at this point, since each of the right players stand to lose the right-side market by moving inward, or losing half the left-side market by moving outward.

The leftmost player has incentive to move inward now, and can do so until he takes enough market share from the other two that one of them can move to him and gain more. If they all did this and ended up at 0, they'd again have an equal 2/3rds. However, anyone can move slightly to one side or the other and increase his market share to nearly 1.

Looks like you're right. I would say there's "equilibrium behavior", though--the 3 players will oscillate between the boundaries [-2/3, 2/3], with someone frequently taking the same position as another.

[saurik]

> If the rightmost player decided to move inward from 2/3 to 0.5, he'd have 0.75 market share (out of 2).

This move would not have been made by theoretically optimal players: if he had moved from 2/3 to 0+ instead he would have had 1 market share (out of 2).

> Only the left player has incentive to move at this point, since each of the right players stand to lose the right-side market by moving inward, or losing half the left-side market by moving outward.

The middle player actually has an incentive to move to the center of the board for the same reason that the original player in the two player case had an incentive to choose the middle of the board (despite having monopoly).

> If they all did this and ended up at 0, they'd again have an equal 2/3rds. However, anyone can move slightly to one side or the other and increase his market share to nearly 1.

In this configuration the two players on the outside would actually each have ~1, leaving the player in the middle ~0. If we call these positions using formats like 0-, 0, and 0+, the 0 player will move to 0++, causing either the 0- player to move to 0 and the 0+ player to move to 0--.

Now we have 0--, 0, and 0++. Now, the 0++ player will move to 0+, and the 0 player will move to 0++, leaving the 0-- player to move to 0-. The 0+ player will move to 0--, the 0++ player will move to 0, and the 0- player will move to 0+. "Finally", the 0-- player will move to 0-.

I am pretty certain that this algorithm does not terminate.

[eric-hu]

Interesting notation :)

I agree that the starting move I proposed was sub-optimal. That was an arbitrary move I chose to get the idea in motion.

That algorithm is optimal in a greedy sense--going for the most immediate gains with no memory or foresight. I think this is where the game starts failing as a model for reality. The optimal game algorithm would probably have enough look-aheads to force the other players to the other side, and then take the 'majority' 1+ by moving to that same side, but closest to the 0, giving it 1 + an infinitesimal market share on the other side.

In reality, there are moving costs and one does not simply "win" when holding a majority market share. Perhaps a redefinition of the game is in order?

[gjm11]

I did a little simulation. Start the vendors off in random places. Each tick, pick a random vendor and move it to its optimal place (either just left of the left-hand other one, or just right of the right-hand other one, or half-way in between; I assume for convenience that some second-order effect makes the midpoint best when you're between two others, and when putting a vendor in a new "outside" position I put it 1% of the way from the old "outside" vendor to the edge).

The resulting evolution settles down quickly to a situation in which all three are very near 0.5, and every time the middle one gets the chance to move it does so (to be just on the other side of whichever of its rivals has more space on the other side). If you plot a graph of this, you get a sort of braided effect, with the braid never getting very wide or moving very far. So it's kinda-sorta stable even though (necessarily) the vendors keep changing places.

With n>3, all sorts of more interesting things happen. For instance, for n=4 the state of the world is usually as follows. You have a cluster of (usually) 2 vendors near a (<1/2) and another near b (>1/2). The outermost vendor in each cluster is happy where it is; the inner ones will jump to just beyond the outermost of whichever cluster is further from 1/2. This means that the clusters tend to be equally far from 1/2 (because the nearer-in one is preferentially jumped to) and tend to move outwards (because a jumping vendor always jumps to just outside a cluster). But this situation can break down in two ways. (1) A vendor jumps from one cluster to the other, so we have 3+1 instead of 2+2. Then the now-isolated vendor, on its next move, will join the other cluster; we now have 4+0. Now what happens is that cluster moves en bloc towards 1/2, at which point it typically splits in two. (2) The two clusters get far enough apart that a leap into the middle becomes favoured. Actually, in my simulation #2 never happens because #1 always happens first. For larger numbers of vendors, though, you get a kinda-similar situation (two clusters, one on each side, slowly moving outward) but the number of vendors in each cluster is large enough that #2 can happen before #1 does, so sometimes you get one leaping into the middle. (As the number of vendors gets big, this becomes the dominant kind of transition, and the overall effect is that generally the vendors are quite evenly spread.)

A more realistic simulation might give quite different results, but I'm at work right now :-).

[eric-hu]

Interesting simulation. The braided behavior sounds like the 'equilibrium behavior' I mentioned earlier. Does this simulation also allow for taking another player's exact location, forcing a split of their market share on both sides? I imagine that's a subtle but game-changing move.

For the higher vendor numbers (3+), did you notice similar behavior when the vendor parity was the same (i.e. all even or all odd)?

[gjm11]

No, it doesn't allow two vendors to be in the exact same spot. The amount of trade that gets you is always exactly half-way between being just to the left and being just to the right, and can therefore only be the best option when all three of those are exactly equal, so I don't think it makes much difference.

I wondered whether parity would be a big deal, but -- purely qualitatively and by eye -- it doesn't seem like it is.

[eric-hu]

Very interesting observation.

In the 2 player case, not allowing for parity means that equilibrium would never be reached. The simulation as you programmed it would approach equilibrium as time goes to infinity, though, so I guess your model works about as well as one with parity, and is simpler. Nice.

[saurik]

I am reasonably certain (but would love to learn more) that a complete description of the strategy used by players in that game is as follows:

1) when squeezed, the middle player will move to just "outside" of the opponent further from a wall 2) otherwise, the player in the middle prefers to be in the middle of the middle (to hedge against new players or take advantage of stupid existing players) 3) an outside player in a good position will move to be directly next to the middle player 4) an outside player in a bad position will temporarily choose to be the middle player, and then /immediately/ choose between strategy #1 and #2

The only rule in this situation that causes player to not be directly next to another player is #2. The two outside players will then either a) invoke rule #3 to put all three players next to each other or b) invoke rule #4 to move all the players closer together. The middle player, when squeezed, just uses rule #1 to move next to another player.

In essence, it is my belief that there will be no stable configuration of the players for this game (unlike the two player case, where "next to each other in the center" is stable), but that at all times the players will be clustered together while they shuffle themselves.

[philbo]

I think the strategy would depend on the cost of moving. If moving has no cost associated with it, then I see the game playing out as you describe. But if the cost of moving repeatedly becomes prohibitive, players would be more likely to adopt a strategy of equidistant equilibrium.

[esrauch]

With 3 hot dog stands in 3 dimensions they would still be very close together. This trivially holds true as we are living in an N dimensional space and there are N or less stores.

[vash_stampy]

I think a more generalized solution will still work with this problem. When there's no center (ie beach extends infinitely), the hot dog vendors would choose to be close together for the simple fact that any distance between the two they share equally. Both vendors would seek to minimize this because any distance outside they claim completely for themselves.