| 词条 | Probabilistic-serial procedure |
| 释义 |
The probabilistic serial procedure (PS), also called serial eating algorithm, is a procedure for fair random assignment. It yields a randomized allocation of indivisible items among several agents that is both envy-free and Pareto efficient. It was suggested by Hervé Moulin and Anna Bogomolnaia.[1] DescriptionFor each item, we create 1 loaf of bread (or other food). Initially, each agent goes to the loaf of his favorite item and starts eating it. It is possible that several agents eat the same loaf at the same time. Whenever a loaf is fully eaten, each of the agents who ate it goes to the loaf of his best remaining item and starts eating it in the same way, until all loaves are consumed. We record, for each item, what fraction of that item was eaten by each agent. These fractions define a probability distribution; we draw one of the agents at random according to this distribution, and give him the item. An important parameter to PS is the eating speed of each agent. In the simplest case, when all agents have the same entitlements, it makes sense to let all agents eat in the same speed all the time. However, when agents have different entitlements, it is possible to give the more privileged agents a higher eating speed. Moreover, it is possible to let the eating speed change with time. ExampleThere are four agents and four items (denoted w,x,y,z). The preferences of the agents are:
The agents have equal rights so we apply PS with equal and uniform eating speed of 1 unit per minute. Initially, Alice and Bob go to w and Carl and Dana go to x. Each pair eats their item simultaneously. After 1/2 minute, Alice and Bob each have 1/2 of w, while Carl and Dana each have 1/2 of x. Then, Alice and Bob go to y (their best remaining item) and Carl and Dana go to z (their best remaining item). After 1/2 minute, Alice and Bob each have 1/2 of y and Carl and Dana each have 1/2 of z. Based on the eaten fractions, item w is given to either Alice or Bob with equal probability and the same is done with item y; item x is given to either Carl or Dana with equal probability and the same is done with item z. See also
References1. ^{{cite journal|doi=10.1006/jeth.2000.2710|title=A New Solution to the Random Assignment Problem|journal=Journal of Economic Theory|volume=100|issue=2|pages=295|year=2001|last1=Bogomolnaia|first1=Anna|last2=Moulin|first2=Hervé}} 1 : Fair division protocols |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。