Geometric Network Design with Selfish Agents
We study a geometric version of a simple non-cooperative network creation game introduced in 2, assuming Euclidean edge costs on the plane. The price of anarchy in such geometric games with k players is Θ(k). Hence, we consider the task of minimizing players incentives to deviate from a payment scheme, purchasing the minimum cost network. In contrast to general games, in small geometric games (2 players and 2 terminals per player), a Nash equilibrium purchasing the optimum network exists. This can be translated into a (1 + ∈)-approximate Nash equilibrium purchasing the optimum network under more practical assumptions, for any ∈ > 0.For more players there are games with 2 terminals per player, such that any Nash equilibrium purchasing the optimum solution is at least (4/3-∈)-approximate. On the algorithmic side, we show that playing small games with best-response strategies yields low-cost Nash equilibria. The distinguishing feature of our paper are new techniques to deal with the geometric setting, fundamentally different from the techniques used in 2.
Martin Hoefer Piotr Krysta
Department of Computer & Information Science, Konstanz University Box D 67,78457 Konstanz, Germany Department of Computer Science, Dortmund University Baroper Str. 301,44221 Dortmund, Germany
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
167-178
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）