Probabilistic Mechanisms for Cost Sharing, Rationing, and Queuing

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

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.