We study efficiency and budget balance in mechanism design in the quasi-linear domain. Green and Laffont [1979] proved that one cannot generically achieve both. We consider strategyproof budget-balanced mechanisms that are approximately efficient. For deterministic mechanisms, we show that a strategyproof and budget-balanced mechanism must have a sink agent whose valuation function is ignored in selecting an alternative, and she is given the payments made by the other agents. We assume the valuations of the agents are drawn from a bounded open interval. This result strengthens Green and Laffont’s impossibility result by showing that even in a restricted domain of valuations, there does not exist a mechanism that is strategyproof, budget balanced, and takes every agent’s valuation into consideration -- a corollary of which is that it cannot be efficient. Using this result, we find a tight lower bound on the inefficiencies of strategyproof, budget-balanced mechanisms in this domain. The bound shows that the inefficiency asymptotically disappears when the number of agents is large -- a result close in spirit to Green and Laffont [1979, Theorem 9.4]. However, our results provide worst-case bounds and the best possible rate of convergence.
Next, we consider minimizing any convex combination of inefficiency and budget imbalance. We show that no deterministic mechanism can do asymptotically better than minimizing inefficiency alone.
Finally, we investigate randomized mechanisms and provide improved lower bounds on expected inefficiency. We give a tight lower bound for an interesting class of strategyproof, budget-balanced, randomized mechanisms.We also use an optimization-based approach -- in the spirit of automated mechanism design -- to provide a lower bound on the minimum achievable inefficiency of any randomized mechanism.
This talk does not assume any background on game theory or mechanism design theory.
This is a joint work with Tuomas Sandholm.
BIO:
Swaprava is a Fulbright-Nehru Post-doctoral fellow at the Computer Science Department, Carnegie Mellon University. Earlier, he was a Lecturer and Post-doctoral Fellow at the Economics and Planning Unit, Indian Statistical Institute, New Delhi. He completed his PhD from the Dept. of Computer Science and Automation, Indian Institute of Science, Bangalore. His current research interest is in the versatile area of Classical and Computational Social Choice Theory.