Chapter 9. Algorithmic Mechanism Design : Through the lens of Multiunit auctions

Mechanism design is a subfield of game theory that aims to design games whose equilibria have desired properties such as achieving high efficiency or high revenue. Algorithmic mechanism design is a subfield that lies on the border of mechanism design and computer science and deals with mechanism design in algorithmically complex scenarios that are often found in computational settings such as the Internet. The central challenge in algorithmic mechanism design is the tension between the computational constraints and the game-theoretic ones. This survey demonstrates both the tension and ways of addressing it by focusing on a single simple problem: multiunit auctions. A variety of issues will be discussed: representation, computational hardness, communication, convexity, approximations, Vickrey-Clarke-Groves (VCG) mechanisms and their generalizations, single-parameter settings vs. multiparameter settings, and the power of randomness.