Facility Location With Approval Preferences: Strategyproofness and Fairness

Edith Elkind; Minming Li; Houyu Zhou

Facility Location With Approval Preferences: Strategyproofness and Fairness

Edith Elkind, Minming Li, Houyu Zhou

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

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 (US)
Title of host publication	International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022
Publisher	International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages	391-399
Number of pages	9
ISBN (Electronic)	9781713854333
State	Published - 2022
Event	21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022 - Auckland, Virtual, New Zealand Duration: May 9 2022 → May 13 2022

Publication series

Name	Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume	1
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
City	Auckland, Virtual
Period	5/9/22 → 5/13/22

Funding

The work described in this paper was partially supported by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 11205619). We would like to thank the anonymous AAMAS-22 reviewers for their very useful feedback.

Keywords

facility location
justified representation
multiwinner voting

ASJC Scopus subject areas

Artificial Intelligence
Software
Control and Systems Engineering

Cite this

Elkind, E., Li, M., & Zhou, H. (2022). Facility Location With Approval Preferences: Strategyproofness and Fairness. In International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022 (pp. 391-399). (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS; Vol. 1). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

Elkind, Edith ; Li, Minming ; Zhou, Houyu. / Facility Location With Approval Preferences : Strategyproofness and Fairness. International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022. 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{acb9de42d1d84e34927cecbf1c514942,

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 = "facility location, justified representation, multiwinner voting",

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

note = "Publisher Copyright: {\textcopyright} 2022 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved; 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022 ; Conference date: 09-05-2022 Through 13-05-2022",

year = "2022",

language = "English (US)",

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 = "International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022",

}

Elkind, E, Li, M & Zhou, H 2022, Facility Location With Approval Preferences: Strategyproofness and Fairness. in International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, vol. 1, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), pp. 391-399, 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, Virtual, New Zealand, 5/9/22.

Facility Location With Approval Preferences: Strategyproofness and Fairness. / Elkind, Edith; Li, Minming; Zhou, Houyu.
International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022. 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; Vol. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Facility Location With Approval Preferences

T2 - 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022

AU - Elkind, Edith

AU - Li, Minming

AU - Zhou, Houyu

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 - facility location

KW - justified representation

KW - multiwinner voting

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

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

M3 - Conference contribution

AN - SCOPUS:85134351903

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

SP - 391

EP - 399

BT - International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022

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

Y2 - 9 May 2022 through 13 May 2022

ER -

Elkind E, Li M, Zhou H. Facility Location With Approval Preferences: Strategyproofness and Fairness. In International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022. 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).

Facility Location With Approval Preferences: Strategyproofness and Fairness

Abstract

Publication series

Conference

Funding

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this