Cost-sharing mechanism

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:

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

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.

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

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

A solution can be characterized by:

It is impossible to attain truthfulness, budget-balance and efficiency simultaneously; therefore, there are two classes of truthful 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:

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

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:

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.

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 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.

...
Wikipedia