AF: Small: New Directions for Simplicity versus Optimality in Mechanism Design

点击翻译按钮获取中文摘要

This project aims to develop new algorithmic techniques for designing market mechanisms that faithfully model consumer behavior and other real-world constraints. This work lies within the purview of algorithmic mechanism design, which deals with the optimization of economic systems wherein many parties with conflicting objectives compete for possession of resources. Insights from this area apply to the design of all kinds of markets – big or small, brick-and-mortar or electronic – and play an increasingly important role in the rise of new electronic marketplaces such as online advertising, the cloud market, the rideshare industry, crowdsourcing marketplaces, etc. The project focuses on the objectives of maximizing the seller's revenue or the economic efficiency of the allocation. For each of these objectives, the goal is to develop solutions that are simple to implement, broadly applicable, and near optimal.The first part of this project will focus on the revenue-maximization objective under a so-called buy-many constraint. This natural constraint requires that the seller cannot limit the number of times a buyer can interact with the mechanism, and is satisfied in most real-world contexts. Imposing this constraint imparts a nice structure to the optimal mechanism, and should thereby allow for much better approximations in the absence of any further assumptions than previously known. The second part of this project will develop algorithms for efficient resource allocation in online settings where buyers arrive in the market over time and allocation decisions must be made without knowing future demand. The goal is to develop simple pricing-based allocation mechanisms that nevertheless achieve near-optimal performance. The third part of this project will consider settings where buyers are uncertain about their current or future values, and will study the effectiveness of pricing strategies such as refunds, free trials, and overuse fees as vehicles for lessening the risk faced by the buyer.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.