# Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio

arXiv: https://arxiv.org/abs/1907.08918 · HTML: https://mlsanity.com/paper/1907.08918/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2019.

## Built on by (most cited first, 1 of 1)

- [Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model](https://mlsanity.com/paper/2204.11282/) (2022)

## Abstract (arXiv)

In this paper, we study the two-facility location game on a line with optional preference where the acceptable set of facilities for each agent could be different and an agent's cost is his distance to the closest facility within his acceptable set. The objective is to minimize the total cost of all agents while achieving strategyproofness. We design a deterministic strategyproof mechanism for the problem with approximation ratio of 2.75, improving upon the earlier best ratio of n/2+1.