Speaker: Mike Dinitz
Title: The Discounted Secretary Problem

Abstract:
The classical secretary problem studies how to select online an
element with maximum value in a randomly ordered sequence. The problem
is closely connected with online mechanism design in which agents {e}
with private values v(e) for a good arrive sequentially in random
order and the mechanism designer wishes to allocate the good to an
agent with maximum value.  The difficulty lies in the fact that an
agent's allocation must be decided irrevocably upon arrival.  A
mechanism for this problem is called alpha-competitive if it gets, in
expectation, at least a 1/alpha fraction of the (expected) optimal
offline solution.  It is well-known how to design constant-competitive
algorithms for the classical secretary problem and several variants.
In this talk we will discuss the discounted secretary problem, in
which there is a time-dependent "discount" factor d(t) and the benefit
derived from assigning the good at time t to agent e is the product of
d(t) and v(e).  For instance, the special case when d(t) is decreasing
captures the natural tension between selling early and waiting to
maximize the value of the agent receiving the good.  We provide nearly
matching logarithmic upper and lower bounds for this problem, and show
a constant-competitive algorithm when the expected optimum is known in
advance.