
CMUCS03141
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS03141
Minmax Payoffs of a Location Game
Shuchi Chawla, Uday Rajan, Ramamoorthi Ravi, Amitabh Sinha
May 2003
CMUCS03141.ps
CMUCS03141.pdf
Keywords: Game theory, location games, hotelling game, minmax payoffs, online games
We consider a twoplayer, 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
firstmover 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 singlemove 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
singlestage game.
12 pages
