Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio

Minming Li; Pinyan Lu; Xingchen Sha; Yuhao Yao; Jialin Zhang

doi:10.1016/j.geb.2026.01.008

Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio

Minming Li, Pinyan Lu, Xingchen Sha^*, Yuhao Yao, Jialin Zhang

^*Corresponding author for this work

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

Abstract

In this paper, we study the two-facility location games 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. For general metrics, we design a deterministic strategyproof mechanism for the problem with an approximation ratio of 1 + 2α, where α is the approximation ratio of the offline optimization version. In particular, for the setting on a line, our mechanism achieves an approximation ratio of 1 + √2, which is tight and improves the previous best upper bound of n/2 + 1 (Chen et al., 2020). © 2026 Elsevier Inc.

Original language	English
Pages (from-to)	125-137
Number of pages	13
Journal	Games and Economic Behavior
Volume	157
Online published	24 Jan 2026
DOIs	https://doi.org/10.1016/j.geb.2026.01.008
Publication status	Published - Mar 2026

Bibliographical note

Full text of this publication does not contain sufficient affiliation information. Related Research Unit(s) information for this record is supplemented by the author(s) concerned.

Funding

Minming Li is supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 11216725). Pinyan Lu is supported by Science and Technology Innovation 2030 -“New Generation of Artificial Intelligence” Major Project No. 2018AAA0100903, the National Natural Science Foundation of China Grants No. 61922052, Innovation Program of Shanghai Municipal Education Commission, Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and the Fundamental Research Funds for the Central Universities. This work was supported in part by the National Natural Science Foundation of China Grants No. 62272441.

Research Keywords

Algorithmic game theory
Computational social choice
Facility location

Publisher's Copyright Statement

COPYRIGHT TERMS OF DEPOSITED POSTPRINT FILE: © 2026. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/.

RGC Funding Information

RGC-funded

Access Output

10.1016/j.geb.2026.01.008

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{ccbbba0b30264468babec04b04e40292,

title = "Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio",

abstract = "In this paper, we study the two-facility location games with optional preference where the acceptable set of facilities for each agent could be different and an agent{\textquoteright}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. For general metrics, we design a deterministic strategyproof mechanism for the problem with an approximation ratio of 1 + 2α, where α is the approximation ratio of the offline optimization version. In particular, for the setting on a line, our mechanism achieves an approximation ratio of 1 + √2, which is tight and improves the previous best upper bound of n/2 + 1 (Chen et al., 2020). {\textcopyright} 2026 Elsevier Inc.",

keywords = "Algorithmic game theory, Computational social choice, Facility location",

author = "Minming Li and Pinyan Lu and Xingchen Sha and Yuhao Yao and Jialin Zhang",

note = "Full text of this publication does not contain sufficient affiliation information. Related Research Unit(s) information for this record is supplemented by the author(s) concerned.",

year = "2026",

month = mar,

doi = "10.1016/j.geb.2026.01.008",

language = "English",

volume = "157",

pages = "125--137",

journal = "Games and Economic Behavior",

issn = "0899-8256",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio

AU - Li, Minming

AU - Lu, Pinyan

AU - Sha, Xingchen

AU - Yao, Yuhao

AU - Zhang, Jialin

N1 - Full text of this publication does not contain sufficient affiliation information. Related Research Unit(s) information for this record is supplemented by the author(s) concerned.

PY - 2026/3

Y1 - 2026/3

N2 - In this paper, we study the two-facility location games 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. For general metrics, we design a deterministic strategyproof mechanism for the problem with an approximation ratio of 1 + 2α, where α is the approximation ratio of the offline optimization version. In particular, for the setting on a line, our mechanism achieves an approximation ratio of 1 + √2, which is tight and improves the previous best upper bound of n/2 + 1 (Chen et al., 2020). © 2026 Elsevier Inc.

AB - In this paper, we study the two-facility location games 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. For general metrics, we design a deterministic strategyproof mechanism for the problem with an approximation ratio of 1 + 2α, where α is the approximation ratio of the offline optimization version. In particular, for the setting on a line, our mechanism achieves an approximation ratio of 1 + √2, which is tight and improves the previous best upper bound of n/2 + 1 (Chen et al., 2020). © 2026 Elsevier Inc.

KW - Algorithmic game theory

KW - Computational social choice

KW - Facility location

UR - http://www.scopus.com/inward/record.url?scp=105029020237&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-105029020237&origin=recordpage

U2 - 10.1016/j.geb.2026.01.008

DO - 10.1016/j.geb.2026.01.008

M3 - RGC 21 - Publication in refereed journal

SN - 0899-8256

VL - 157

SP - 125

EP - 137

JO - Games and Economic Behavior

JF - Games and Economic Behavior

ER -

Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio

Abstract

Bibliographical note

Funding

Research Keywords

Publisher's Copyright Statement

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Embargoed Document

Fingerprint

GRF: Temporal Facility Location Games with Building Sequence

Cite this

Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio

Abstract

Bibliographical note

Funding

Research Keywords

Publisher's Copyright Statement

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Embargoed Document

Fingerprint

Projects

GRF: Temporal Facility Location Games with Building Sequence

Cite this