From: Kelli McGee \(Kelly Services Inc\) (a-kellim@microsoft.com)
Date: Tue Jul 20 2004 - 13:47:01 PDT
You are invited to attend...
************************************************************************
*****************************
WHO: Mohammad Taghi Hajiaghayi
AFFILIATION: MIT and Microsoft Research
TITLE: Online Auctions, Strategyproofness and Random
Valuations
WHEN: Wed 7/21/2004
WHERE: 113/1159 Research Lecture Room, Microsoft Research
TIME: 3:30PM-5:00PM
HOST: Kamal Jain
************************************************************************
******************************
ABSTRACT:
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.
BIO:
MohammadTaghi Hajiaghayi received the Bachelor's degree in computer
engineering from Sharif University of Technology in 2000. He received
the Master's degree in Computer Science from the University of Waterloo
in 2001. Since September 2001, he is a Ph.D. candidate in Computer
Science and Artificial Intelligence Laboratory at the Massachusetts
Institute of Technology. Previously, he worked at the IBM T.J. Watson
Research Center (Department of Mathematical Sciences) and also at the
Microsoft Research (Theory group). His research interests are
algorithmic graph theory, combinatorial optimizations, distributed and
mobile computing, computational geometry and embeddings, game theory and
combinatorial auctions, and random structures and algorithms.
This archive was generated by hypermail 2.1.6 : Tue Jul 20 2004 - 13:47:19 PDT