Research Repository

Mechanism Design for Constrained Heterogeneous Facility Location

Kyropoulou, Maria and Ventre, Carmine and Zhang, Xiaomeng (2019) Mechanism Design for Constrained Heterogeneous Facility Location. In: Algorithmic Game Theory, 12th International Symposium, SAGT 2019, 2019-09-30 - 2019-10-03, Athens, Greece.

sagt19-submission-facloc-submitted.pdf - Accepted Version

Download (320kB) | Preview


The facility location problem has emerged as the benchmark problem in the study of the trade-off between incentive compatibility without transfers and approximation guarantee, a research area also known as approximate mechanism design without money. One limitation of the vast literature on the subject is the assumption that agents and facilities have to be located on the same physical space. We here initiate the study of constrained heterogeneous facility location problems, wherein selfish agents can either like or dislike the facility and facilities can be located on a given feasible region of the Euclidean plane. In our study, agents are assumed to be located on a real segment, and their location together with their preferences towards the facilities can be part of their private type. Our main result is a characterization of the feasible regions for which the optimum is incentive-compatible in the settings wherein agents can only lie about their preferences or about their locations. The stark contrast between the two findings is that in the former case any feasible region can be coupled with incentive compatibility, whilst in the second, this is only possible for feasible regions where the optimum is constant.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Uncontrolled Keywords: Mechanism design without money; Facility location; Incentive compatibility
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 24 Mar 2022 17:38
Last Modified: 24 Mar 2022 17:39

Actions (login required)

View Item View Item