Hiring a secretary from a poset.
Venue
Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), pp. 39-48
Publication Year
2011
Authors
Ravi Kumar, Silvio Lattanzi, Sergei Vassilvitskii, Andrea Vattani
BibTeX
Abstract
The secretary problem lies at the core of mechanism design for online auctions. In
this work we study the generalization of the classical secretary problem in a
setting where there is only a partial order be- tween the elements and the goal of
the algorithm is to return one of the maximal elements of the poset. This is
equivalent to the setting where the seller has a multidimensional objective
function with only a partial order among the outcomes. We obtain an algorithm that
succeeds with probability at least?1 + l k^{âk/(kâ1)} ((1+log^{-1/(k-1)} k)^k -1)
where k is the number of maximal elements in the poset and is the only information
about the poset that is known to the algorithm. On the other hand, we prove an
almost matching upper bound of k^{â1/(kâ1)} on the success probability of any
algorithm for this problem; this upper bound holds even if the algorithm knows the
complete structure of the poset.
