QQ客服 官方微博 反馈留言

	The isolation game: A game of distances
	Zhao, Yingchao ; Chen, Wei ; Teng, Shang-hua
	2010-10-12 ; 2010-10-12
关键词	Algorithmic game theory Nash equilibrium Computational complexity VORONOI GAME LOCATION MODELS Computer Science, Theory & Methods
中文摘要	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 Durr and Thang, each player's objective is to maximize the area of tier Voronoi region. In contrast, in the isolation game, each player's objective is to position herself as far away from other players as possible ill 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 fatness measure in an asymmetric space or a slightly more sophisticated fatness measure in a symmetric space. Complementing these hardness results, we establish existence theorems for several special families of fatness 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 in, 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 oil 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. (C) 2009 Elsevier B.V. All rights reserved.
语种	英语 ; 英语
出版者	ELSEVIER SCIENCE BV ; AMSTERDAM ; PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
内容类型	期刊论文
源URL	[http://hdl.handle.net/123456789/82865]
专题	清华大学
推荐引用方式 GB/T 7714	Zhao, Yingchao,Chen, Wei,Teng, Shang-hua. The isolation game: A game of distances[J],2010, 2010.
APA	Zhao, Yingchao,Chen, Wei,&Teng, Shang-hua.(2010).The isolation game: A game of distances..
MLA	Zhao, Yingchao,et al."The isolation game: A game of distances".(2010).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。