Heterogeneous Facility Location with Limited Resources

Argyrios Deligkas; Aris Filos-Ratsikas; Alexandros A. Voudouris

doi:10.1609/aaai.v36i5.20427

Heterogeneous Facility Location with Limited Resources

Argyrios Deligkas, Aris Filos-Ratsikas, Alexandros A. Voudouris

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

Abstract

We initiate the study of the heterogeneous facility location problem with limited resources. We mainly focus on the fundamental case where a set of agents are positioned in the line segment [0,1] and have approval preferences over two available facilities. A mechanism takes as input the positions and the preferences of the agents, and chooses to locate a single facility based on this information. We study mechanisms that aim to maximize the social welfare (the total utility the agents derive from facilities they approve), under the constraint of incentivizing the agents to truthfully report their positions and preferences. We consider three different settings depending on the level of agent-related information that is public or private. For each setting, we design deterministic and randomized strategyproof mechanisms that achieve a good approximation of the optimal social welfare, and complement these with nearly-tight impossibility results.

Original language	English
Title of host publication	Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence - Vol. 36 No. 5: AAAI-22 Technical Tracks 5
Editors	Katia Sycara, Vasant Honavar, Matthijs Spaan
Place of Publication	Palo Alto, California, USA
Publisher	AAAI Press
Pages	4966-4974
Number of pages	9
Volume	36
ISBN (Print)	1-57735-876-7, 978-1-57735-876-3
DOIs	https://doi.org/10.1609/aaai.v36i5.20427
Publication status	Published - 28 Jun 2022
Event	36th AAAI Conference on Artificial Intelligence - Virtual Conference Duration: 22 Feb 2022 → 1 Mar 2022 Conference number: 36 https://aaai.org/Conferences/AAAI-22/

Publication series

Name	Proceedings of the AAAI Conference on Artificial Intelligence
Publisher	AAAI Press
Number	5
Volume	36
ISSN (Print)	2159-5399
ISSN (Electronic)	2374-3468

Conference

Conference	36th AAAI Conference on Artificial Intelligence
Abbreviated title	AAAI 2022
Period	22/02/22 → 1/03/22
Internet address	https://aaai.org/Conferences/AAAI-22/

Access to Document

10.1609/aaai.v36i5.20427Licence: All Rights Reserved

https://ojs.aaai.org/index.php/AAAI/article/view/20427Licence: All Rights Reserved

1 Article

Heterogeneous facility location with limited resources
Deligkas, A., Filos-Ratsikas, A. & Voudouris, A. A., 1 May 2023, In: Games and Economic Behavior. 139, p. 200-215 16 p.
Research output: Contribution to journal › Article › peer-review

Open Access
File

Cite this

Deligkas, A., Filos-Ratsikas, A., & Voudouris, A. A. (2022). Heterogeneous Facility Location with Limited Resources. In K. Sycara, V. Honavar, & M. Spaan (Eds.), Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence - Vol. 36 No. 5: AAAI-22 Technical Tracks 5 (Vol. 36, pp. 4966-4974). (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 36, No. 5). AAAI Press. https://doi.org/10.1609/aaai.v36i5.20427

Deligkas, Argyrios ; Filos-Ratsikas, Aris ; Voudouris, Alexandros A. / Heterogeneous Facility Location with Limited Resources. Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence - Vol. 36 No. 5: AAAI-22 Technical Tracks 5. editor / Katia Sycara ; Vasant Honavar ; Matthijs Spaan. Vol. 36 Palo Alto, California, USA : AAAI Press, 2022. pp. 4966-4974 (Proceedings of the AAAI Conference on Artificial Intelligence; 5).

@inproceedings{9464d5da322b49a1b4667556489c375d,

title = "Heterogeneous Facility Location with Limited Resources",

abstract = "We initiate the study of the heterogeneous facility location problem with limited resources. We mainly focus on the fundamental case where a set of agents are positioned in the line segment [0,1] and have approval preferences over two available facilities. A mechanism takes as input the positions and the preferences of the agents, and chooses to locate a single facility based on this information. We study mechanisms that aim to maximize the social welfare (the total utility the agents derive from facilities they approve), under the constraint of incentivizing the agents to truthfully report their positions and preferences. We consider three different settings depending on the level of agent-related information that is public or private. For each setting, we design deterministic and randomized strategyproof mechanisms that achieve a good approximation of the optimal social welfare, and complement these with nearly-tight impossibility results.",

author = "Argyrios Deligkas and Aris Filos-Ratsikas and Voudouris, {Alexandros A.}",

year = "2022",

month = jun,

day = "28",

doi = "10.1609/aaai.v36i5.20427",

language = "English",

isbn = "1-57735-876-7",

volume = "36",

series = "Proceedings of the AAAI Conference on Artificial Intelligence",

publisher = "AAAI Press",

number = "5",

pages = "4966--4974",

editor = "Katia Sycara and Vasant Honavar and Matthijs Spaan",

booktitle = "Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence - Vol. 36 No. 5: AAAI-22 Technical Tracks 5",

note = "36th AAAI Conference on Artificial Intelligence, AAAI 2022 ; Conference date: 22-02-2022 Through 01-03-2022",

url = "https://aaai.org/Conferences/AAAI-22/",

}

Deligkas, A, Filos-Ratsikas, A & Voudouris, AA 2022, Heterogeneous Facility Location with Limited Resources. in K Sycara, V Honavar & M Spaan (eds), Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence - Vol. 36 No. 5: AAAI-22 Technical Tracks 5. vol. 36, Proceedings of the AAAI Conference on Artificial Intelligence, no. 5, vol. 36, AAAI Press, Palo Alto, California, USA, pp. 4966-4974, 36th AAAI Conference on Artificial Intelligence, 22/02/22. https://doi.org/10.1609/aaai.v36i5.20427

Heterogeneous Facility Location with Limited Resources. / Deligkas, Argyrios; Filos-Ratsikas, Aris; Voudouris, Alexandros A.

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence - Vol. 36 No. 5: AAAI-22 Technical Tracks 5. ed. / Katia Sycara; Vasant Honavar; Matthijs Spaan. Vol. 36 Palo Alto, California, USA : AAAI Press, 2022. p. 4966-4974 (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 36, No. 5).

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

TY - GEN

T1 - Heterogeneous Facility Location with Limited Resources

AU - Deligkas, Argyrios

AU - Filos-Ratsikas, Aris

AU - Voudouris, Alexandros A.

N1 - Conference code: 36

PY - 2022/6/28

Y1 - 2022/6/28

N2 - We initiate the study of the heterogeneous facility location problem with limited resources. We mainly focus on the fundamental case where a set of agents are positioned in the line segment [0,1] and have approval preferences over two available facilities. A mechanism takes as input the positions and the preferences of the agents, and chooses to locate a single facility based on this information. We study mechanisms that aim to maximize the social welfare (the total utility the agents derive from facilities they approve), under the constraint of incentivizing the agents to truthfully report their positions and preferences. We consider three different settings depending on the level of agent-related information that is public or private. For each setting, we design deterministic and randomized strategyproof mechanisms that achieve a good approximation of the optimal social welfare, and complement these with nearly-tight impossibility results.

AB - We initiate the study of the heterogeneous facility location problem with limited resources. We mainly focus on the fundamental case where a set of agents are positioned in the line segment [0,1] and have approval preferences over two available facilities. A mechanism takes as input the positions and the preferences of the agents, and chooses to locate a single facility based on this information. We study mechanisms that aim to maximize the social welfare (the total utility the agents derive from facilities they approve), under the constraint of incentivizing the agents to truthfully report their positions and preferences. We consider three different settings depending on the level of agent-related information that is public or private. For each setting, we design deterministic and randomized strategyproof mechanisms that achieve a good approximation of the optimal social welfare, and complement these with nearly-tight impossibility results.

U2 - 10.1609/aaai.v36i5.20427

DO - 10.1609/aaai.v36i5.20427

M3 - Conference contribution

SN - 1-57735-876-7

SN - 978-1-57735-876-3

VL - 36

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 4966

EP - 4974

BT - Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence - Vol. 36 No. 5: AAAI-22 Technical Tracks 5

A2 - Sycara, Katia

A2 - Honavar, Vasant

A2 - Spaan, Matthijs

PB - AAAI Press

CY - Palo Alto, California, USA

T2 - 36th AAAI Conference on Artificial Intelligence

Y2 - 22 February 2022 through 1 March 2022

ER -

Deligkas A, Filos-Ratsikas A, Voudouris AA. Heterogeneous Facility Location with Limited Resources. In Sycara K, Honavar V, Spaan M, editors, Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence - Vol. 36 No. 5: AAAI-22 Technical Tracks 5. Vol. 36. Palo Alto, California, USA: AAAI Press. 2022. p. 4966-4974. (Proceedings of the AAAI Conference on Artificial Intelligence; 5). doi: 10.1609/aaai.v36i5.20427

Heterogeneous Facility Location with Limited Resources

Abstract

Publication series

Conference

Access to Document

Research output

Heterogeneous facility location with limited resources

Cite this