The Isolation Game: A Game of Distances

We introduce a new multi-player geometric game, which we will refer to as the isolation game, and study its Nash equilibria and best or better response dynamics. The isolation game is inspired by the Voronoi game, competitive facility location, and geometric sampling. In the Voronoi game studied by Dürr and Thang, each player’s objective is to maximize the area of her Voronoi region. In contrast, in the isolation game, each player’s objective is to position herself as far away from other players as possible in a bounded space. Even though this game has a simple definition, we show that its game-theoretic behaviors are quite rich and complex. We consider various measures of farness from one player to a group of players and analyze their impacts to the existence of Nash equilibria and to the convergence of the best or better response dynamics: We prove that it is NP-hard to decide whether a Nash equilibrium exists, using either a very simple farness measure in an asymmetric space or a slightly more sophisticated farness measure in a symmetric space. Complementing to these hardness results, we establish existence theorems for several special families of farness measures in symmetric spaces: We prove that for isolation games where each player wants to maximize her distance to her m ^th nearest neighbor, for any m, equilibria always exist. Moreover, there is always a better response sequence starting from any configuration that leads to a Nash equilibrium. We show that when m = 1 the game is a potential game — no better response sequence has a cycle, but when m > 1 the games are not potential. More generally, we study farness functions that give different weights to a player’s distances to others based on the distance rankings, and obtain both existence and hardness results when the weights are monotonically increasing or decreasing. Finally, we present results on the hardness of computing best responses when the space has a compact representation as a hypercube.

Authors and Affiliations

1. State Key Laboratory of Intelligent Technology and Systems Tsinghua National Laboratory for Information Science and Technology Department of Computer Science and Technology, Tsinghua University, China

   Yingchao Zhao

2. Microsoft Research Asia, China

   Wei Chen

3. Boston University, USA

   Shang-Hua Teng

Editors and Affiliations

1. School of Information Technologies, University of Sydney, Australia

   Seok-Hee Hong

2. Graduate School of Informatics, Kyoto University, 606-8501, Kyoto, Japan

   Hiroshi Nagamochi

3. Graduate School of Informatics, Kyoto University, Japan

   Takuro Fukunaga

Reprints and permissions

© 2008 Springer-Verlag Berlin Heidelberg

Policies and ethics