The price of anarchy of serial, average and incremental cost sharing

详细信息    查看全文

• 作者：Herv¨¦ Moulin
• 关键词：Price of anarchy ; Cost sharing ; Average cost ; Serial cost ; Incremental cost
• 刊名：Economic Theory
• 出版年：2008
• 出版时间：September, 2008
• 年：2008
• 卷：36
• 期：3
• 页码：379-405
• 全文大小：333.6 KB

文摘

We compute the price of anarchy (PoA) of three familiar demand games, i.e., the smallest ratio of the equilibrium to efficient surplus, over all convex preferences quasi-linear in money. For any convex cost, the PoA is at least \frac1n\frac{1}{n} in the average and serial games, where n is the number of users. It is zero in the incremental game for piecewise linear cost functions. With quadratic costs, the PoA of the serial game is q(\frac1logn)\theta (\frac{1}{\log n}) , and q(\frac1n)\theta (\frac{1}{n}) for the average and incremental games. This generalizes if the marginal cost is convex or concave, and its elasticity is bounded.