Sellers in a square town

Sellers on a street worked out Harold Hotelling’s game of 1929 exactly. Customers are spread evenly along a street, each walks to the nearest stand, and each seller picks a spot to win as many customers as possible. Two sellers end back to back in the middle, each with half the street. Three sellers have no arrangement in which all are content: whoever is in the middle is squeezed to nothing and jumps out, and the chase never ends. Four sellers settle in pairs, two at a quarter of the way along and two at three quarters, each with a quarter of the street.

A street is a town of one dimension. Real customers are spread over an area, and the same game on an area is the question that essay left open. This one takes the simplest area there is — a square, with customers spread evenly over it — and computes each seller’s market exactly, so that whether anyone wants to move can be decided arrangement by arrangement.

A market is a cell #

In a town, the customers who walk to a given seller are the ones closer to that seller than to any other, and that region is the seller’s Voronoi cell — the plane divided by whoever is nearest. Between two sellers the dividing line is the perpendicular bisector of the segment joining them, and a seller’s cell is the part of the square on its own side of every bisector. So a cell is a convex polygon, cut from the square by at most one line for each rival, and its area can be computed exactly: start from the square, clip it by each bisector in turn, and add up the area of what is left. Sellers standing at the same point share their cell equally.

A seller’s best reply to the others, the notion on which every equilibrium in this subject is built, is the spot that maximises its cell’s area with the others held fixed. The figures find it by evaluating the area on a fine grid of spots and then refining the best one by small steps until no step improves it. An arrangement is a pure equilibrium exactly when every seller is already at a best reply, and the natural measure of how far an arrangement is from one is its regret: the most that any single seller could gain by moving alone, as a share of the town. Regret is nought at an equilibrium and positive everywhere else.

That measure is what the search uses. Starting from random arrangements, it nudges the sellers about and keeps any change that lowers the regret, shrinking the nudges as it goes, and reports the calmest arrangement it finds. A search of this kind cannot prove that no equilibrium exists. It can find one if there is one in reach, and report how close it came when there is not.

Two sellers settle at the centre #

Put one seller at the centre of the square and ask where a second does best.

Anywhere other than the centre, the newcomer is on the smaller side of a bisector: the line halfway between the two sellers cuts the square so that the newcomer’s piece is smaller than the rival’s, because the centre of a symmetric town is the point that every line through it halves. At the centre the two share every customer equally. So two sellers at the centre are an equilibrium, and the search confirms it with regret nought.

The argument is the street’s argument in two dimensions, and it has a clean general form. In a town where customers are spread with any density, call a point a centre if every straight line through it splits the customers into two equal halves. With one rival at such a point, any spot a newcomer chooses lies on one side of a line through the centre — the bisector between them is parallel to such a line and on the newcomer’s side of it — so the newcomer can have at most half. A square, a disc, any centrally symmetric town has a centre and two sellers settle there. A town with no such point, a triangle for instance, has no point that every line halves, and there two sellers have no pure equilibrium either: whichever spot one takes, the other can take a spot just beside it on the heavier side. Two sellers need a centre, and on a street every town has one — the median. That is why the street’s answer for two sellers was so tidy, and why it does not carry over to every town.

Three sellers never settle #

On the street three sellers fail because the middle one is squeezed. In a town there is no middle in that sense, and it is natural to hope that three sellers might share the square comfortably — at the corners of a triangle, say, each with a third of the town. The hero shows the calmest arrangement the search found, and it is not calm: one seller can gain 4.21 per cent of the town by moving, in this case to a spot right beside a rival, taking a slice of that rival’s customers.

The triangle is the obvious candidate, so it is worth sweeping it on its own.

A small triangle leaves the outskirts to be taken: a seller who steps outside it, away from the other two, gives up a sliver of the middle and gains a whole side of town. A large triangle leaves the middle open: a seller who steps inward, towards the centre, takes customers from both rivals at once. The regret falls as the triangle grows from a cluster, reaches its least, 3.87 per cent, at a radius of 0.22, and rises again as the corners move towards the edges. The two temptations trade against each other and never both vanish.

Drawn as a map of where the third seller does best, the temptation is visible. The share is highest in a ridge running towards each rival, and the very best point is pressed against one of them, on the side away from the other. That is the move that defeated three sellers on the street — stand right beside a rival and take everything behind it — and the town does not prevent it. A rival has a back, and in a square it is two-dimensional.

The street’s pairs fail by half a per cent #

Four sellers were the surprise of the street: they settle, in two pairs at the quarter points, each pair splitting the half of the street around it. The obvious town version puts the two pairs at the quarter points of the square’s middle line, $(\tfrac14, \tfrac12)$ and $(\tfrac34, \tfrac12)$, each pair splitting a half of the town. On the line through them, nobody wants to move: a seller sliding along the line in either direction loses, exactly as on the street.

Off the line it does. A seller who steps diagonally inward, to about $(0.33, 0.38)$, wins 25.48 per cent of the town instead of 25: a gain of 0.48 per cent. The map shows why. The darker regions form a diamond around the middle, and the pairs sit at its left and right corners — the worst places along its edge, not the best. On the street, every point of the street is on the line through the pairs, and the diamond’s sides do not exist. In the town they do, and a seller can slip along one.

The gain is small, and that smallness is itself information. The four-seller pairs are much closer to rest than any arrangement of three, which suggests that a nearby arrangement of four might be an equilibrium, and that the street’s answer has only moved slightly. The search does not find one: its best arrangement of four from random starts leaves a regret of 3.01 per cent, worse than the pairs, which shows how hard the landscape is to search and how special the pairs are. Whether a pure equilibrium of four sellers exists in the square is not settled by these computations.

How far each arrangement is from rest #

Gathered together, the regrets say what the town does to Hotelling’s game.

Two sellers at the centre: nought, an equilibrium. Three sellers on a line through the centre, the street’s arrangement laid across the town: fifteen per cent, because the middle seller is squeezed exactly as on the street. Three on the best triangle: 3.87. Four at the centres of the four quarters, an arrangement that looks like a natural division of the town: 5.57, because each seller can step towards the centre and take a slice of three neighbours. Four in the street’s pairs: 0.48.

The pattern is that the town makes things worse for every number of sellers except two. On the street the obstruction for three sellers was a single squeeze; in the town every seller has more directions in which to move, and every extra direction is another way for an arrangement to fail. An equilibrium needs every seller to be at a best reply at once, and in two dimensions there are twice as many conditions for each seller to satisfy.

The shape of a cell, and what a step buys #

Why a sideways step pays in a town and not on a street can be seen in the cell of a single seller. On a street, a seller between two rivals owns the interval from the midpoint on its left to the midpoint on its right, and moving a small distance $\delta$ to the right moves both midpoints by $\delta/2$: it gains $\delta/2$ on one side and loses $\delta/2$ on the other. Nothing changes until a seller runs out of rivals on one side, and that boundary effect is the whole of the street’s analysis — it is why the outermost sellers pair up and why the middle of three is squeezed.

In a town a seller’s cell is a polygon, and a small step changes it along every edge it shares with a rival. Each such edge lies on the bisector between the two sellers, and when one of them moves the bisector both slides and tilts: it slides by half the step’s component towards the rival, and it turns about the point where it crosses the segment joining them by an angle set by the step’s sideways component. A cell with many edges of different lengths, at different distances from those pivots, gains along some and loses along others, and the net effect of a small step is a weighted sum over all of them. Only when that sum is nought in every direction is the seller content to first order. Edges on the town’s own boundary never move, which is the town’s version of the street’s ends: a seller crowded against the boundary on one side has less to lose by stepping away from it.

On the street the same bookkeeping has two terms, one midpoint on each side, and it is exactly the rule that pushed the end sellers inward until they met a neighbour. None of it applies to a seller sharing a point with a partner, because there a step is not small in its effect: stepping away from the partner splits a shared cell, and the seller’s share jumps from half of the pair’s cell to everything on its own side of the new bisector. On the street that jump is exactly balanced at the quarter points — the seller gains the far side’s half of the pair’s interval and loses nothing — and that balance is what makes the pairs an equilibrium. In the town the jump depends on the direction of the step, because the new bisector can be tilted, and the diagonal step the map shows is the direction in which the jump pays most.

So every arrangement in a town must satisfy two kinds of condition at once: a first-order balance over its edges for every lone seller, and a balance of jumps for every seller with a partner. On a street each seller has one degree of freedom and one condition; in a town each has two of each, and every condition involves the cells of every neighbour, which change as anyone moves. An arrangement satisfying them all is a solution of $2n$ coupled conditions, which then also has to be a maximum for each seller rather than a saddle — the second condition that the landscape of a game can fail even when the first is met.

Why this is not a proof #

The figures establish less than the dek might suggest, and it is worth being exact about what.

Two sellers are proved, by the centre argument, for any symmetric town; the computation only illustrates it. The failure of the street’s four-seller pairs is proved by exhibiting the deviation: a seller at $(0.33, 0.38)$ wins more than a quarter, and that is a single area computed exactly. The failure of three sellers is not proved. The search found no arrangement with regret below about four per cent, and the triangle family’s least is 3.87, but a search over six coordinates can miss a narrow valley, and the best reply itself is found by a grid search that could miss a narrow peak — which would make some regrets slightly too small, never too large. A proof of non-existence needs an argument, not a search.

No general theorem settles three or more sellers in a square. Curtis Eaton and Richard Lipsey worked out the street for every number of sellers in 1975, and the street’s analysis rests on an order the town does not have: on a line, the sellers’ cells are intervals arranged in sequence and only the neighbours on each side matter, while in a town a seller’s cell is bounded by every rival that can see it.

The randomised equilibria left undrawn #

Mixed equilibria exist and are not drawn. As on the street, a game with no pure equilibrium still has equilibria in which the sellers randomise, choosing spots by a probability distribution that leaves each rival indifferent. For three sellers in a square these distributions have not been computed here, and they are not simple.

The town is a square, evenly populated, with straight-line distances. Real towns have streets, so distance is closer to the taxicab kind, and population is uneven. With taxicab distance the bisectors are not straight lines but staircases, and the cells are different shapes; the median argument for two sellers survives in modified form, and the computations for three and four would have to be redone.

Prices are fixed. Hotelling’s own model let sellers choose prices as well as places, and the interaction between the two is the subject of most of the economics literature on this game. Here every seller charges the same and competes on location alone.

Still open: rest for some number of sellers #

The street has a pure equilibrium for every number of sellers except three. The square, on this evidence, has one for two and perhaps for no other number. Is there any $n \ge 3$ for which $n$ sellers have a pure equilibrium in a square town? The pairs of four come within half a per cent, and for larger numbers there are natural candidates — sellers in pairs at the points of a lattice, the building block of every equilibrium on the street beyond three sellers. On the street, five sellers settle with pairs at a sixth and five sixths and a lone seller between them, and six or more have many equilibria built from pairs. In a town each pair is open to the same sideways step that defeated the pairs of four, and the computations here say nothing about whether some lattice and some number of sellers leaves no profitable step.

The broader lesson is about what an equilibrium needs. A third of random games have no pure equilibrium, and games with more strategies per player are less likely to have one; a seller in a town has a continuum of strategies in two directions, and the best replies of fictitious play chase each other round the square without settling. Two sellers escape this because a centre exists. For three and more, the square town is a place where every seller can always do slightly better, and nobody can stand still.