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,
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
References listed on IDEAS
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.:
- Hervé Moulin, 2002.
"The proportional random allocation of indivisible units,"
Social Choice and Welfare,
Springer;The Society for Social Choice and Welfare, vol. 19(2), pages 381-413.
- Moulin, Herve, 2000. "The Proportional Random Allocation of Indivisible Units," Working Papers 2000-02, Rice University, Department of Economics.
- 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.
- Moulin, Herve, 1985. "Egalitarianism and Utilitarianism in Quasi-linear Bargaining," Econometrica, 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.
- 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, 2003. "On Demand Responsiveness in Additive Cost Sharing," Working Papers 2003-10, Rice University, Department of Economics.
- Moulin, Herve & Sprumont, Yves, 2004. "On Demand Responsiveness in Additive Cost Sharing," Working Papers 2004-03, Rice University, Department of Economics.
- Jeroen Suijs, 1996. "On incentive compatibility and budget balancedness in public decision making," Review of Economic Design, Springer;Society for Economic Design, vol. 2(1), pages 193-209, December.
- Moulin, Herve & Stong, Richard, 2003. "Filling a multicolor urn: an axiomatic analysis," Games and Economic Behavior, Elsevier, vol. 45(1), pages 242-269, October.
- Moulin, Herve, 2001. "Filling a Multicolor Urn: An Axiomatic Analysis," Working Papers 2001-01, Rice University, Department of Economics.
- 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.
- 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.
- Ju, Biung-Ghi & Miyagawa, Eiichi & Sakai, Toyotaka, 2007. "Non-manipulable division rules in claim problems and generalizations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 1-26, January.
- Youngsub Chun, 2000. "Agreement, separability, and other axioms for quasi-linear social choice problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 17(3), pages 507-521.
- Manipushpak Mitra, 2002. "Achieving the first best in sequencing problems," Review of Economic Design, Springer;Society for Economic Design, vol. 7(1), pages 75-91.
- Manipushpak Mitra, 2000. "Achieving the First Best in Sequencing Problems," Bonn Econ Discussion Papers bgse11_2001, University of Bonn, Germany.
- Biung-Ghi Ju, 2003. "Manipulation via merging and splitting in claims problems," Review of Economic Design, Springer;Society for Economic Design, vol. 8(2), pages 205-215, October.
- M. Angeles de Frutos, 1999. "Coalitional manipulations in a bankruptcy problem," Review of Economic Design, Springer;Society for Economic Design, vol. 4(3), pages 255-272.
- 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.
- 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.
- Robert J. Dolan, 1978. "Incentive Mechanisms for Priority Queuing Problems," Bell Journal of Economics, The RAND Corporation, vol. 9(2), pages 421-436, Autumn. Full references (including those not matched with items on IDEAS)