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.