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.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. 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.
Publisher Info
Paper provided by Rice University, Department of Economics in its series Working Papers with number
2000-09.
For technical questions regarding this item, or to correct its listing, contact: ().
Related research
Keywords:
Other versions of this item:
Find related papers by JEL classification: D63 - Microeconomics - - Welfare Economics - - - Equity, Justice, Inequality, and Other Normative Criteria and Measurement
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.:
Salvador Barbera, 1995.
"Strategy-Proof Allotment Rules,"
Discussion Papers
1142, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
[Downloadable!]
Other versions:
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.
[Downloadable!] (restricted)
Other versions:
Cited by: (explanations, 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.)