Strategy-proof mechanisms for obnoxious facility game with bounded service range

Yukun Cheng (), Qiaoming Han (), Wei Yu () and Guochuan Zhang ()
Additional contact information
Yukun Cheng: School of Business, Suzhou University of Science and Technology
Qiaoming Han: Zhejiang University of Finance and Economics
Wei Yu: East China University of Science and Technology
Guochuan Zhang: Zhejiang University

Journal of Combinatorial Optimization, 2019, vol. 37, issue 2, No 19, 737-755

Abstract: Abstract In this paper, we study the obnoxious facility game with a limited service capacity on a line network, in which all facilities are undesirable and necessary for agents, such as the garbage dumps. The limited service capacity restricts each facility only to serve the agents in its service radius $$r> 0$$ r > 0 . All agents prefer to be far away from facilities, but still to be served by a facility. Namely, the distance between an agent and her nearest facility is at most r. In a deterministic or randomized mechanism, based on the addresses reported by the selfish agents, the locations or the location distributions of facilities are determined. The aim of the mechanisms is to maximize the obnoxious social welfare, the total distance between all agents and the facilities, on the premise of each agent being served. On the other hand, each agent tries to maximize her own utility, i.e., the distance from the facility, and she may lie if, by doing so, to get strictly more benefit. We are interested in mechanisms without money to elicit the true location profile (strategy-proofness or group strategy-proofness) and maximize the obnoxious social welfare as much as possible. In this paper, we give the first attempt for this game on a closed interval [0, 1], to design group strategy-proof deterministic and randomized mechanisms for the case of $$\frac{1}{2}\le r\le 1$$ 1 2 ≤ r ≤ 1 . The approximation ratios, depending on the radius r, of different mechanisms are explored. We also provide the lower bounds on approximation ratios of deterministic strategy-proof mechanisms.

Keywords: Algorithmic mechanism design; Obnoxious facility location; Service radius; Social choice (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0344-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:2:d:10.1007_s10878-018-0344-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0344-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().