Axiomatic models of scheduling: fairness and incentive compatibility.

本研究计划将微观经济学，特别是博弈论应用到排队和调度协议的分析中。以前关于这个问题的研究主要集中在参与者的不合作行为，特别是决定加入一个排队或“退缩”，以及揭示一个人的等待成本的动机。它依靠现金转移来使激励与效率保持一致。这个项目的智力价值是双重的。首先，它侧重于公平和合作稳定，特别是有限责任和就业战略转移的思想。其次，建立了一个概率调度模型，在该模型中，现金转移被排除，服务器根据作业的处理时间和发布日期对不同的作业进行随机排序。它与更熟悉的准线性模型不同，在准线性模型中，现金转移是可行的，在作业完成之前的等待时间是线性的。在公平方面，首先考虑的是限制用户的等待责任，即考虑到用户自身的特点和潜在的其他用户的数量，尽可能严格地限制他的最坏情况下的延迟。PI将开发一个概率模型，并将分析不同的调度方法来确定哪种方法最能实现社会目标。当中央处理器无法轻松监控其处理的作业的最终消费者身份时，客户可以将他们的作业合并为一个作业，使用稻草人将一个作业拆分成几个小作业，或者与联盟一起转移部分作业。我们将系统地研究这些合作行动永远无利可图的调度方法。排队和调度是制成品生产的核心，也是诸如道路网络和互联网等公共设施开发的核心。将要开发和分析的模型包括所有这些例子，以及其他具有普遍适用性的简单调度协议。在互联网和许多其他僵化的网络中，现金转移是不可行的，随机化是实现公平的唯一途径，通常是通过先服务于短工作的概率高于服务长工作的概率。简单的最短作业优先协议不能保护短作业免受较长作业的“饥饿”。这项研究为这个问题、与用户之间的工作转移相关的中断以及其他几个规范性问题提供了系统的解决方案。

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