Algorithms vs. Mechanisms: Mechanism Design for Complex Environments

Abstract

Prevalent internet marketplaces and crowdsourcing platforms have started facing new computational challenges. In point of fact, these challenges exist mostly due to the strategic behavior of users, the stochastic nature of these platforms, their real-time computations, and the demand for incorporating the large-scale users data. With these challenges in front of the mechanism designer, the job of the field of algorithmic mechanism design is to find new ways of tackling them. Having this objective in mind, my dissertation is taking a closer look into various aspects of mechanism design for (real-world) applications suffering from the aforementioned challenges. We informally refer to such applications as "complex environments". In this dissertation, we particularly show how to develop general reductions from mechanism design to algorithm design, how to develop and analyze simple mechanisms for trade, and finally how to learn optimal revenue mechanisms in an online fashion by interacting with users in several rounds. Throughout this dissertation, we point out how we Incorporate techniques and ideas from combinatorial optimization, learning theory and applied probability to obtain our results.