×

Strategy-proof approximation mechanisms for an obnoxious facility game on networks. (English) Zbl 1422.91144

Summary: We study a new facility game, namely, an obnoxious facility game, on a network where the facility is undesirable and all agents try to be as far away from the facility as possible. The following process is considered: at first the agents declare their locations, then, given these bids, a mechanism selects a place on the network to locate the facility. The aim of the mechanism is to maximize the obnoxious social welfare, i.e., the total distance between the agents and the facility. The objective of each agent is to maximize his/her utility, i.e., the distance from the facility. Thus an agent may lie if, by doing so, he/she can get strictly more benefit. We are interested in mechanisms without money to decide the facility location so that the obnoxious social welfare is maximized and all agents are enforced to report their true locations.
In this paper we give a first attempt at this game on different networks. Our main results are the following. When the network is a path, we show a 3-approximation group strategy-proof deterministic mechanism which is best possible if the facility can only take one of the endpoints on the path, and a group strategy-proof randomized mechanism with tight approximation ratio of \(\frac{3}{2}\). When the networks are a circle (known as a ring in the case of computer networks) and a tree, we propose two group strategy-proof deterministic mechanisms that each provides the approximation ratio of 3. Furthermore, when all agents are on a general network, we propose a 4-approximation group strategy-proof deterministic mechanism and a 2-approximation group strategy-proof randomized mechanism.

MSC:

91A43 Games involving graphs
90B80 Discrete location and assignment
91B14 Social choice
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[2] Clarke, E., Multipart pricing of public goods, Public Choices, 17C33 (1971)
[3] Church, R. L.; Garfinkel, R. S., Locating an obnoxious facility on a network, Transp. Sci., 12, 107-118 (1978)
[4] Groves, T., Incentive in teams, Econometrica, 41, 4, 617-631 (1973) · Zbl 0311.90002
[9] Schummer, J.; Vohra, R. V., Mechanism design without money, (Nisan, N.; Roughgarden, T.; Tardos, E.; Vazirani, V., Algorithmic Game Theory (2007), Cambridge University Press), chapter 10 · Zbl 1143.91317
[10] Tamir, A., Obnoxious facility location on graphs, SIAM J. Discrete Math., 4, 550-567 (1991) · Zbl 0737.05063
[11] Ting, S. S., A linear-time algorithm for maxisum facility location on tree networks, Transp. Sci., 18, 76-84 (1984)
[12] Vickrey, W., Counterspeculation, auctions and competitive sealed tenders, J. Finance, 16, 8-37 (1961)
[13] Zelinka, B., Medians and peripherians of trees, Arch. Math., 4, 87-95 (1968) · Zbl 0206.26105
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.