Auctions for dynamic environments: WiFi, last-minute tickets and grid computing

MohammadTaghi Hajiaghayi
Postdoc, ALADDIN Center, Carnegie Mellon University

Friday, April 28th, 3:30 pm
Wean Hall 7220

Abstract

We consider the problem of auction design for dynamic environments, in which agents arrive and depart dynamically and in which goods are inherently temporal. Motivating examples are drawn from the problem of WiFi allocation in coffee houses, last-minute tickets, and scientific grid computing. We provide a characterization for the design of truthful online auctions, such that it is a domnant strategy equilibrium for bidders to reveal their true value for resources immediately upon arrival into a system. The auctions are online, in the sense that they make allocation decisions without knowledge of the future. In a setting without priors, we provide an e-competitive (for efficiency) truthful auction for a limited-supply unit-demand problem, drawing an analogy with the classic secretary problem. We also present a 2-competitive auction (wrt efficiency) for a setting with a reusable resource, and describe a randomized online auction that achieves a competitive ratio for revenue of O(log h), where h is the ratio of maximum value to minimum value among the agents. In closing, we discuss envy-pricing and the concept of "fair equilibrium" versus "dominant equilibrium" and their relation to online auctions, and we end with several interesting directions for future work.

This is from some papers which are joint work with Erik D. Demaine (MIT), Uriel Feige (MSR), David C. Parkes (Harvard), R.D. Kleinberg (Cornell), Mohammad R. Salavatipour (U. Alberta).