Facility Location With Approval Preferences: Strategyproofness and Fairness

Edith Elkind; Minming Li; Houyu Zhou

Facility Location With Approval Preferences: Strategyproofness and Fairness

Department of Computer Science

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

7 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	AAMAS' 22
Subtitle of host publication	Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems
Place of Publication	Richland, SC
Publisher	International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages	391–399
ISBN (Electronic)	978-1-4503-9213-6
Publication status	Published - 2022
Event	21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022) - Virtual, New Zealand Duration: 9 May 2022 → 13 May 2022 https://aamas2022-conference.auckland.ac.nz/

Publication series

Name	Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
ISSN (Print)	1548-8403
ISSN (Electronic)	1558-2914

Conference

Conference	21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)
Country/Territory	New Zealand
Period	9/05/22 → 13/05/22
Internet address	https://aamas2022-conference.auckland.ac.nz/

Bibliographical note

Research Unit(s) information for this publication is provided by the author(s) concerned.

Research Keywords

justified representation
multiwinner voting
facility location

Access Output

https://dl.acm.org/doi/10.5555/3535850.3535895

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Elkind, E., Li, M., & Zhou, H. (2022). Facility Location With Approval Preferences: Strategyproofness and Fairness. In AAMAS' 22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (pp. 391–399). (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). https://dl.acm.org/doi/10.5555/3535850.3535895

Elkind, Edith ; Li, Minming ; Zhou, Houyu. / Facility Location With Approval Preferences : Strategyproofness and Fairness. AAMAS' 22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems. Richland, SC : International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022. pp. 391–399 (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS).

@inproceedings{8634b09114b44bb0a1a3be197d1f3682,

title = "Facility Location With Approval Preferences: Strategyproofness and Fairness",

abstract = "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.",

keywords = "justified representation, multiwinner voting, facility location",

author = "Edith Elkind and Minming Li and Houyu Zhou",

note = "Research Unit(s) information for this publication is provided by the author(s) concerned.; 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)<br/> ; Conference date: 09-05-2022 Through 13-05-2022",

year = "2022",

language = "English",

series = "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS",

publisher = "International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)",

pages = "391–399",

booktitle = "AAMAS' 22",

url = "https://aamas2022-conference.auckland.ac.nz/",

}

Elkind, E, Li, M & Zhou, H 2022, Facility Location With Approval Preferences: Strategyproofness and Fairness. in AAMAS' 22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), Richland, SC, pp. 391–399, 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)
, New Zealand, 9/05/22. <https://dl.acm.org/doi/10.5555/3535850.3535895>

Facility Location With Approval Preferences: Strategyproofness and Fairness. / Elkind, Edith; Li, Minming ; Zhou, Houyu.
AAMAS' 22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022. p. 391–399 (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS).

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

TY - GEN

T1 - Facility Location With Approval Preferences

T2 - 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)<br/>

AU - Elkind, Edith

AU - Li, Minming

AU - Zhou, Houyu

N1 - Research Unit(s) information for this publication is provided by the author(s) concerned.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - justified representation

KW - multiwinner voting

KW - facility location

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

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

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

T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

SP - 391

EP - 399

BT - AAMAS' 22

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

CY - Richland, SC

Y2 - 9 May 2022 through 13 May 2022

ER -

Elkind E, Li M , Zhou H. Facility Location With Approval Preferences: Strategyproofness and Fairness. In AAMAS' 22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). 2022. p. 391–399. (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS). Epub 2022 May 9.

Facility Location With Approval Preferences: Strategyproofness and Fairness

Abstract

Publication series

Conference

Bibliographical note

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this