Axiomatic models of scheduling: fairness and incentive compatibility.

点击翻译按钮获取中文摘要

This research project will apply microeconomics, in particular game theory, to the analysis ofqueuing and scheduling protocols. Previous work on this problem has focused on the noncooperative behavior of participants - in particular the decision to join a queueor "balk"-, and the incentives to reveal one's waiting cost. It relies on cashtransfers to align incentives with effciency.The intellectual merit of this project is twofold. Firstly it focuses onfairness and cooperative stability, in particular the ideas of limited liability andthe strategic tranfers of jobs. Secondly it develops a probabilistic model ofscheduling,where cash transfers are ruled out and the server randomly ordersthe different jobs according to their processing times and release dates. It iscontrasted with the more familiar quasi-linear model, where cash transfers arefeasible 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 characteristicsand 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 ofthe jobs it processes, customers can merge their jobs into a single job, use straw mento split a single job into several small jobs, or transfer parts of their jobs withina coalition. The scheduling methods for which these cooperative maneuversare never profitable will be systematically investigated.Queuing and scheduling are central tothe production of manufactured commodities, to the exploitation of congestedcommons 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 protocolswith universal applicability. In the internet and many other congestednetworks, cash transfers are not feasible, and randomization is the only way toachieve fairness, typically by serving first a short job with a higher probabilitythan a long job. The simple shortest job first protocol fails to protect short jobsfrom being "starved" by longer jobs. This research provides systematic solutionsto this problem, to the related disruption of job transfers accross users,and to several other normative concerns.1