Online Auctions, Strategyproofness and Random Valuations

We discuss the limited-supply online auction problem, in which an auctioneer has k goods to sell and bidders arrive and depart dynamically, from a theoretical point of view and show how Economics, Scheduling theory, Probability theory and finally Graph theory have a nice intersection in this area. First we present a background on recent work in this area. Then we consider the notion of value- and time-strategyproofness (truthfulness) and show for the k=1 problem we have a strategyproof variant on the classic Secretary’s problem. Next, we consider the case in which we have re-usable goods and present the relation to finding a maximum weight matching in bipartite graphs or more generally scheduling theory. During the talk we present several algorithms which are constant competitive for revenue and/or efficiency (we define these simple terms in the talk).

This talk is from two papers joint work with Mohammad Mahdian, Robert Kleinberg and David Parkes.

Speaker Details

Mohammad-Taghi Hajiaghayi is a Senior Researcher in the Algorithms and Theoretical Computer Science group at AT&T Labs – Research. In addition, he holds a Research Affiliate position in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). He is also a Permanent Member of Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers. Before joining to AT&T Research Labs, he was a one-year Postdoctoral Fellow in the School of Computer Science at Carnegie Mellon University (with ALADDIN project) and a one-year Postdoctoral Associate in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) from which he also earned his Ph.D in 2005. He received the Master’s degree in Computer Science from the University of Waterloo in 2001 and the Bachelor’s degree in Computer Engineering from Sharif University of Technology in 2000. During his Ph.D. studies, he also worked at the IBM T.J. Watson Research Center (Department of Mathematical Sciences) and at the Microsoft Research Center (Theory group). Dr. Hajiaghayi’s research interests are network design, algorithmic graph theory, combinatorial optimizations and approximation algorithms, distributed and mobile computing, computational geometry and embeddings, game theory and combinatorial auctions, and random structures and algorithms.