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

Mathematics of Operations Research - Tập 32 Số 2 - Trang 266-283 - 2007
Hervé Moulin1
1Economics Department, Rice University, Houston, Texas 77005

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

Aczél J., 1996, Lectures on Functional Equations and Their Applications

Banker R., 1981, Joint Cost Allocations, 110

10.1007/s003550050175

Chun Y. Consistency and monotonicity in sequencing problems. (2004) . Working paper, Seoul National University, Seoul, Korea

10.1016/j.mathsocsci.2005.08.002

10.1007/s100580050037

10.2307/3003591

10.1007/3-540-45748-8_24

10.1016/S0899-8256(05)80005-3

10.1006/jeth.1999.2534

10.1016/j.geb.2003.09.005

Hamers H., 2002, Game Theory in Honor of Stef Tijs, 27

10.1007/s10058-003-0097-8

Katta A., Sethuraman J. A note on cooperation in queues. (2004) . Working paper, Columbia University, New York

Kittsteiner T., Moldovanu B. Auction-based queue disciplines. (2003) . Working paper, University of Bonn, Bonn, Germany

10.1287/mnsc.1040.0301

10.1016/S0022-0531(02)00036-4

10.1287/opre.38.5.870

10.1007/PL00004107

10.1007/s100580200071

10.1016/j.jet.2005.08.003

10.2307/1911723

10.1007/BF01756289

Moulin H., 2004, Games and Econom. Behav.

Moulin H., 2005, J. Oper. Res.

10.1016/0377-2217(89)90427-X

10.1007/BF01414208

10.1002/nav.3800030106

10.1111/j.1468-0262.2005.00633.x

10.1007/BF02499133

10.1006/game.1996.0064

Thông tin
Thông tin xuất bản

Mathematics of Operations Research

Tập 32 Số 2

266-283

Thông tin tác giả