Constant-Approximate and Constant-Strategyproof Two-Facility Location
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918124753780736 |
|---|---|
| author | Fullerton, Elijah Journey Hu, Zeyuan Plaxton, C. Gregory |
| author_facet | Fullerton, Elijah Journey Hu, Zeyuan Plaxton, C. Gregory |
| contents | We study deterministic mechanisms for the two-facility location problem. Given the reported locations of n agents on the real line, such a mechanism specifies where to build the two facilities. The single-facility variant of this problem admits a simple strategyproof mechanism that minimizes social cost. For two facilities, however, it is known that any strategyproof mechanism is $Ω(n)$-approximate. We seek to circumvent this strong lower bound by relaxing the problem requirements. Following other work in the facility location literature, we consider a relaxed form of strategyproofness in which no agent can lie and improve their outcome by more than a constant factor. Because the aforementioned $Ω(n)$ lower bound generalizes easily to constant-strategyproof mechanisms, we introduce a second relaxation: Allowing the facilities (but not the agents) to be located in the plane. Our first main result is a natural mechanism for this relaxation that is constant-approximate and constant-strategyproof. A characteristic of this mechanism is that a small change in the input profile can produce a large change in the solution. Motivated by this observation, and also by results in the facility reallocation literature, our second main result is a constant-approximate, constant-strategyproof, and Lipschitz continuous mechanism. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04485 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constant-Approximate and Constant-Strategyproof Two-Facility Location Fullerton, Elijah Journey Hu, Zeyuan Plaxton, C. Gregory Computer Science and Game Theory We study deterministic mechanisms for the two-facility location problem. Given the reported locations of n agents on the real line, such a mechanism specifies where to build the two facilities. The single-facility variant of this problem admits a simple strategyproof mechanism that minimizes social cost. For two facilities, however, it is known that any strategyproof mechanism is $Ω(n)$-approximate. We seek to circumvent this strong lower bound by relaxing the problem requirements. Following other work in the facility location literature, we consider a relaxed form of strategyproofness in which no agent can lie and improve their outcome by more than a constant factor. Because the aforementioned $Ω(n)$ lower bound generalizes easily to constant-strategyproof mechanisms, we introduce a second relaxation: Allowing the facilities (but not the agents) to be located in the plane. Our first main result is a natural mechanism for this relaxation that is constant-approximate and constant-strategyproof. A characteristic of this mechanism is that a small change in the input profile can produce a large change in the solution. Motivated by this observation, and also by results in the facility reallocation literature, our second main result is a constant-approximate, constant-strategyproof, and Lipschitz continuous mechanism. |
| title | Constant-Approximate and Constant-Strategyproof Two-Facility Location |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2507.04485 |