In most real-world auction settings, bidders do not have unlimited money to spend on acquiring the goods they seek. In this talk I'll address how to maximize efficiency when bidders are subject to arbitrary publicly-known budget constraints. I'll start by presenting the optimal budget-feasible auction among those that make allocation decisions deterministically as a function of bids; notably, maximizing expected efficiency requires sometimes not allocating the good to an agent that is willing and able to pay more than all others. Then, expanding our scope to randomized mechanisms, I will introduce an auction that is optimal among all those that make allocation decisions based on the rank of each bid. Finally, I'll describe a simple auction that converges to perfect efficiency as the population size gets large, showing that budgets do not pose a significant obstacle to allocative efficiency in settings with lots of bidders.
Faculty Host: Ariel Procaccia
Series generously supported by Yahoo! Academic Relations
sawako [atsymbol] cs.cmu.edu