TY - JOUR
T1 - Computational Aspects of Assigning Agents to a Line
AU - Aziz, Haris
AU - Hougaard, Jens Leth
AU - Moreno-Ternero, Juan D.
AU - Østerdal, Lars Peter
PY - 2017/11
Y1 - 2017/11
N2 - We consider the problem of assigning agents to slots on a line, where only one agent can be served at a slot and each agent prefers to be served as close as possible to his target. We introduce a general approach to compute aggregate gap-minimizing assignments, as well as gap-egalitarian assignments. The approach relies on an algorithm which is shown to be faster than general purpose algorithms for the assignment problem. We also extend the approach to probabilistic assignments and explore the computational features of existing, as well as new, methods for this setting.
AB - We consider the problem of assigning agents to slots on a line, where only one agent can be served at a slot and each agent prefers to be served as close as possible to his target. We introduce a general approach to compute aggregate gap-minimizing assignments, as well as gap-egalitarian assignments. The approach relies on an algorithm which is shown to be faster than general purpose algorithms for the assignment problem. We also extend the approach to probabilistic assignments and explore the computational features of existing, as well as new, methods for this setting.
U2 - 10.1016/j.mathsocsci.2016.12.004
DO - 10.1016/j.mathsocsci.2016.12.004
M3 - Journal article
SN - 0165-4896
VL - 86
SP - 68
EP - 74
JO - Mathematical Social Sciences
JF - Mathematical Social Sciences
ER -