The PI will consider two facets of auction design that are not only of fundamental importance, but also have defied significant positive results despite extensive research in the economics literature. These facets arise from practical constraints imposed on auctions: Budget constraints on the bidders, and asymmetric and incomplete information between the bidder and auctioneer. The PI seeks to develop and employ techniques from theoretical computer science, particularly approximation algorithms, adversarial mechanism design, stochastic control, and learning theory to develop novel tools and techniques to address these questions. The intellectual merit of the proposed research will be in blending, encompassing, and extending work on related problems in theoretical computer science, economics, stochastic decision theory, and computational learning, thereby developing new theoretical models and solutions, which in turn will impact the respective disciplines. Furthermore, it is imperative to develop such tools since the facets we consider will become critical to the successful deployment of auctions in several modern internet-based settings. The proposed work will also be broadly disseminated via workshops and specialized courses.
