Computer Science Department
School of Computer Science, Carnegie Mellon University


Minmax Payoffs of a Location Game

Shuchi Chawla, Uday Rajan, Ramamoorthi Ravi, Amitabh Sinha

May 2003

Keywords: Game theory, location games, hotelling game, min-max payoffs, online games

We consider a two-player, sequential location game, with n stages. At each stage, players 1 and 2 choose locations from a feasible set in sequence. After all moves are made, consumers each purchase one unit of the good from the closest location. Since player 1 has a natural first-mover disadvantage here (player 2 can obtain a payoff of 1/2 just by replicating player 1's moves), we examine her minmax payoff. When the number of stages is known to both players we show that (i) if the feasible locations form a finite set in R^d , player 1 must obtain at least 1/d+1 in the single-move game (ii) in the original Hotelling game (uniformly distributed consumers on the unit interval), player 1 obtains 1/2 even in the multiple stage game. However, player 1's minmax payoff suffers if she does not know the number of moves, but player 2 does. In the Hotelling game, where the number of stages is either 1 or 2, player 1's payoff falls to 5/12 . If she has no information at all about n, we provide a lower bound for her minmax payoff: it must at least equal half the payoff of the single-stage game.

12 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by