Assigning agents to a line

We consider the problem of assigning agents to a facility, represented by slots on a line, where only one agent can be served at a time. There is a finite number of agents, and each one wants to be served as close as possible to his preferred slot. We first consider deterministic assignment of agents to slots. We characterize (Pareto) efficiency in such setting and provide an algorithm for testing if a given deterministic assignment is efficient. We also characterize utilitarianism (minimization of the total gap between preferred and assigned slots) and provide a quick algorithm for testing if a given deterministic assignment is utilitarian. We then consider probabilistic assignment of agents to slots. In such framework, we characterize, making use of the previous algorithms, a method which is ordinally efficient and utilitarian.