Mechanism Design governs the design of protocols for problems of allocation-of-goods to strategic (i.e., selfish) agents and has applications in both computer science and economics. Such allocation problems are all around: advertisers compete in an auction through online search engines to post their links beside query responses; Internet traffic competes for router access; elementary students compete for a limited number of openings in an elite magnet school. These processes can aim to achieve different objectives: search engines want to maximize revenue from ad sales; the Internet wants to minimize the total communication delays of all users; school districts want to respect fairness in school assignments.
Historically, research in mechanism design focuses almost exclusively on mechanisms that are simple for the agents, requiring that it is in each agent's best interest to truthfully reveal its preference. Such mechanisms are known as revelation mechanisms. The mechanisms that result often both have complex rules and are dependent on detailed assumptions about the environment. This project develops the theory for design and analysis of non-revelation mechanisms, which may require strategic optimization by the agents, but are simple and robust. Broader impacts of this project include contribution to the economics literature, development of theory that informs the design of mechanisms in industry, and the training of undergraduates and Ph.D. students who will use the developed skills in software development jobs and research.
This project will address a number of foundational questions in non-revelation mechanism design. First, simple non-revelation mechanisms may have parameters that need to be tuned to the environment and this environment may not be stationary. For example, both supply and demand may be evolving. A goal of the project is to understand families of mechanisms that both have good performance and can be tuned directly from historical data from the mechanism, and to identify statistically efficient procedures for performing this tuning.
Second, an especially robust criterion for design is that the mechanism perform well under any environmental conditions; i.e., without any parameterization. The project will investigate the design of robust non-revelation mechanisms and quantify the extent to which robust guarantees for non-revelation mechanisms may be better than the best robust guarantees possible for revelation mechanisms.
Third, in non-revelation mechanisms, where truthful revelation is not an agent's best response, agents will need to take actions strategically. Agents may find strategically good actions may only come after some trial and error, e.g., via learning algorithms. When all agents are behaving thus, the resulting actions will be correlated. The project aims to study the performance of mechanisms under such natural dynamics and their convergence properties.
