Operations Research · 2001 · 80 citations · 11 references
Social SciencesDecision SciencesEconomicsGame TheoryMicroeconomicsSchedulingIncentive SchemesMechanism DesignPreemptive SchedulingRandomized AlgorithmsStochastic DominanceStochastic SchedulingEquilibriumPriority AssignmentPriority Scheduling PoliciesProbabilistic Scheduling
In a scheduling problem where agents can opt out, we show that the familiar random priority (RP) mechanism can be improved upon by another mechanism dubbed probabilistic serial (PS). Both mechanisms are nonmanipulable in a strong sense, but the latter is Pareto superior to the former and serves a larger (expected) number of agents. The PS equilibrium outcome is easier to compute than the RP outcome; on the other hand, RP is easier to implement than PS. We show that the improvement of PS over RP is significant but small: at most a couple of percentage points in the relative welfare gain and the relative difference in quantity served. Both gains vanish when the number of agents is large; hence both mechanisms can be used as a proxy of each other.
11
The Regulation of Queue Size by Levying Tolls
P. Naor · Econometrica · 1969 · 1.3K citations
Business, Economics, Queuing Theory +15
A New Solution to the Random Assignment Problem
Anna Bogomolnaia, Hervé Moulin · Journal of Economic Theory · 2001 · 766 citations
Optimal Incentive-Compatible Priority Pricing for the M/M/1 Queue
Haim Mendelson, Seungjin Whang · Operations Research · 1990 · 571 citations
Business, Economics, Microeconomics +16
On Packet Switches with Infinite Storage
John Nagle · IEEE Transactions on Communications · 1987 · 381 citations