Proportional scheduling, split-proofness, and merge-proofness
AbstractIf 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,
Download InfoIf 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.
Bibliographic InfoArticle provided by Elsevier in its journal Games and Economic Behavior.
Volume (Year): 63 (2008)
Issue (Month): 2 (July)
Contact details of provider:
Web page: http://www.elsevier.com/locate/inca/622836
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.:
- M. Angeles de Frutos, 1999. "Coalitional manipulations in a bankruptcy problem," Review of Economic Design, Springer, vol. 4(3), pages 255-272.
- 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.
- Moulin, Herve, 2000.
"The Proportional Random Allocation of Indivisible Units,"
2000-02, Rice University, Department of Economics.
- Hervé Moulin, 2002. "The proportional random allocation of indivisible units," Social Choice and Welfare, Springer, vol. 19(2), pages 381-413.
- 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.
- Manipushpak Mitra & Roland Hain, 2001.
"Simple Sequencing Problems with Interdependent Costs,"
Bonn Econ Discussion Papers
bgse20_2001, University of Bonn, Germany.
- Hain, Roland & Mitra, Manipushpak, 2004. "Simple sequencing problems with interdependent costs," Games and Economic Behavior, Elsevier, vol. 48(2), pages 271-291, August.
- 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.
- Manipushpak Mitra, 2000.
"Achieving the First Best in Sequencing Problems,"
Bonn Econ Discussion Papers
bgse11_2001, University of Bonn, Germany.
- 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.
- 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 & 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.
- Biung-Ghi Ju & Juan D. Moreno-Ternero, 2009.
"Progressive and merging-proof taxation,"
2009-7, Universidad de Málaga, Department of Economic Theory, Málaga Economic Theory Research Center.
- Biung-Ghi Ju & Juan D. Moreno-Ternero, 2009. "Progressive and merging-proof taxation," Working Papers 09.12, Universidad Pablo de Olavide, Department of Economics.
- JU, Biung-Ghi & MORENO-TERNERO, Juan D., . "Progressive and merging-proof taxation," CORE Discussion Papers RP -2280, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Itai Sher, 2012.
"Optimal shill bidding in the VCG mechanism,"
Springer, vol. 50(2), pages 341-387, June.
- William Thomson, 2014. "New variable-population paradoxes for resource allocation," Social Choice and Welfare, Springer, vol. 42(2), pages 255-277, February.
- Conan Mukherjee, 2013. "Weak group strategy-proof and queue-efficient mechanisms for the queueing problem with multiple machines," International Journal of Game Theory, Springer, vol. 42(1), pages 131-163, February.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei).
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.