This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Crès, H. Articles by Moulin, H. Search for Related Content

Scheduling with Opting Out: Improving upon Random Priority

HEC School of Management, 78351 Jouy-en Josas, France
Department of Economics, Rice University, MS 22, P.O. Box 1892, Houston, Texas, 77251-1892
cres{at}hec.fr
moulin{at}rice.edu

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 dubbed probabilistic serial (PS). Both mechanisms are nonmanipulable in a strong sense, but the latter is Pareto superior to the former and serves a larger (expected) number of agents. The PS equilibrium outcome is easier to compute than the RP outcome; on the other hand, RP is easier to implement than 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 other.

Subject classifications: Production/scheduling: probabilistic sequencing, random priority; opting out; Games/group decisions: Pareto improvement, strategy-proof report of utility.
History: Received October 1998; revision received August 1999; accepted February 2000.

This article has been cited by other articles:

				A. Agnetis, P. B. Mirchandani, D. Pacciarelli, and A. Pacifici Scheduling Problems with Two Competing Agents Operations Research, March 1, 2004; 52(2): 229 - 242. [Abstract] [PDF]