Hiring a Secretary from a Poset

摘要

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 between the elements and the goal of the algorithm is to return one of the maximal elements of the poset. This is equivalent to the auction 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 k~(-k/(k-1))((1+log k~(1/(k-1))~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; the success probability approaches the classical bound of 1/e as k → 1. 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.