Scheduling with opting out: Improving upon random priority

In a scheduling problem where agents can opt out, we show that the familiar random priority (RP) mechanism can be improved upon by another mechanism d ubbed probabilistic serial (PS). Both mechanisms are nonmanipulable in a st rong sense, but the latter is Pareto superior to the former and serves a la rger (expected) number of agents. The PS equilibrium outcome is easier to c ompute than the RP outcome; on the other hand, RP is easier to implement th an PS. We show that the improvement of PS over RP is significant but small: at most a couple of percentage points in the relative welfare gain and the relative difference in quantity served. Both gains vanish when the number of agents is large; hence both mechanisms can be used as a proxy of each ot her.