Facility Location With Approval Preferences: Strategyproofness and Fairness

We develop a formal model of multiwinner facility location with approval preferences in one dimension: there is a set of facilities, a set of potential locations, and the goal is to build k facilities at these locations. Agents have approval preferences over 'facility, location' pairs, and may misreport their preferences if they can benefit from doing so. We consider both unit-demand agents and agents with additive demands, and the social objectives of coverage and utilitarian welfare. We ask whether these social objectives can be satisfied in a computationally efficient and strategyproof way. We also initiate the study of proportional representation in the context of facility location. We show that the axiom of justified representation, which is used to capture proportionality in multiwinner voting with approval preferences, is not well-suited for the facility location setting, and provide a relaxation of this axiom that can handle incompatibilities and may be of broader interest.