Facility location games with distinct desires

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)148-160
Journal / PublicationDiscrete Applied Mathematics
Volume264
Early online date6 Mar 2019
Publication statusPublished - 15 Jul 2019

Abstract

In facility location games, one aims at designing a mechanism to decide the facility location based on the addresses reported by all agents. In the facility location game, each agent wants to minimize his/her distance from the facility, while in the obnoxious facility game, each agent prefers to be as far away from the facility as possible. In this paper we revisit the two games on a line network by finely defining another reasonable agent utility function in terms of their satisfaction degree with respect to the facility location. Namely, a happiness factor within [0,1] is introduced to measure the difference between the best facility location for an agent and the one given by the mechanism. An agent wants to gain a largest possible happiness factor while the social satisfaction is to maximize the sum of the factors. For the facility location game, we first show that the median mechanism (Procaccia and Tennenholtz, 2009) is 3/2-approximation. We then devise a 5/4-approximate group strategy-proof mechanism. Subsequently, we investigate the variant of maximizing the smallest happiness factor over all agents for this setting. For the obnoxious facility game, we show that the majority mechanism (Cheng et al., 2011) remains the best possible with approximation ratio of two. Finally, we devise a 4/3 -approximate randomized mechanism.

Research Area(s)

  • Approximation ratio, Facility location game, Happiness, Strategyproofness

Citation Format(s)

Facility location games with distinct desires. / Mei, Lili; Li, Minming; Ye, Deshi; Zhang, Guochuan.

In: Discrete Applied Mathematics, Vol. 264, 15.07.2019, p. 148-160.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review