Revealing optimal thresholds for generalized secretary problem via continuous LP: impacts on online K-item auction and bipartite K-matching with random arrival order

Abstract

We consider the general (J, K)-secretary problem, where n totally ordered items arrive in a random order. An algorithm observes the relative merits of arriving items and is allowed to make J selections. The objective is to maximize the expected number of items selected among the K best items. Buchbinder, Jain and Singh proposed a finite linear program (LP) that completely characterizes the problem, but it is difficult to analyze the asymptotic behavior of its optimal solution as n tends to infinity. Instead, we prove a formal connection between the finite model and an infinite model, where there are a countably infinite number of items, each of which has arrival time drawn independently and uniformly from [0, 1]. The finite LP extends to a continuous LP, whose complementary slackness conditions reveal an optimal algorithm which involves JK thresholds that play a similar role as the 1/e-threshold in the optimal classical secretary algorithm. In particular, for the case K=1, the J optimal thresholds have a nice 'rational description'. Our continuous LP analysis gives a very clear perspective on the problem, and the new insights inspire us; to solve two related problems. 1. We settle the open problem whether algorithms based only on relative merits can achieve optimal ratio for matroid secretary problems. We show that, for online 2-item auction with random arriving bids (the if-uniform matroid problem with K=2), an algorithm making decisions based only on relative merits cannot achieve the optimal ratio. This is in contrast with the folklore that, for online 1-item auction, no algorithm can have performance ratio strictly larger than 1/e, which is achievable by an algorithm that considers only relative merits. 2. We give a general transformation technique that takes any monotone algorithm (such as thresholdalgorithms) for the (K, K)-secretary problem, and constructs an algorithm for online bipartite K-matching with random arrival order that has at least the same performance guarantee.