An Introduction to Mechanism Design
Consider a decentralized communication network modeled as a graph with agents controlling the edges (pictured below). Sending information across an edge has an intrinsic cost that is known only to the agent controlling the edge. In this scenario we want to send information from one node to another and pay the lowest possible price. There are many routes to choose from, but we can ask each agent their price and easily determine the cheapest route.
However, the agents controlling the edges are rational and greedy — they can charge whatever they’d like for each edge. It is easy to fathom many different resultant strategies that would emerge on the part of the agents, many of which would involve charging substantially more than the intrsinsic cost for use of the edge. How do we keep them honest and ensure we get the genuinely cheapest price?
One way to achieve honesty is quite simple: write rules that control the agents rather than the system. This would require some kind of central authority that could enforce such a rule, an overhead that is increasingly becoming less popular. Mechanism design attempts to solve this problem without a central authority by creating rules for the system itself that incentivize the agents to behave correctly.
Mechanism design is a field in economics and game theory that takes an engineering approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally.
- Wikipedia
Is this even possible?
An interesting principle, called the revelation principle, makes it quite clear that this is possible for many situations.
The above scenario is an example of a Bayesian game, which is a game that has hidden information. In this case the hidden information was the intrisic cost of sending information down each path. (Mechanism design typically refers to these secrets as “types.”) In some games (as in the one above), there exists a Bayesian Nash equilibrium. Intuitively, this means that there exists an optimal strategy — the best response to every other possible strategy, taking into account beliefs about the other players. In the above example it might look something like “charge 2x the intrinsic cost every time.”
The revelation principle states that if there exists a Bayesian Nash equilibrium, there also exists a game with the an equilibrium where no agent lies about their hidden information. That is, everyone is truth-telling simply because telling the truth is optimal. In the above example that would mean the best strategy is always “charge the intrinsic cost exactly.”
The proof is quite simple — say there exists a strategy that involves lying. We can call the truth x and the optimal lie defined by the strategy x’. Define some function f such that x’ = f(x) for any given truth. This function effectively encapsulates the entirety of the strategy. Now, we call the outcome of the game O. In the above example O would represent the path selected for sending information. Similarly, consider the game as a function g of all the reported information O = g(x1, x2, …). We can easily construct a new game g’ defined as g’(x1, x2,…) = g(f(x1), f(x2),…). Intuitively, all we did was embed the optimal strategy into the rules of the game itself. As a result every agent will be truth-telling.
Finding A Truthful Game
Knowing that it is possible to create a game where all participants tell the truth is not the same as actually finding one. We call the rules to such a game a mechanism and we say a mechanism is truthful if truth-telling is the resultant dominant strategy in the game. More formally, a mechanism is composed of the output of the game (in the example at the top that would be which path was taken) and the payment scheme (the agents on the edges only report how much it costs for them to send the information, you can pay them differently).
A very famous mechanism is called the Vickrey-Clarke-Groves (VCG, sometimes VGC) mechanism. Assuming n agents, the mechanism takes the following form:
Where g is a game, x is hidden information, g(x) is the outcome of the game, and v is the value an agent derives from the outcome, given its hidden information. Intuitively, we create a game that maximizes for the utility across all valuations. It is important to note that this maximization only dictates the outcome of the game. The payment scheme of a VCG mechanism is as follows:
Where p is the payment to each agent, and h is an arbitrary function. The payment to each agent is simply the sum of the valuations of all the other agents. The function h is strictly dependent on the valuations of all the other agents.
A simple proof that a VCG mechanism is truth telling can be found here. The result is incredibly important as any mechanism that is a VCG mechanism will result in truth-telling.
We can quickly find a solution to the problem at the top of this post by creating a VCG mechanism. Each agent reports their cost (this will be a negative number) and we only pay those on the resultant shortest path. If we set h(v) to 0, the payment to each agent is calculated as the sum of costs on the path minus the agent’s own cost. This would be a negative number, disincentivizing agent participation in the game in the first place. Therefore we have to set h(v) to a function that will keep rational agents in the game. A nice solution here is called the Clarke pivot rule:
In our example this would translate to the negation of the cost of the shortest path if the agent’s edge did not exist. This results in a solution to the problem presented at the start of the post: pay each agent on the shortest path the difference between the cost of the shortest path without the edge and the cost of the shortest path with the edge set to 0.
A couple of examples to show how this works:
In this case the shortest path is trivial: the agent who reported a cost of 2 would be paid 3. In this trivial case we almost exactly have a Vickrey auction.
The shortest path in example is A, D, F with a cost of 6. The payment to the agent that owns A, D is 4: the cost of the shortest path without A, D (which is 7) minus the cost of the path if A, D was 0 (which is 3). The agent owning D, F is paid the same.
There’s a lot more
Mechanism design uses incentives to effectively program rational agents into behaving predictably. The math in this field is directly applicable to the recent surge in blockchain programming and cryptoeconomics, whose roots are fueled by such economic incentives. However, the analysis presented in this post is incredibly simplified. For example, it is typically hard to assume agents are rational. Even the conditions of the example presented are that each agent reports their cost simulaneously, which is hard to achieve in practice (although there are workarounds for this).
