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 Google Scholar Google Scholar Articles by Moulin, H. Search for Related Content

On Scheduling Fees to Prevent Merging, Splitting, and Transferring of Jobs

Economics Department, Rice University, Houston, Texas 77005
moulin{at}rice.edu, http://www.ruf.rice.edu/econ/faculty/Moulin.htm

A deterministic server is shared by users with identical linear waiting costs, requesting jobs of arbitrary lengths. Shortest jobs are served first for efficiency. The server can monitor the length of a job but not the identity of the job’s user, thus merging, splitting, or partially transferring jobs offer cooperative strategic opportunities. Can we design cash transfers to neutralize such manipulations? We prove that mergeproofness and splitproofness are not compatible, and that it is similarly impossible to prevent all transfers of jobs involving three or more agents. On the other hand, robustness against pairwise transfers is feasible and essentially characterizes a one-dimensional set of scheduling methods. This line is borne by two outstanding methods: the merge-proof S⁺ and the split-proof S^–. Splitproofness, unlike mergeproofness, is not compatible with several simple tests of equity. Thus, the two properties are far from equally demanding.

Key Words: scheduling; queuing; merging; splitting; transferring; linear waiting cost
History: Received: August 30, 2004; revision received: June 20, 2006;