Fairness in Temporal Slot Assignment

Edith Elkind; Sonja Kraiczy; Nicholas Teh

doi:10.1007/978-3-031-15714-1_28

Fairness in Temporal Slot Assignment

Edith Elkind^*, Sonja Kraiczy, Nicholas Teh

^*Corresponding author for this work

Computer Science

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

9 Scopus citations

Abstract

We investigate settings where projects need to be assigned to time slots based on preferences of multiple agents. We consider a variety of objectives, including utilitarian social welfare, egalitarian social welfare, Nash social welfare, Pareto optimality, equitability, and proportionality. We introduce a general-purpose randomized algorithm, which, for each of these objectives, can decide whether it is achievable for a given instance; the running time of this algorithm is in the complexity class XP with respect to the number of agents. We also provide complexity results for the case where the number of agents is large, and identify special cases that admit efficient algorithms.

Original language	English (US)
Title of host publication	Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings
Editors	Panagiotis Kanellopoulos, Maria Kyropoulou, Alexandros Voudouris
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	490-507
Number of pages	18
ISBN (Print)	9783031157134
DOIs	https://doi.org/10.1007/978-3-031-15714-1_28
State	Published - 2022
Event	15th International Symposium on Algorithmic Game Theory, SAGT 2022 - Colchester, United Kingdom Duration: Sep 12 2022 → Sep 15 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13584 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th International Symposium on Algorithmic Game Theory, SAGT 2022
Country/Territory	United Kingdom
City	Colchester
Period	9/12/22 → 9/15/22

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-15714-1_28

Cite this

Elkind, E., Kraiczy, S., & Teh, N. (2022). Fairness in Temporal Slot Assignment. In P. Kanellopoulos, M. Kyropoulou, & A. Voudouris (Eds.), Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings (pp. 490-507). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13584 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-15714-1_28

Elkind, Edith ; Kraiczy, Sonja ; Teh, Nicholas. / Fairness in Temporal Slot Assignment. Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings. editor / Panagiotis Kanellopoulos ; Maria Kyropoulou ; Alexandros Voudouris. Springer Science and Business Media Deutschland GmbH, 2022. pp. 490-507 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{048d2f9ece6e47ce996cd19e51608ac0,

title = "Fairness in Temporal Slot Assignment",

abstract = "We investigate settings where projects need to be assigned to time slots based on preferences of multiple agents. We consider a variety of objectives, including utilitarian social welfare, egalitarian social welfare, Nash social welfare, Pareto optimality, equitability, and proportionality. We introduce a general-purpose randomized algorithm, which, for each of these objectives, can decide whether it is achievable for a given instance; the running time of this algorithm is in the complexity class XP with respect to the number of agents. We also provide complexity results for the case where the number of agents is large, and identify special cases that admit efficient algorithms.",

author = "Edith Elkind and Sonja Kraiczy and Nicholas Teh",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 15th International Symposium on Algorithmic Game Theory, SAGT 2022 ; Conference date: 12-09-2022 Through 15-09-2022",

year = "2022",

doi = "10.1007/978-3-031-15714-1_28",

language = "English (US)",

isbn = "9783031157134",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "490--507",

editor = "Panagiotis Kanellopoulos and Maria Kyropoulou and Alexandros Voudouris",

booktitle = "Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings",

address = "Germany",

}

Elkind, E, Kraiczy, S & Teh, N 2022, Fairness in Temporal Slot Assignment. in P Kanellopoulos, M Kyropoulou & A Voudouris (eds), Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13584 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 490-507, 15th International Symposium on Algorithmic Game Theory, SAGT 2022, Colchester, United Kingdom, 9/12/22. https://doi.org/10.1007/978-3-031-15714-1_28

Fairness in Temporal Slot Assignment. / Elkind, Edith; Kraiczy, Sonja; Teh, Nicholas.
Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings. ed. / Panagiotis Kanellopoulos; Maria Kyropoulou; Alexandros Voudouris. Springer Science and Business Media Deutschland GmbH, 2022. p. 490-507 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13584 LNCS).

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

TY - GEN

T1 - Fairness in Temporal Slot Assignment

AU - Elkind, Edith

AU - Kraiczy, Sonja

AU - Teh, Nicholas

PY - 2022

Y1 - 2022

N2 - We investigate settings where projects need to be assigned to time slots based on preferences of multiple agents. We consider a variety of objectives, including utilitarian social welfare, egalitarian social welfare, Nash social welfare, Pareto optimality, equitability, and proportionality. We introduce a general-purpose randomized algorithm, which, for each of these objectives, can decide whether it is achievable for a given instance; the running time of this algorithm is in the complexity class XP with respect to the number of agents. We also provide complexity results for the case where the number of agents is large, and identify special cases that admit efficient algorithms.

AB - We investigate settings where projects need to be assigned to time slots based on preferences of multiple agents. We consider a variety of objectives, including utilitarian social welfare, egalitarian social welfare, Nash social welfare, Pareto optimality, equitability, and proportionality. We introduce a general-purpose randomized algorithm, which, for each of these objectives, can decide whether it is achievable for a given instance; the running time of this algorithm is in the complexity class XP with respect to the number of agents. We also provide complexity results for the case where the number of agents is large, and identify special cases that admit efficient algorithms.

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

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

U2 - 10.1007/978-3-031-15714-1_28

DO - 10.1007/978-3-031-15714-1_28

M3 - Conference contribution

AN - SCOPUS:85138821207

SN - 9783031157134

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 490

EP - 507

BT - Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings

A2 - Kanellopoulos, Panagiotis

A2 - Kyropoulou, Maria

A2 - Voudouris, Alexandros

PB - Springer Science and Business Media Deutschland GmbH

T2 - 15th International Symposium on Algorithmic Game Theory, SAGT 2022

Y2 - 12 September 2022 through 15 September 2022

ER -

Elkind E, Kraiczy S, Teh N. Fairness in Temporal Slot Assignment. In Kanellopoulos P, Kyropoulou M, Voudouris A, editors, Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 490-507. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-15714-1_28