Proportional scheduling, split-proofness, and merge-proofness

B-Tier
Journal: Games and Economic Behavior
Year: 2008
Volume: 63
Issue: 2
Pages: 567-587

Score contribution per author:

2.011 = (α=2.01 / 1 authors) × 1.0x B-tier

α: calibrated so average coauthorship-adjusted count equals average raw count

Abstract

If shortest (respectively longest) jobs are served first, splitting a job into smaller jobs (respectively merging several jobs) can reduce the actual wait. Any deterministic protocol is vulnerable to strategic splitting and/or merging. This is not true if scheduling is random, and users care only about expected wait. The Proportional rule draws the job served last with probabilities proportional to size, then repeats among the remaining jobs. It is immune to splitting and merging. Among split-proof protocols constructed in this recursive way, it is characterized by either one of three properties: job sizes and delays are co-monotonic; total delay is at most twice optimal delay; the worst (expected) delay of any job is at most twice the smallest feasible worst delay. A similar result holds within the family of separable rules,

Technical Details

RePEc Handle
repec:eee:gamebe:v:63:y:2008:i:2:p:567-587
Journal Field
Theory
Author Count
1
Added to Database
2026-01-26