This research project will apply microeconomics, in particular game theory, to the analysis of queuing and scheduling protocols. Previous work on this problem has focused on the non cooperative behavior of participants - in particular the decision to join a queue or "balk"-, and the incentives to reveal one's waiting cost. It relies on cash transfers to align incentives with effciency.
The intellectual merit of this project is twofold. Firstly it focuses on fairness and cooperative stability, in particular the ideas of limited liability and the strategic tranfers of jobs. Secondly it develops a probabilistic model of scheduling,where cash transfers are ruled out and the server randomly orders the different jobs according to their processing times and release dates. It is contrasted with the more familiar quasi-linear model, where cash transfers are feasible and disutilities are linear in waiting time until job completion.
On the fairness side a first concern is to limit a user's liability to wait, i.e., to place as tight a cap as possible on his worst case delay, given his own characteristics and the number of potential other users. The PI will develop a probabilistic model and will analyze different scheduling methods to determine which method best achieves social goals.
When the central processor cannot monitor easily the identity of the final consumers of the jobs it processes, customers can merge their jobs into a single job, use straw men to split a single job into several small jobs, or transfer parts of their jobs within a coalition. The scheduling methods for which these cooperative maneuvers are never profitable will be systematically investigated.
Queuing and scheduling are central to the production of manufactured commodities, to the exploitation of congested commons such as road networks and the Internet, and much more. The models that will be developed and analyzed encompass all these examples, and other simple scheduling protocols with universal applicability. In the internet and many other congested networks, cash transfers are not feasible, and randomization is the only way to achieve fairness, typically by serving first a short job with a higher probability than a long job. The simple shortest job first protocol fails to protect short jobs from being "starved" by longer jobs. This research provides systematic solutions to this problem, to the related disruption of job transfers accross users, and to several other normative concerns. 1
