Challenges in Algorithmic Mechanism Design

This thesis addresses three challenges in algorithmic mechanism design, which seeks to devise computationally efficient mechanisms consisting of an outcome rule and a payment rule that implement desirable outcomes in strategic equilibrium. The first challenge that we address is the design of expressive mechanisms, i.e., mechanisms that allow the participating agents to express rich preferences. We focus on multi-item auc- tions with unit demand. For this setting we present the most expressive polynomial-time mechanism known to date that is incentive compatible for non-degenerate inputs. This mech- anism can, e.g., be used in ad auctions with per-click and per-impression valuations and it can handle a large variety of soft and hard budget constraints. The second challenge that we consider is the analysis of simplicity-expressiveness tradeoffs. We develop tools for analyzing how simplification, i.e., restricting the message space, affects the set of equilibria of a mechanism. We use these tools to analyze two representative settings, sponsored search auctions and combinatorial auctions. We find that in both cases simplifica- tion can be beneficial, either by ruling out undesirable equilibria or by promoting desirable ones. In the case of sponsored search auctions our analysis leads to a strong argument in favor of the mechanism that is used by all major search engines. Finally, and this is the third challenge, we consider the design of approximately strategyproof mechanisms. We present a framework that exploits a remarkably close connection between discriminant-based classification and the design of strategyproof mechanisms. For a given algorithmically specified outcome rule our framework finds a payment rule that makes the resulting mechanism maximally strategyproof. We support our theoretical findings by applying our framework to a multi-minded combinatorial auction with a greedy outcome rule and to an assignment problem with egalitarian outcome rule.