Composable and efficient mechanisms

We initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple mechanisms simultaneously or sequentially. We define the class of smooth mechanisms, related to smooth games defined by Roughgarden, that can be thought of as mechanisms that generate approximately market clearing prices. We show that smooth mechanisms result in high quality outcome both in equilibrium and in learning outcomes in the full information setting, as well as in Bayesian equilibrium with uncertainty about participants. Our main result is to show that smooth mechanisms compose well: smoothness locally at each mechanism implies global efficiency. For mechanisms where good performance requires that bidders do not bid above their value, we identify the notion of a weakly smooth mechanism. Weakly smooth mechanisms, such as the Vickrey auction, are approximately efficient under the no-overbidding assumption, and the weak smoothness property is also maintained by composition. In most of the paper we assume participants have quasi-linear valuations. We also extend some of our results to settings where participants have budget constraints.

Authors

• Vasilis Syrgkanis
• Éva Tardos

Keywords

• composition
• efficiency
• mechanism
• smoothness