Efficiency of Simple Mechanisms in Complex Markets

We consider games of incomplete information that arise from simple non-truthful mechanisms in settings with quasi-linear preferences and analyze the social welfare of the resulting allocation at Bayes-Nash equilibria and at outcomes resulting from no-regret play. We ask what are the properties of the mechanism that lead to approximately efficient allocations at equilibrium and which mechanisms lead to global approximate efficiency when players simultaneously participate in many mechanisms and have complex valuations on allocations across mechanisms. We define the class of smooth mechanisms and show that smooth mechanisms are approximately efficient and compose well. We show that several simple mechanisms are smooth for settings such as combinatorial auctions, multi-unit auctions, bandwidth sharing and position auctions.