International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong


Invited Speakers

Track A

Two-Facility Location Games with Distance Requirement

Ling Gai

Donghua University

We consider the games of locating two homogeneous facilities in the interval $[0,1]$ with maximum/minimum distance requirement. In these games, n agents report their locations, then the designed mechanism outputs the locations of two homogeneous facilities. All the location information is private and the agents can choose to misreport to influence the output. The utility of any agent in the games is determined by his minimum distance to one of the two facilities. The strategy-proof mechanisms are designed to minimize the total cost/ maximize the total utility. In the game of locating two desirable facilities with maximum distance requirement, we show that no deterministic strategy-proof mechanism can reach a constant approximation ratio comparing with the optimal solution without private information. In the game of locating two obnoxious facilities with maximum distance requirement, we propose group strategy-proof mechanisms and prove their approximation ratios. We then focus on the games of locating two obnoxious homogeneous facilities with both the minimum and maximum distance constraint. We design several group strategy-proof mechanisms aiming at maximizing the total utility. The approximation ratios are analyzed and the comparison of mechanisms is conducted. Lower bound instances are also presented to show the gaps.

Associate professor of Donghua University. Her research interest includes approximation algorithm design and analysis, bin packing game and facility location game.