We Can’t Have Efficiency, Good Incentives and No Deficit

Mechanism design is the application of game theory and computer science to the design of incentives. One of the interesting results of the field is that a mechanism that shares its costs with at least some of its agents can’t be at the same time efficient, incentive-compatible and budget-balanced. In this article, we will unpack what does this mean.

The Basics

In mechanism design, a designer set the rules of a system with a number N of agents to reach a certain aim.

Types

Each agent i has private information θᵢ called the type of the agent. The set of all the possible types of the agent i is Θᵢ, which is called the type set or type profile of agent i. The set of the type profiles of all the agents is Θ. The designer knows the type profile of every agent, but not their actual type.

Utility

Given the set of all the possible outcomes X, the utility function of an agent is uᵢ: X × Θᵢ → ℝ. The designer knows the utility function from the start, but remember that she doesn’t know the actual type of each agent. Will use u without subscript for the utility of a set of agents.

Social Choice Function

The social choice function f is a function f: Θ → X, and it is a map from the set of type profiles to the set of outcomes. This is a simplified form, just to give the idea. We use this form when the setting doesn’t allow transfers between agents.

Message

A message is a communication between an agent and the mechanism designer. For every agent i the designer sets a message space Mᵢ, a set of all the possible messages that i can send. M is the set of all message spaces.

Mechanism

So we arrive at the mechanism. A mechanism ℳ is defined as ℳ = (M, φ), where M is the set of all message spaces and φ is the decision rule or cos function. The decision rule φ: M→ X maps from the set of message spaces to the set of outcomes. A mechanism is a direct mechanism if the designer can access agents’ private information. Here, φ is the social choice function f.

Cost-Sharing Mechanism

A cost-sharing mechanism is a mechanism used to allocate goods. Given the set U of agents that will get the service and a cost function C: U →ℝ⁺, a cost-sharing mechanism decides the set U and the price to charge.

A cost-sharing mechanism has optimal social welfare and is efficient if it maximizes the social welfare function W(U) = u(U) - C(U).

The Problem

We want the cost-sharing mechanism to be efficient. We want it to be budget-balanced, to recover the costs of service provisioning and incur no deficits. We want it to be incentive-compatible, which means that it should drive agents to signal truthfully their type. But there is a problem: we can’t have all these properties together.

Example

We have to allocate an excludable public good, there is a number n of agents, with n > 1, the cost function C has value 1, and we have an incentive compatible and efficient mechanism that can do for the job. Let’s suppose that all the agents value the good as 1 + ε, where ε is any negligible positive value. The resulting social welfare function has value N(1 + ε) -1. A mechanism to be incentive compatible has to grant a take-or-leave price to any new agent. We set the price in the following way: we set a threshold function tᵢ: ℝ ͫ →ℝ⁺, where, for an agent i of U, the input is the vector of length m of the other agents’ valuations (m = n - 1) and the output the price to charge to i. i receives the good only if its valuation uᵢ is greater than tᵢ. At the same time to keep optimal social welfare we have to charge 0 to i. This line of reasoning have to apply to any possible agent i. So the total charge is 0. The deficit becomes N(1 + ε) + 1 and it increases with any new entry.
This happens because we want prices to serve two colliding functions: to incentivize truthful participation and to help recover the costs of the mechanism.

Conclusions

The problem has been know since 1979 when Green and Laffont published “Incentives in Public Decision-Making”. Why should we care? Because the first step to building well-incentivized systems is to know what kind of systems we cannot build.

In the next article, we’ll see what are the two most used methods to achieve incentive-compatible mechanisms. The VCG mechanism is the most optimal solution that is efficient and incentive compatible. The Moulin method is a classical solution that gives us balanced budgets and incentive compatibility and an acceptable approximation to optimal efficiency.

Sources

1. Theory of Mechanism Design, Indian Statistical Institute, 2017, https://www.isid.ac.in/~dmishra/gmdoc/mdnotes.pdf
2. Trade-offs in cost-sharing, Mukund Sundararajan, Stanford, 2009, https://crypto.stanford.edu/portia/papers/mukund-thesis.pdf