The price of anarchy of serial cost sharing and other methods

Опубликовано 6 сентября 2016, 5:45

Users share an increasing marginal cost technology. A cost sharing method specifies non negative and non transferable cost shares covering costs. We look at the worst surplus gain (relative to the efficient surplus) in any Nash equilibrium when preferences are convex and quasi-linear, and otherwise arbitrary. We compare four popular methods: average cost pricing, serial cost sharing, marginal cost pricing and incremental cost sharing. No matter what the (convex) cost function, the average cost and serial methods guarantee a surplus gain no less than (1/n), where n is the number of users. Neither the marginal pricing, nor the incremental cost sharing method guarantees any positive relative gain. For any n we can choose the cost function C, so that the serial method yields the highest guaranteed surplus gain. The same statement holds for the incremental cost method. However, if the marginal cost is convex, or if it is concave and its elasticity is bounded, the guaranteed surplus gain of serial cost sharing is O(1/(log n)), whereas that of each of the three other methods is O(1/n).