Probabilistic Mechanisms for Cost Sharing, Rationing, and Queuing

成本分摊、配给和排队的概率机制

• 批准号: 9809316
• 负责人: Herve Moulin
• 金额: $ 16.53万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-09-15 至 2000-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9809316&HistoricalAwards=false
• 关键词: Probabilistic; Mechanisms; Cost; Sharing; Rationing

The celebrated `tragedy of the commons` arises when a certain technology with increasing marginal cost is the common property of its users. Examples include the exploitation of fisheries and other natural resources, as well as queuing problems where users want a service and the externalities result from congestion. The first theme of this project is to compare, in a very simple model of the tragedy, two natural mechanisms where users have free access to the technology (think of the congestion externalities on the internet where entry by new users is not restricted). In one mechanism, Average Cost, each user pay the same average cost; in the other, Random Priority, users are randomly ordered ( without bias) and successively given the opportunity to buy at the `true` marginal cost. In the queuing example the AC game correspond to the unorganized queue, where the server draws one agent at random in the queue, whereas RP corresponds to the organized queue, where each agent receives a randomly drawn number and the server follows this ordering. Both mechanisms, AC and RP, lead to inefficient overproduction, but the question is which one leads to a less severe `tragedy`? Preliminary investigations show that RP tends to overproduce less, but that which game collects more social surplus depends much on the configuration of the demand (namely the social value of the goods produced). Specifically, a spread-out demand (heterogeneous users) tends to slightly favour AC, but a concentrated demand (fairly homogeneous users) strongly favors RP; moreover, the more crowded the commons, the more RP outperforms AC. Systematic investigation of these comparisons is mathematically difficult, and is pursued both formally and numerically in this project. The second, related, theme of the project is rationing. A rationing problem is an elementary model of distributive justice, where the pie is a certain amount of a single commodity and must be divided among a given set of beneficiaries. The beneficiaries differ only in the extent of their (numerical) claims (or demands) on the pie. The sum of the claims is larger than the pie. In certain rationing problems, in particular queuing problems, the demands and the pie come in indivisible units, and a probabilistic allocation method is a natural way to restore equity. Our second model formalizes probabilistic rationing, assuming that the pie and the claims are deterministic and integer valued. We determine which probabilistic method is the natural counterpart of the familiar proportional rationing method. All the usual axioms that are the key to the critical comparison of deterministic rationing methods can be easily adapted in the probabilistic model: the axioms of Consistency and Distributivity appear most promising among these. If rationing models are helpful to discuss some aspects of actual queuing algorithms, they fail to capture an essential ingredient of queuing, namely the order of arrival in the queue. For instance, two of the most common algorithms, FiFO=first in, first out, and FiLO=first in, last out, are predicated on this information. Our third model formalizes an abstract queuing algorithm and will use axioms inspired from the rationing literature to single out important algorithms such as FiFO and FiLO. Again, Consistency and Distributivity will play a leading role. A probabilistic version of queuing is explored as well. It allows us to discuss, by the axiomatic methodology, the actual algorithms used on the Internet and in other networks.

当某种边际成本不断增加的技术成为其使用者的共同财产时，就出现了著名的"公地悲剧"。这方面的例子包括渔业和其他自然资源的开发，以及用户需要服务时的排队问题和拥挤造成的外部因素。这个项目的第一个主题是比较，在一个非常简单的悲剧模型中，用户可以自由访问技术的两种自然机制（想想互联网上新用户进入不受限制的拥塞外部性）。 在一种机制中，平均成本，每个用户支付相同的平均成本;在另一种机制中，随机优先级，用户被随机排序（没有偏见），并连续给予机会以“真正的”边际成本购买。 在排队的例子中，AC游戏对应于无组织的队列，其中服务器在队列中随机抽取一个代理，而RP对应于有组织的队列，其中每个代理接收随机抽取的数字，并且服务器遵循此顺序。 AC和RP这两种机制都会导致低效的生产过剩，但问题是哪一种机制会导致不那么严重的“悲剧”？初步研究表明，RP倾向于生产过剩较少，但哪种游戏收集更多的社会剩余在很大程度上取决于需求的配置（即所生产的商品的社会价值）。具体而言，分散的需求（异构用户）往往略有青睐AC，但集中的需求（相当同质的用户）强烈青睐RP;此外，更拥挤的公地，更多的RP优于AC。 这些比较的系统研究在数学上是困难的，并在本项目中进行正式和数字。 该项目的第二个相关主题是配给。 配给问题是分配正义的一个基本模型，其中馅饼是一定数量的单一商品，必须在给定的受益者之间分配。 受益人的不同之处仅在于他们对馅饼的（数字）要求（或要求）的程度。索赔的总数大于馅饼。 在某些配给问题中，特别是排队问题，需求和馅饼是不可分割的，概率分配方法是恢复公平的自然方法。我们的第二个模型形式化的概率配给，假设馅饼和索赔是确定性和整数值。我们确定哪种概率方法是常见的比例配给方法的自然对应物。 所有通常的公理是关键的确定性配给方法的关键比较，可以很容易地适应在概率模型：公理的一致性和分布性似乎最有前途的这些。如果配给模型有助于讨论实际排队算法的某些方面，那么它们无法捕捉排队的一个基本要素，即队列中的到达顺序。例如，两个最常见的算法FiFO =先进先出和FiLO =先进后出都是基于此信息的。我们的第三个模型形式化了一个抽象的排队算法，并将使用从配给文献中获得灵感的公理来挑选重要的算法，如FiFO和FiLO。再次，一致性和分配性将发挥主导作用。一个概率版本的排队进行了探讨。 它使我们能够讨论，通过公理化方法，在互联网和其他网络中使用的实际算法。