Secretary problems: weights and discounts

ABSTRACT

The classical secretary problem studies the problem of selecting online an element (a "secretary") with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for the classical secretary problems (see, e.g., the survey of Freeman [7]) and several variants. We study the following two extensions of the secretary problem:

• In the discounted secretary problem, there is a time-dependent "discount" factor d(t), and the benefit derived from selecting an element/secretary e at time t is d(t) · v(e). For this problem with arbitrary (not necessarily decreasing) functions d(t), we show a constant-competitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound of Ω(log n/log log n), and give a nearly-matching O(log n)-competitive algorithm.

• In the weighted secretary problem, up to K secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of K positions, with position k having weight w(k), and assigning object/secretary e to position k has benefit w(k) · v(e). The goal is to select secretaries and assign them to positions to maximize Σ_{e, k} w(k) · v(e) · x_ek where x_ek is an indicator variable that secretary e is assigned position k. We give constant-competitive algorithms for this problem.

Most of these results can also be extended to the matroid secretary case (Babaioff et al. [2]) for a large family of matroids with a constant-factor loss, and an O(log rank) loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al. These problems have connections to online mechanism design (see, e.g., Hajiaghayi et al. [9]). All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.

REFERENCES

• 1: Moshe Babaioff , Nicole Immorlica , David Kempe , Robert Kleinberg, A Knapsack Secretary Problem with Applications, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_2]
• 2: Moshe Babaioff , Nicole Immorlica , Robert Kleinberg, Matroids, secretary problems, and online mechanisms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.434-443, January 07-09, 2007, New Orleans, Louisiana
• 3: Cyrus Derman, Gerald J. Lieberman, and Sheldon M. Ross. A sequential stochastic assignment problem. Management Sci., 18:349--355, 1971.
• 4: Nedialko B. Dimitrov , C. Greg Plaxton, Competitive Weighted Matching in Transversal Matroids, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_33]
• 5: E. B. Dynkin. Optimal choice of the stopping moment of a Markov process. Dokl. Akad. Nauk SSSR, 150:238--240, 1963.
• 6: T. S. Ferguson. Who solved the secretary problem? Statistical Science, 4:282--296, 1989.
• 7: P. R. Freeman. The secretary problem and its extensions: a review. Internat. Statist. Rev., 51(2):189--206, 1983.
• 8: A. Gershkov and B. Moldovanu. The dynamic assignment of heterogenous objects: A mechanism design approach. Technical report, University of Bonn, 2007.
• 9: Mohammad Taghi Hajiaghayi , Robert Kleinberg , David C. Parkes, Adaptive limited-supply online auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988784]
• 10: Robert Kleinberg, A multiple-choice secretary algorithm with applications to online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 11: Nitish Korula and Martin Pal. Algorithms for secretary problems on graphs and hypergraphs. arXiv:0807.1139v1 {cs.DS}, 2008.
• 12: Ron Lavi , Noam Nisan, Competitive analysis of incentive compatible on-line auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.233-241, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352897]
• 13: Ron Lavi , Noam Nisan, Online ascending auctions for gradually expiring items, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 14: D. V. Lindley. Dynamic programming and decision theory. Applied Statistics, 10(1):39--51, March 1961.
• 15: M. Mahdian, P. McAffee, and D. Pennock. The secretary problem with durable employment. personal communication, 2008.
• 16: Willis T. Rasmussen and Stanley R. Pliska. Choosing the maximum from a sequence with a discount function. Appl. Math. Optim., 2(3):279--289, 1975/76.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms