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.:
- Moulin, Herve & Sprumont, Yves, 2004.
"On Demand Responsiveness in Additive Cost Sharing,"
2004-03, Rice University, Department of Economics.
- Moulin Herve, 1984.
"Egalitarianisme and utilitarianism in quasi-linear bargaining,"
CEPREMAP Working Papers (Couverture Orange)
- Moulin, Herve, 1985. "Egalitarianism and Utilitarianism in Quasi-linear Bargaining," Econometrica, Econometric Society, vol. 53(1), pages 49-67, January.
- 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.
- 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.
- 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, 2003. "Manipulation via merging and splitting in claims problems," Review of Economic Design, Springer, vol. 8(2), pages 205-215, October.
- Moulin, Herve & Stong, Richard, 2003.
"Filling a multicolor urn: an axiomatic analysis,"
Games and Economic Behavior,
Elsevier, vol. 45(1), pages 242-269, October.
- Hervé Moulin, 2002.
"The proportional random allocation of indivisible units,"
Social Choice and Welfare,
Springer, 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.
- 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.
- 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, 2002.
"Achieving the first best in sequencing problems,"
Review of Economic Design,
Springer, vol. 7(1), pages 75-91.
- Robert J. Dolan, 1978. "Incentive Mechanisms for Priority Queuing Problems," Bell Journal of Economics, The RAND Corporation, vol. 9(2), pages 421-436, Autumn.
- M. Angeles de Frutos, 1999. "Coalitional manipulations in a bankruptcy problem," Review of Economic Design, Springer, vol. 4(3), pages 255-272.
- 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.
- Biung-Ghi Ju & Juan Moreno-Ternero, 2011.
"Progressive and merging-proof taxation,"
International Journal of Game Theory,
Springer, vol. 40(1), pages 43-62, February.
- Biung-Ghi Ju & Juan D. Moreno-Ternero, 2009. "Progressive and merging-proof taxation," Working Papers 2009-7, Universidad de Málaga, Department of Economic Theory, Málaga Economic Theory Research Center.
- 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).
- Biung-Ghi Ju & Juan D. Moreno-Ternero, 2009. "Progressive and merging-proof taxation," Working Papers 09.12, Universidad Pablo de Olavide, Department of Economics.
- Itai Sher, 2008.
"Optimal Shill Bidding in the VCG Mechanism,"
2008-4, University of Minnesota, Department of Economics, revised 05 2009.
- 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.
- William Thomson, 2014. "New variable-population paradoxes for resource allocation," Social Choice and Welfare, Springer, vol. 42(2), pages 255-277, 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.