Simple And Approximately Optimal Mechanisms Design PDF Download

The field of mechanism design seeks mechanisms (auction formats, market reg- ulations, labor contracts, insurance policies, and so on) such that participants, acting in their own self-interest, nonetheless arrive at an outcome desired by the mechanism designer. This theory models problems in online advertising, crowdsourcing, cloud computing, matching employers with employees, and many other domains. In order to be of practical use, however, a mechanism must be easy for participants to understand, and must realistically model the tradeoffs participants consider when deciding how to act. This thesis studies the canonical mechanism design problem of maximizing a seller's revenue. Classically, buyers' preferences have been modeled by the axioms of von Neumann and Morgenstern (1944)'s Expected Utility Theory (EUT). Under the further assumption that buyers are risk-neutral, the optimal mechanism can be characterized as the solution to a linear program. However, this mechanism may be complex, requiring randomness in the outcomes, and is not seen in practice. We therefore pursue two lines of inquiry. In the first, we adopt the classical risk-neutral model, and show that a certain natural and deterministic mechanism suffices to capture a constant fraction of the optimal revenue. In the second, we initiate the study of revenue-optimal mechanisms under behavioral models beyond EUT. We study the Cumulative Prospect Theory (CPT) model (Tversky and Kahneman, 1992), in which a buyer's utility for a randomized outcome does not satisfy linearity. We describe the implications for revenue maximization of this more realistic model, and provide deterministic mechanisms which obtain constant fractions of the optimal revenue.