First of all, what is mechanism design? Mechanism design is just combinatorial optimization, for which the input to the problem instance is controlled by a set of self-interested parties who might lie about their data if lying proves to be advantageous. The challenge of mechanism design is therefore not only to design an algorithm that finds a good solution to its given input, but also to do so in such a way so that all of the self-interested parties are incentivized to report their true data to the mechanism.
Auctions represent the canonical mechanism design problem: The auctioneer has a set of goods to distribute among n bidders, and the bidders each have a valuation function that determines how much utility they would receive from each subset of the goods. One common objective for a mechanism designer is to distribute the items so as to maximize social welfare: the sum utilities of all of the bidders. In addition to being able to distribute the goods, the mechanism is given the power to charge bidders some price, up to their reported valuation for the set of goods they ultimately receive.
When do there exist mechanisms to optimize social welfare? The Vickrey Auction, introduced in the early 1960s, and later generalized into the VCG Mechanism by Clarke and Groves in the 1970s gives the answer: almost always. Under quite weak conditions, the VCG mechanism defines prices which incentivize agents to report truthfully when the mechanism computes the optimal allocation given the reports. This is great news, and Vickrey won the Nobel Prize for this in 1996. But it doesn't quite close the book on social welfare maximization. The VCG mechanism requires the auctioneer to actually calculate the optimal allocation to maximize social welfare, and so when the welfare maximization problem is itself computationally difficult, it is not possible to implement the VCG mechanism. Unfortunately, the incentive properties of the VCG mechanism depend on the output allocation actually being optimal: this means that approximation algorithms for combinatorial optimization problems don't easily translate into truthful mechanisms which approximately maximize social welfare.
This brings us to one of the motivating questions for algorithmic mechanism design: When exact optimization of social welfare is a computationally difficult problem, when do there exist computationally efficient truthful algorithms which well approximate optimal social welfare? This paper considers the role that randomization plays in the answer to this question.
Lets revisit what truthful means. For a deterministic mechanism to be truthful, no matter what the reported data of the other agents, no agent i should ever be able to manipulate the mechanism by lying about his own data so as to cause the mechanism to select an outcome he prefers. There are two ways that we can generalize this to randomized mechanisms:
- A universally truthful randomized mechanism is simply a probability distribution over deterministic truthful mechanisms. The mechanism gets to flip some coins, but no matter what the outcome of the coins, no agent could have benefited by lying, even in hindsight.
- A truthful in expectation mechanism only guarantees that no agent can benefit in expectation by lying, before the mechanism's coins are flipped. For some outcomes of the coins in hindsight, agents could possibly have benefited by lying.
This paper proves a separation which answers the question: yes. Dobzinski and Dughmi demonstrate an auction problem with m items for which they prove:
- For any epsilon > 0, there exists a truthful in expectation mechanism which achieves a (1+epsilon) approximation to social welfare and runs in time poly(1/epsilon, log m).
- For any constant epsilon > 0 any universally truthful mechanism that achieves a (2-epsilon) approximation to social welfare must run in time Omega(m).
The auction for which the separation is proved is somewhat artificial, but nevertheless shows that the class of efficient truthful in expectation mechanisms is strictly broader than the class of efficient universally truthful mechanisms. This should be viewed analogously to a complexity-class separation in how it shapes our understanding of the power of efficient truthful mechanisms.
So. Come to class on Thursday to hear more!