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 xi units by agent i and one of xj units by agent j. The first job scheduled is drawn from the agents whose demand has the highest standard.
|Date of creation:||Mar 2001|
|Date of revision:|
|Contact details of provider:|| Postal: |
Phone: (713) 527-4875
Fax: (713) 285-5278
Web page: http://www.ruf.rice.edu/~econ/papers/index.htmlEmail:
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.:
- Hervé Moulin, 2002. "The proportional random allocation of indivisible units," Social Choice and Welfare, Springer, vol. 19(2), pages 381-413.
- Kaminski, Marek M., 2000. "'Hydraulic' rationing," Mathematical Social Sciences, Elsevier, vol. 40(2), pages 131-155, September.
- Young, H. P., 1988. "Distributive justice in taxation," Journal of Economic Theory, Elsevier, vol. 44(2), pages 321-335, April.
- Moulin, Herve, 2001.
"Axiomatic Cost and Surplis-Sharing,"
2001-06, Rice University, Department of Economics.
- Salvador Barbera, 1995.
"Strategy-Proof Allotment Rules,"
1142, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- 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.
- Hervé Moulin, 2000. "Priority Rules and Other Asymmetric Rationing Methods," Econometrica, Econometric Society, vol. 68(3), pages 643-684, May.
When requesting a correction, please mention this item's handle: RePEc:ecl:riceco:2000-09. 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: ()
If references are entirely missing, you can add them using this form.