Scheduling with Opting Out: Improving Upon Random Priority

The article examines the scheduling model with opting out of agents. The planner/manager controls a server processing one job per unit of time. All agents prefer early service but are heterogeneous in their type. The manager uses a nonprice mechanism to schedule the agents; the only information he can use is the type of each agent. A simple and natural way to restore fairness is the random priority (RP) mechanism: the planner selects at random and without bias a certain priority ordering of the agents. Probabilistic serial resembles random priority closely, in particular shares its properties of incentive compatibility (strategyproofness) and fairness. Probabilistic serial is implemented in the same way as random priority: In the mathematical economics literature on random assignment on the other hand, fairness means, at least, that users with identical demands should be treated equally (ex ante), and sometimes is interpreted as the stronger requirement of envy-freeness (no agent prefers ex ante the assignment of another agent to his own).