Dynamic Mechanism Design in Complex Environments

Abstract

Inspired by various applications including ad auctions, matching markets, and voting, mechanism design deals with the problem of designing algorithms that take inputs from strategic agents and return an outcome optimizing a given objective, while taking the strategic behavior from the agents into account.The focus of this thesis is to design mechanisms in dynamic environments that take into account rich constraints (e.g., budget constraints), features (e.g., robustness and credibility), and different types of agents (e.g., utility-maximizing agents and learning agents). Two main reasons why dynamic mechanism design is hard compared to mechanism design in a static environment are the need to make decisions in an online manner while the future might be unpredictable or even be chosen by an adversary arbitrarily, and the need to cope with strategic agents, who aim to maximize their cumulative utilities by looking into the future.We propose a framework to design dynamic mechanisms with simple structures for utility-maximizing agents without losing any optimality, which facilitates both the design for the designer and the participation for the agents. Our framework enables the design of mechanisms achieving non-trivial performance guarantees relative to the optimal mechanism that has access to all future information in advance, even though our mechanisms are not equipped with any knowledge about the future. We further develop a class of dynamic mechanisms that are robust against estimation errors in agents' valuation distributions, a class of dynamic mechanisms that are credible so that the designer is incentivized to follow the rules, and a class of dynamic mechanisms for learning agents. In addition to dynamic mechanism design frameworks, we develop statistical tools to test whether a dynamic mechanism has correctly aligned the agents' incentives, and to measure the extent of the misalignment if it exists.