Cost Sharing Mechanisms

Hello all,
Vast amount of literature is available on cost sharing mechanisms. Here is summary of a paper by Herve Moulin and Scott Shenker, titled, "Strategyproof sharing of submodular costs: budget balance versus efficiency". This paper appeared in Economic Theory, Volume 18, Number 3 / November, 2001.

A scenario where a service is to be allocated to n agents is studied. Each agent either may receive the service or may not receive. The cost of service depends upon set of agents served and is assumed to be a submodular function through out the paper. Each agent has a maximum willingness to pay (u_i) for receiving the service. u_i s are private to the agents. Authors explore the strategyproof mechanisms for this problem to allocate the service to subset of the agents.

Due to Green-Laffont impossibility theorem, no strategy proof mechanism is efficient as well as budget balanced.

The authors first propose a class of mechanisms that is group strategy proof, budget balanced and satisfies voluntary participation (VP), No Positive Transfers (NPT) and Consumer Sovereignty (CS). These mechanisms depend upon a cross monotonic cost sharing method for the given cost function to satisfy the above properties.

One can use the cross monotonic cost sharing method of his choice, which could be anything from egalitarian to shapley or their convex combinations. Authors also show that Shapley Value based cost sharing is the one with minimal loss in efficiency.

When efficiency is more important than budget balance, then authors propose marginal cost sharing based mechanism which belongs to the class of Groves' mechanisms (Efficient + strategy proof).

Authors show if a mechanism has to satisfy reasonable properties along with efficiency and strategy proof, marginal cost sharing mechanism is the unique mechanism.

Authors compare maximal worst case welfare loss in Shapley cost sharing mechanism vs worst case maximal budget deficit in marginal cost sharing mechanism and show that the former is smaller as compared to later.

Thus authors feel budget balanced mechanisms are better as they also satisfy group strategyproof as well as it is a rich class as compared to unique efficient mechanism.


Acknowledgements:
This paper was presented in ECL, by Radhika. She also helped in editing this summary. The inital draft of the annotation of the talk was prepared by Rohith Vallam.


---
Sujit Gujar
Research Student,
Indian Institute of Science, Bangalore.