Research Repository

On Discrete Truthful Heterogeneous Two-Facility Location

Kanellopoulos, Panagiotis and Voudouris, Alexandros and Zhang, Rongsen (2022) On Discrete Truthful Heterogeneous Two-Facility Location. In: 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence (IJCAI-ECAI 22), 2022-07 - 2022-07, Vienna. (In Press)

main922-camera.pdf - Accepted Version

Download (203kB) | Preview


We revisit the discrete heterogeneous two-facility location problem, in which there is a set of agents that occupy nodes of a line graph, and have private approval preferences over two facilities. When the facilities are located at some nodes of the line, each agent derives a cost that is equal to her total dis- tance from the facilities she approves. The goal is to decide where to locate the two facilities, so as to (a) incentivize the agents to truthfully report their preferences, and (b) achieve a good approximation of the minimum total (social) cost or the maximum cost among all agents. For both objectives, we de- sign deterministic strategyproof mechanisms with approximation ratios that significantly outperform the state-of-the-art, and complement these results with (almost) tight lower bounds.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: _not provided_
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 25 Apr 2022 12:10
Last Modified: 25 Apr 2022 12:10

Actions (login required)

View Item View Item