Collective Schedules: Scheduling Meets Computational Social Choice

F. Pascual, K. Rzadca, P. Skowron
AAMAS 2018
Abstract
When scheduling public works or events in a shared facility one needs to accommodate preferences of a population. We formalize this problem by introducing the notion of a collective schedule. We show how to extend fundamental tools from social choice theory - positional scoring rules, the Kemeny rule and the Condorcet principle - to collective scheduling. We study the computational complexity of finding collective schedules. We also experimentally demonstrate that optimal collective schedules can be found for instances with realistic sizes.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Ordinal Impartial Culture {9} {146} 100 None
Ordinal Impartial Culture {7} {153} 100 None
Ordinal Impartial Culture {10} {5000} 100 None
Ordinal Impartial Culture {10} {500} 100 None
Ordinal Mallows {9} {146} 100 None
Ordinal Mallows {7} {153} 100 None
Ordinal Mallows {10} {5000} 100 None
Ordinal Mallows {10} {500} 100 None
Ordinal PrefLib {9} {146} 100 https://www.preflib.org/dataset/00009
Ordinal PrefLib {7} {153} 100 https://www.preflib.org/dataset/00009
Ordinal PrefLib {10} {5000} 100 https://www.preflib.org/dataset/00014
Ordinal PrefLib {10} {500} 100 https://www.preflib.org/dataset/00014