Axiomatic models of scheduling: fairness and incentive compatibility.

调度的公理模型：公平性和激励相容性。

• 批准号: 0414543
• 负责人: Herve Moulin
• 金额: --
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-11-01 至 2007-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0414543&HistoricalAwards=false
• 关键词: Axiomatic; models; scheduling; fairness; incentive

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

本研究计画将应用微观经济学，特别是博奕论，来分析排队与排程协定。 以前对这个问题的研究主要集中在参与者的非合作行为上--特别是决定加入一个等待者或“阻碍”--以及揭示一个人的等待成本的激励。它依赖于现金转移支付来使激励与效率相一致。首先，它关注公平和合作稳定性，特别是有限责任和工作战略转移的思想。其次，它开发了一个概率模型的调度，现金转移被排除和服务器随机ordersing不同的工作，根据他们的处理时间和发布日期。它与更熟悉的准线性模型形成对比，在准线性模型中，现金转移是可行的，而非效用在工作完成之前的等待时间中是线性的。在公平性方面，首先要考虑的是限制用户的等待责任，即，考虑到他自己的特点和其他潜在用户的数量，尽可能严格地限制他最坏情况下的延迟。PI将开发一个概率模型，并分析不同的调度方法，以确定哪种方法最好地实现社会目标。当中央处理器不能轻松地监视其处理的作业的最终消费者的身份时，客户可以将他们的作业合并为单个作业，使用吸管将单个作业拆分为几个小作业，或在联盟内转移部分作业。这些合作的调度方法是从来没有盈利将被系统地调查。调度和调度是核心的制造商品的生产，开发的共享资源，如道路网络和互联网，等等。将要开发和分析的模型包括所有这些例子，以及其他具有普遍适用性的简单调度协议。在互联网和许多其他封闭的网络中，现金转移是不可行的，而随机化是实现公平的唯一途径，通常是先服务于一个比长时间工作概率更高的短期工作。简单的最短作业优先协议不能保护短作业不被长作业“饿死”。这项研究提供了系统的解决方案，这一问题，相关的中断跨用户的工作转移，以及其他几个规范的关注。