Automated Mechanism Design: A New Application Area for Search Algorithms ?
For this first issue of Equilibria Club, I will review a paper introducing a very exciting area of research: Automated Mechanism Design! The field of Mechanism Design aims to understand and design games in which agents interact. Over the past decades, mathematically inclined economists have been able to model auctions, markets, price discrimination schemes and much more, aimed at achieving particular goals such as maximizing social welfare or profits of a particular party. A core assumption of such models is that people respond to incentives; a fact which may not be true for individuals during particular moments, but which is still a very, if not the most, likely scenario in many situations.
To understand the significance of this paper on the field of economics, I’d like to contrast it to a new development in medicine. In a recent interview, the co-founder of biotech company Moderna, Noubar Afeyan, spoke excitedly about the new frontier of personalized vaccines which they are working on:
“For every one of those patients, we’re doing what we did for the virus, over and over and over again. We get DNA sequence. We convert it into the antigenic part. We make it into an RNA. We put it in a particle.”
Personalized medicine promises to achieve a higher effectiveness than generic medicine by being able to target a very particular person and situation. The ambition of Automated Mechanism Design is to be able to do the same for Mechanism Design. Instead of having generic auctioning mechanisms, specific mechanisms can be designed which are tailored to a particular set of agents, to a particular environment, but which can also achieve a particular goal.
“This approach has several advantages: 1) it can yield better mechanisms than the ones known to date, 2) it applies beyond the problem classes studied manually to date, 3) it can circumvent seminal economic impossibility results, and 4) it shifts the burden of design from man to machine.”
Admittedly that fourth advantage sounds a bit too much like computers will soon rule the world, but until then, we’ll hopefully be able to use Automated Mechanism Design to coordinate our world.
So, how does it work?
By defining a number of parameters a mixed integer/linear program is created. These parameters include the following (which an example below will help clarify further):
- A finite set of outcomes;
- A finite set of agents;
- For each agent i, types, probability distribution over types and a corresponding utility function;
- An objective function whose expectation the designer wishes to maximize.
There are two mechanism design constraints to note which are relevant when maximizing the objective function:
Individual rationality (IR) constraints: "The utility of each agent has to be at least as great as the agent’s fallback utility, that is, the utility that the agent would receive if it did not participate in the mechanism."
Incentive compatibility (IC) constraints: "The agents should never have an incentive to misreport their type." This constraint gives us a glimpse of the complexity which agents have to deal with if they would try and make truly rational decisions, as there are different strategies which agents can adhere to: "in dominant strategies implementation, truthtelling is optimal regardless of what the other agents report. If it is optimal only given that the other agents are truthful, and given that one does not know the other agents’ types, we have implementation in Bayesian Nash equilibrium."
The economists favorite example: divorces
Let’s have a look at an example mechanism which should allow two agents to divide their property based on a mutually agreed upon mechanism:
Consider a couple getting a divorce. They jointly own a painting and the arbitrator has to decide what happens to the painting. There are 4 options to decide between: (1) the husband gets the painting, (2) the wife gets the painting, (3) the painting remains in joint ownership and is hung in a museum, and (4) the painting is burned. The husband and wife each have two possible types: one that implies not caring for the painting too much (low), and one that implies being strongly attached to the painting (high). (low) is had with probability .8, (high) with .2, by each party.
Implementation in dominant strategies
First, a mechanism can be created in which our couple’s agents should have an incentive to be truthful, regardless of the other person’s actions. In this case, the “mechanism” is nothing more than a typical game theoretic payoff matrix and shows that: “we cannot do better than always giving the painting to the husband (or always giving it to the wife). (The solver does not look for the “fairest” mechanism because fairness is not part of the objective we specified).”
Implementation in Bayesian Nash Equilibrium
Alternatively: “When we relax the incentive compatibility constraint to Bayesian Nash equilibrium, we can do better by sometimes burning the painting! The burning of the painting (with which nobody is happy per se) is sufficiently helpful in tailoring the incentives that it becomes a key part of the mechanism.”
The power of randomness
I’m often amazed at the many applications of randomization. Random functions are a key component in most cryptographic protocols. Another great example from social choice / political science theory is that when elections are held by means of a random lottery (known as sortition), the incentive to vote truthfully according to one’s preferences gets a huge boost. Moreover, randomness can also help to decrease the computational complexity of finding the solution to a set of mechanism design constraints:
In most variants of the problem, designing a deterministic mechanism is NP-complete (even with just one agent), while a randomized mechanism can be designed in polynomial time using linear programming (for any constant number of agents). Put in perspective, the designer faces uncertainty about the agents’ private information, which leads to the need for mechanism design and introduces the associated computational complexity. Interestingly, the designer can remove this complexity by making the agents face additional uncertainty (randomization in the mechanism). This comes at no loss, and in some cases at a gain, in the designer’s objective because deterministic mechanisms are a subset of randomized ones (the outcome probabilities are 0/1 for each type vector).
An example of a randomized mechanism is a payoff matrix with uncertain rewards:
How has Automated Mechanism Design fared in the real world?
The divorce example above is a very simple starting point, and many more possibilities exist for extension of Automated Mechanism Design, whereby many more assumptions are held under the looking glass. For example, more difficult mechanisms can be created which are multi-stage, or which take into account agent’s bounded rationality.
Unfortunately I could not find any code samples, though the author does mention that CPLEX is used to perform the calculations and a number of video tutorials can be found on this website. As founder and CEO of various companies, including CombineNet, Inc. and Optimized Markets, Inc., the author has delivered on customized mechanism design in many different sectors!