کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437948 690211 2009 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The isolation game: A game of distances
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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 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 mth 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 47–49, 6 November 2009, Pages 4905-4919