[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.