Proportional scheduling, split-proofness, and merge-proofness
If shortest (respectively longest) jobs are served first, splitting a job into smaller jobs (respectively merging several jobs) can reduce the actual wait. Any deterministic protocol is vulnerable to strategic splitting and/or merging. This is not true if scheduling is random, and users care only about expected wait. The Proportional rule draws the job served last with probabilities proportional to size, then repeats among the remaining jobs. It is immune to splitting and merging. Among split-proof protocols constructed in this recursive way, it is characterized by either one of three properties: job sizes and delays are co-monotonic; total delay is at most twice optimal delay; the worst (expected) delay of any job is at most twice the smallest feasible worst delay. A similar result holds within the family of separable rules,
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Manipushpak Mitra, 2002.
"Achieving the first best in sequencing problems,"
Review of Economic Design,
Springer, vol. 7(1), pages 75-91.
- Jeroen Suijs, 1996. "On incentive compatibility and budget balancedness in public decision making," Review of Economic Design, Springer, vol. 2(1), pages 193-209, December.
- Fishburn, Peter C., 1992. "Induced binary probabilities and the linear ordering polytope: a status report," Mathematical Social Sciences, Elsevier, vol. 23(1), pages 67-80, February.
- Moulin, Herve & Stong, Richard, 2003.
"Filling a multicolor urn: an axiomatic analysis,"
Games and Economic Behavior,
Elsevier, vol. 45(1), pages 242-269, October.
- Kittsteiner, Thomas & Moldovanu, Benny, 2004.
"Priority Auctions and Queue Disciplines that Depend on Processing Time,"
Discussion Paper Series of SFB/TR 15 Governance and the Efficiency of Economic Systems
5, Free University of Berlin, Humboldt University of Berlin, University of Bonn, University of Mannheim, University of Munich.
- Thomas Kittsteiner & Benny Moldovanu, 2005. "Priority Auctions and Queue Disciplines That Depend on Processing Time," Management Science, INFORMS, vol. 51(2), pages 236-248, February.
- Moulin, Herve & Sprumont, Yves, 2005.
"On demand responsiveness in additive cost sharing,"
Journal of Economic Theory,
Elsevier, vol. 125(1), pages 1-35, November.
- Moulin, Herve & Sprumont, Yves, 2004. "On Demand Responsiveness in Additive Cost Sharing," Working Papers 2004-03, Rice University, Department of Economics.
- Moulin, Herve & Sprumont, Yves, 2003. "On Demand Responsiveness in Additive Cost Sharing," Working Papers 2003-10, Rice University, Department of Economics.
- Robert J. Dolan, 1978. "Incentive Mechanisms for Priority Queuing Problems," Bell Journal of Economics, The RAND Corporation, vol. 9(2), pages 421-436, Autumn.
- Hain, Roland & Mitra, Manipushpak, 2004.
"Simple sequencing problems with interdependent costs,"
Games and Economic Behavior,
Elsevier, vol. 48(2), pages 271-291, August.
- Manipushpak Mitra & Roland Hain, 2001. "Simple Sequencing Problems with Interdependent Costs," Bonn Econ Discussion Papers bgse20_2001, University of Bonn, Germany.
- Hervé Moulin, 2002. "The proportional random allocation of indivisible units," Social Choice and Welfare, Springer, vol. 19(2), pages 381-413.
- Moulin, Herve, 1985.
"Egalitarianism and Utilitarianism in Quasi-linear Bargaining,"
Econometric Society, vol. 53(1), pages 49-67, January.
- Moulin Herve, 1984. "Egalitarianisme and utilitarianism in quasi-linear bargaining," CEPREMAP Working Papers (Couverture Orange) 8417, CEPREMAP.
- M. Angeles de Frutos, 1999. "Coalitional manipulations in a bankruptcy problem," Review of Economic Design, Springer, vol. 4(3), pages 255-272.
- Youngsub Chun, 2000. "Agreement, separability, and other axioms for quasi-linear social choice problems," Social Choice and Welfare, Springer, vol. 17(3), pages 507-521.
- Biung-Ghi Ju, 2003. "Manipulation via merging and splitting in claims problems," Review of Economic Design, Springer, vol. 8(2), pages 205-215, October.
- Biung-Ghi Ju & Eiichi Miyagawa & Toyotaka Sakai, 2003. "Non-Manipulable Division Rules in Claim Problems and Generalizations," WORKING PAPERS SERIES IN THEORETICAL AND APPLIED ECONOMICS 200307, University of Kansas, Department of Economics, revised Aug 2005.
When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:63:y:2008:i:2:p:567-587. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.