Efficiency of Mechanisms in Complex Markets

We provide a unifying theory for the analysis and design of efficient simple mechanisms for allocating resources to strategic players, with guaranteed good properties even when players participate in many mechanisms simultaneously or sequentially and even when they use learning algorithms to identify how to play and have incomplete information about the parameters of the game. These properties are essential in large scale markets, such as electronic marketplaces, where mechanisms rarely run in isolation and the environment is too complex to assume that the market will always converge to the classic economic equilibrium or that the participants will have full knowledge of the competition. We propose the notion of a smooth mechanism, and show that smooth mechanisms possess all the aforementioned desiderata in large scale markets. We further give guarantees for smooth mechanisms even when players have budget constraints on their payments. We provide several examples of smooth mechanisms and show that many simple mechanisms used in practice are smooth (such as formats of position auctions, uniform price auctions, proportional bandwidth allocation mechanisms, greedy combinatorial auctions). We give algorithmic characterizations of which resource allocation algorithms lead to smooth mechanisms when accompanied by appropriate payment schemes and show a strong connection with greedy algorithms on matroids. Last we show how inefficiencies of mechanisms can be alleviated when the market grows large in a canonical manner.