Cost-sharing mechanism

For other uses, see Cost sharing.

In economics and mechanism design, a cost-sharing mechanism is a process by which several agents decide on the scope of a public service, and how much each agent should pay for the service.

The cost of the service is higher when more agents are served, but the increase in cost is often smaller than when serving each agent individually (i.e, the cost function is a submodular set function). As a typical example, consider two agents, Alice and George, who live near a water-source, with the following distances:

Source-Alice: 8 km
Source-George: 7 km
Alice-George: 2 km

Suppose that each kilometer of water-pipe costs $1000. We have the following options:

Nobody is connected; the cost is 0.
Only George is connected; the cost is $7000.
Only Alice is connected; the cost is $8000.
Both Alice and George are connected; the cost is $9000, since the pipe can go from Source to George and then to Alice. Note that it is much cheaper than the sum of the costs of George and Alice.

The choice between these four options should depend on the valuations of the agents - how much each of them is willing to pay for being connected to the water-source.

The goal is to find a truthful mechanism that will induce the agents to reveal their true willingness-to-pay. ^[1]

Definitions

A cost-sharing problem is defined by the following functions, where i is an agent and S is a subset of agents:

Value(i) = the amount that agent i is willing to pay in order to enjoy the service.
Cost(S) = the cost of serving all and only the agents in S. E.g, in the above example Cost({Alice,George})=9000.

A solution to a cost-sharing problem is defined by:

A subset S of agents who should be served;
A payment ${\text{Pay}}(i)$ for every agent who is served.

A solution can be characterized by:

The budget surplus of a solution is the total payment minus the total cost: $Surplus:=\sum _{i\in S}{\text{Pay}}(i)-{\text{Cost}}(S)$ . We would like to have budget balance, which means that the surplus should be exactly 0.
The social welfare of a solution is the total utility minus the total cost: $Welfare:=\sum _{i\in S}{\text{Value}}(i)-{\text{Cost}}(S)$ . We would like to have efficiency, which means that the social welfare is maximized.

It is impossible to attain truthfulness, budget-balance and efficiency simultaneously; therefore, there are two classes of truthful mechanisms:

Budget-balanced mechanisms

A budget-balanced cost-sharing mechanism can be defined by a function Payment(i,S) - the payment that agent i has to pay when the subset of served agents is S. This function should satisfy the following two properties:

budget-balance: the total payment by any subset equals the total cost of serving this subset: $\forall S:\sum _{i\in S}{\text{Payment}}(i,S)={\text{Cost}}(S)$ . So if a single agent is served, he must pay all his cost, but if two or more agents are served, each of them may pay less than his individual cost because of the submodularity.
population monotonicity: the payment of an agent weakly increases when the subset of served agents shrinks: $T\supseteq S\implies {\text{Payment}}(i,T)\leq {\text{Payment}}(i,S)$ .

For any such function, a cost-sharing problem with submodular costs can be solved by the following tatonnement process:^[1]

Initially, let S be the set of all agents.
Tell each agent i that he should pay Payment(i,S).
Each agent who is not willing to pay his price, leaves S.
If any agent has left S, return to step 2.
Otherwise, finish and server the agents that remain in S.

Note that, by the population-monotonicity property, the price always increases when people leave S. Therefore, an agent will never want to return to S, so the mechanism is truthful (the process is similar to an English auction). In addition to truthfulness, the mechanism has the following merits:

Group strategyproofness - no group of agents can gain by reporting untruthfully.
No positive transfers - no agent is paid money in order to be served.
Individual rationality - no agent loses value from participation (in particular, a non-served agent pays nothing and a served agent pays at most his valuation).
Consumer sovereignty - every agent can choose to get service, if his willingness-to-pay is sufficiently large.

Moreover, any mechanism satisfying budget-balance, no-positive-transfers, individual-rationality, consumer-sovereignty and group-strategyproofness can be derived in this way using an appropriate Payment function.^[1]^{:Proposition 1}

The mechanism can select the Payment function in order to attain such goals as fairness or efficiency. When agents have equal apriori rights, some reasonable payment functions are:

The Shapley value, e.g, for two agents, the payments when both agents are served are: Payment(Alice,Both) = [Cost(Both)+Cost(Alice)-Cost(George)]/2, Payment(George,Both) = [Cost(Both)+Cost(George)-Cost(Alice)]/2.
The egalitarian solution,^[2] e.g. Payment(Alice,Both) = median[Cost(Alice), Cost(Both)/2, Cost(Both)-Cost(George)], Payment(George,Both) = median[Cost(George), Cost(Both)/2, Cost(Both)-Cost(Alice)].
When agents have different rights (e.g. some agents are more senior than others), it is possible to charge the most senior agent only his marginal cost, e.g. if George is more senior, then for every subset S which does not contain George: Payment(George,S+George) = Cost(S+George)−Cost(S). Similarly, the next-most-senior agent can pay his marginal remaining cost, and so on.

The above cost-sharing mechanisms are not efficient - they do not always select the allocation with the highest social welfare. But, when the payment function is selected to be the Shapley value, the loss of welfare is minimized.^[1]^{:Proposition 2}

Socially-efficient mechanisms

A different class of cost-sharing mechanisms are the VCG mechanisms. A VCG mechanism always selects the socially-optimal allocation - the allocation that maximizes the total utility of the served agents minus the cost of serving them. Then, each agent receives the welfare of the other agents, and pays an amount that depends only on the valuations of the other agents. Moreover, all VCG mechanisms satisfy the consumer-sovereignty property.

There is a single VCG mechanism which also satisfies the requirements of no-positive-transfers and individual-rationality - it is the Marginal Cost Pricing mechanism.^[1]^{:Proposition 3} This is a special VCG mechanism in which each non-served agent pays nothing, and each served agent pays:

Pay(i)=Value(i)-[Welfare(All)-Welfare(All\setminus \{i\})]

I.e, each agent pays his value, but gets back the welfare that is added by his presence. Thus, the interests of the agent are aligned with the interests of society (maximizing the social welfare) so the mechanism is truthful.

The problem with this mechanism is that it is not budget-balanced - it runs a deficit. Consider the above water-pipe example, and suppose both Alice and George value the service as $10000. When only Alice is served, the welfare is 10000-8000=2000; when only George is served; the welfare is 10000-7000=3000; when both are served, the welfare is 10000+10000-9000=11000. Therefore, the Marginal Cost Pricing mechanism selects to serve both agents. George pays 10000-(11000-2000)=1000 and Alice pays 10000-(11000-3000)=2000. The total payment is only 3000, which is less than the total cost of 9000.

Moreover, the VCG mechanism is not group-strategyproof: an agent can help other agents by raising his valuation, without harming himself.^[1]

References

1 2 3 4 5 6 Moulin, Hervé; Shenker, Scott (2001). "Strategyproof sharing of submodular costs:budget balance versus efficiency". Economic Theory. 18 (3): 511. doi:10.1007/PL00004200.
↑ Dutta, Bhaskar; Ray, Debraj (1989). "A Concept of Egalitarianism Under Participation Constraints". Econometrica. 57 (3): 615. doi:10.2307/1911055. JSTOR 1911055.

This article is issued from Wikipedia - version of the 9/11/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Cost-sharing mechanism

Definitions

Budget-balanced mechanisms

Socially-efficient mechanisms

See also

References