Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance

Longteng Duan; Zifan Gong; Minming Li; Chenhao Wang; Xiaoying Wu

doi:10.1007/978-3-030-89543-3_42

Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance

Longteng Duan, Zifan Gong, Minming Li, Chenhao Wang^*, Xiaoying Wu

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

3 Citations (Scopus)

Abstract

In this paper, we study the mechanism design for two-facility-location games with the fractional preferences of agents, in which each agent has private information including her location in an interval [0, 1] and her fractional preference to indicate how much she prefers the two facilities. The decision maker needs to locate the two facilities to serve the agents, who has a utility equal to the interval length 1 minus the sum of weighted distances to both facilities. The facility locations are required to satisfy a minimum distance constraint, i.e., the distance of the two facilities must exceed a given number d ∈ [ 0, 1 ]. The goal is to design strategy-proof mechanisms to maximize the social/minimum utility among the agents. We propose a randomized strategy-proof mechanism, which is 2-approximation for both objectives of maximizing the social utility and minimum utility. We also propose a deterministic strategy-proof mechanism which has an approximation ratio of ⁴⁄_2-d and 4 for the two objectives, respectively. Furthermore, we derive corresponding lower bounds on the approximation ratios of strategy-proof mechanisms.

Original language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	27th International Conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021, Proceedings
Editors	Chi-Yeh Chen, Wing-Kai Hon, Ling-Ju Hung, Chia-Wei Lee
Place of Publication	Cham
Publisher	Springer
Pages	499-511
ISBN (Electronic)	9783030895433
ISBN (Print)	9783030895426
DOIs	https://doi.org/10.1007/978-3-030-89543-3_42
Publication status	Published - 2021
Event	27th International Conference on Computing and Combinatorics (COCOON 2021) - Shangri-La's Far Eastern Plaza Hotel, Tainan, Taiwan, China Duration: 24 Oct 2021 → 26 Oct 2021 http://cocoon-conference.org/2021/

Publication series

Name	Lecture Notes in Computer Science
Volume	13025
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	27th International Conference on Computing and Combinatorics (COCOON 2021)
Place	Taiwan, China
City	Tainan
Period	24/10/21 → 26/10/21
Internet address	http://cocoon-conference.org/2021/

Bibliographical note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Research Keywords

Approximation
Facility location
Mechanism design

RGC Funding Information

RGC-funded

Access Output

10.1007/978-3-030-89543-3_42

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Duan, L., Gong, Z., Li, M., Wang, C., & Wu, X. (2021). Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance. In C.-Y. Chen, W.-K. Hon, L.-J. Hung, & C.-W. Lee (Eds.), Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021, Proceedings (pp. 499-511). (Lecture Notes in Computer Science; Vol. 13025). Springer . https://doi.org/10.1007/978-3-030-89543-3_42

Duan, Longteng ; Gong, Zifan ; Li, Minming et al. / Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance. Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021, Proceedings. editor / Chi-Yeh Chen ; Wing-Kai Hon ; Ling-Ju Hung ; Chia-Wei Lee. Cham : Springer , 2021. pp. 499-511 (Lecture Notes in Computer Science).

@inproceedings{23204e88704642f49c6b8ede4416a06c,

title = "Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance",

abstract = "In this paper, we study the mechanism design for two-facility-location games with the fractional preferences of agents, in which each agent has private information including her location in an interval [0, 1] and her fractional preference to indicate how much she prefers the two facilities. The decision maker needs to locate the two facilities to serve the agents, who has a utility equal to the interval length 1 minus the sum of weighted distances to both facilities. The facility locations are required to satisfy a minimum distance constraint, i.e., the distance of the two facilities must exceed a given number d ∈ [ 0, 1 ]. The goal is to design strategy-proof mechanisms to maximize the social/minimum utility among the agents. We propose a randomized strategy-proof mechanism, which is 2-approximation for both objectives of maximizing the social utility and minimum utility. We also propose a deterministic strategy-proof mechanism which has an approximation ratio of 4⁄2-d and 4 for the two objectives, respectively. Furthermore, we derive corresponding lower bounds on the approximation ratios of strategy-proof mechanisms.",

keywords = "Approximation, Facility location, Mechanism design",

author = "Longteng Duan and Zifan Gong and Minming Li and Chenhao Wang and Xiaoying Wu",

note = "Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).; 27th International Conference on Computing and Combinatorics (COCOON 2021) ; Conference date: 24-10-2021 Through 26-10-2021",

year = "2021",

doi = "10.1007/978-3-030-89543-3_42",

language = "English",

isbn = "9783030895426",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "499--511",

editor = "Chi-Yeh Chen and Wing-Kai Hon and Ling-Ju Hung and Chia-Wei Lee",

booktitle = "Computing and Combinatorics",

url = "http://cocoon-conference.org/2021/",

}

Duan, L, Gong, Z , Li, M, Wang, C & Wu, X 2021, Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance. in C-Y Chen, W-K Hon, L-J Hung & C-W Lee (eds), Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021, Proceedings. Lecture Notes in Computer Science, vol. 13025, Springer , Cham, pp. 499-511, 27th International Conference on Computing and Combinatorics (COCOON 2021), Tainan, Taiwan, China, 24/10/21. https://doi.org/10.1007/978-3-030-89543-3_42

Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance. / Duan, Longteng; Gong, Zifan ; Li, Minming et al.
Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021, Proceedings. ed. / Chi-Yeh Chen; Wing-Kai Hon; Ling-Ju Hung; Chia-Wei Lee. Cham: Springer , 2021. p. 499-511 (Lecture Notes in Computer Science; Vol. 13025).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance

AU - Duan, Longteng

AU - Gong, Zifan

AU - Li, Minming

AU - Wang, Chenhao

AU - Wu, Xiaoying

N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

PY - 2021

Y1 - 2021

N2 - In this paper, we study the mechanism design for two-facility-location games with the fractional preferences of agents, in which each agent has private information including her location in an interval [0, 1] and her fractional preference to indicate how much she prefers the two facilities. The decision maker needs to locate the two facilities to serve the agents, who has a utility equal to the interval length 1 minus the sum of weighted distances to both facilities. The facility locations are required to satisfy a minimum distance constraint, i.e., the distance of the two facilities must exceed a given number d ∈ [ 0, 1 ]. The goal is to design strategy-proof mechanisms to maximize the social/minimum utility among the agents. We propose a randomized strategy-proof mechanism, which is 2-approximation for both objectives of maximizing the social utility and minimum utility. We also propose a deterministic strategy-proof mechanism which has an approximation ratio of 4⁄2-d and 4 for the two objectives, respectively. Furthermore, we derive corresponding lower bounds on the approximation ratios of strategy-proof mechanisms.

AB - In this paper, we study the mechanism design for two-facility-location games with the fractional preferences of agents, in which each agent has private information including her location in an interval [0, 1] and her fractional preference to indicate how much she prefers the two facilities. The decision maker needs to locate the two facilities to serve the agents, who has a utility equal to the interval length 1 minus the sum of weighted distances to both facilities. The facility locations are required to satisfy a minimum distance constraint, i.e., the distance of the two facilities must exceed a given number d ∈ [ 0, 1 ]. The goal is to design strategy-proof mechanisms to maximize the social/minimum utility among the agents. We propose a randomized strategy-proof mechanism, which is 2-approximation for both objectives of maximizing the social utility and minimum utility. We also propose a deterministic strategy-proof mechanism which has an approximation ratio of 4⁄2-d and 4 for the two objectives, respectively. Furthermore, we derive corresponding lower bounds on the approximation ratios of strategy-proof mechanisms.

KW - Approximation

KW - Facility location

KW - Mechanism design

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

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

U2 - 10.1007/978-3-030-89543-3_42

DO - 10.1007/978-3-030-89543-3_42

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783030895426

T3 - Lecture Notes in Computer Science

SP - 499

EP - 511

BT - Computing and Combinatorics

A2 - Chen, Chi-Yeh

A2 - Hon, Wing-Kai

A2 - Hung, Ling-Ju

A2 - Lee, Chia-Wei

PB - Springer

CY - Cham

T2 - 27th International Conference on Computing and Combinatorics (COCOON 2021)

Y2 - 24 October 2021 through 26 October 2021

ER -

Duan L, Gong Z , Li M, Wang C, Wu X. Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance. In Chen CY, Hon WK, Hung LJ, Lee CW, editors, Computing and Combinatorics: 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021, Proceedings. Cham: Springer . 2021. p. 499-511. (Lecture Notes in Computer Science). Epub 2021 Oct 20. doi: 10.1007/978-3-030-89543-3_42

Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance

Abstract

Publication series

Conference

Bibliographical note

Research Keywords

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this