Fair Queuing and Other Probabilistic Allocation Methods
A server processes one job per unit of time and randomly schedules the jobs requested by a given set of users; each user may request a different number of jobs.Fair queuing (Shenker 1989) schedules jobs in successive round-robin fashion, where each agent receives one unit in each round until his demand is met and the ordering is random in each round. Fair queuing * , the reverse scheduling of fair queuing, serves first (with uniform probability) one of the users with the largest remaining demand.We characterize fair queuing * by the combination of lower composition---LC---(the scheduling sequence is history independent), demand monotonicity---DM---(increasing my demand cannot result in increased delay) and two equity axioms, equal treatment ex ante---ETEA (two identical demands give the same probability distribution of service) and equal treatment ex post---ETEP (two identical demands must be served in alternating fashion). The set of dual axioms (in which ETEA and ETEP are unchanged) characterizes fair queuing.We also characterize the rich family of methods satisfying LC, DM, and the familiar consistency---CSY---axiom. They work by fixing a standard of comparison (preordering) between a demand of x i units by agent i and one of x j units by agent j . The first job scheduled is drawn from the agents whose demand has the highest standard.
Volume (Year): 27 (2002)
Issue (Month): 1 (February)
|Contact details of provider:|| Postal: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA|
Web page: http://www.informs.org/
More information through EDIRC
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.:
- Kaminski, Marek M., 2000. "'Hydraulic' rationing," Mathematical Social Sciences, Elsevier, vol. 40(2), pages 131-155, September.
- 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.
- Moulin, Herve, 2002. "Axiomatic cost and surplus sharing," Handbook of Social Choice and Welfare,in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 1, chapter 6, pages 289-357 Elsevier.
- Moulin, Herve, 2001. "Axiomatic Cost and Surplis-Sharing," Working Papers 2001-06, Rice University, Department of Economics.
- Barbera, Salvador & Jackson, Matthew O. & Neme, Alejandro, 1997. "Strategy-Proof Allotment Rules," Games and Economic Behavior, Elsevier, vol. 18(1), pages 1-21, January.
- Salvador Barbera, 1995. "Strategy-Proof Allotment Rules," Discussion Papers 1142, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Young, H. P., 1988. "Distributive justice in taxation," Journal of Economic Theory, Elsevier, vol. 44(2), pages 321-335, April.
- Hervé Moulin, 2000. "Priority Rules and Other Asymmetric Rationing Methods," Econometrica, Econometric Society, vol. 68(3), pages 643-684, May.
- Moulin, Herve, 1994. "Social choice," Handbook of Game Theory with Economic Applications,in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 2, chapter 31, pages 1091-1125 Elsevier.
- Aumann, Robert J. & Maschler, Michael, 1985. "Game theoretic analysis of a bankruptcy problem from the Talmud," Journal of Economic Theory, Elsevier, vol. 36(2), pages 195-213, August. Full references (including those not matched with items on IDEAS)
When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:27:y:2002:i:1:p:1-30. 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: (Mirko Janc)
If references are entirely missing, you can add them using this form.