Scheduling with Opting Out: Improving upon Random Priority

Hervé Crès A · Herve J. Moulin

77 citations0/0 files storedOperations Research

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Voting Systems Game Theory and Applications Optimization and Search Problems

Abstract

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.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 77 citations exist upstream.

References

1969The Regulation of Queue Size by Levying Tolls 2001A New Solution to the Random Assignment Problem 1979The Efficient Allocation of Individuals to Positions 1990Optimal Incentive-Compatible Priority Pricing for the M/M/1 Queue 1985Pricing computer services: queueing effects 1990On a conjecture by gale about one-sided matching problems 1978Incentive Mechanisms for Priority Queuing Problems 1996On incentive compatibility and budget balancedness in public decision making

Cited by

2013The computational complexity of random serial dictatorship 2003Ordinal efficiency and dominated sets of assignments 2002Ordinal Efficiency and the Polyhedral Separating Hyperplane Theorem 2002Strategy-proofness and population-monotonicity for house allocation problems 2010Strategy-proof Social Choice

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.