Competitive Ratios for Submodular Secretary Problems

Improved Competitive Ratios for Submodular Secretary Problems Moran Feldman Joseph (Seffi) Naor Roy Schwartz Technion Israel Institute of Technology

Outline The classical secretary problem Algorithm Alternative arrival process Prelimineries Set functions Competitive ratio Submodular Secretary Problems State of the art and our results Partition matroid Uniform matroid 2

The Secretary Problem n secretaries, each with a unique internal value vi. The Secretaries are interviewed one after the other, in a random order. In the interview: The value of the secretary is revealed. We can hire the secretary, or dismiss her. In both cases, the decision is final. v1v2v3v4v5v6v7v8v9 Goal: Hire the best secretary with high probability. Question: How good can we do? We can succeed with probability 1/e! [Bruss84] 3

The Algorithm Algorithm 1. Inspect the first n/e secretaries; let v be the value of the best secretary among these. 2. Interview the rest of the secretaries; hire the first one with value over v. It can be shown that this algorithm succeeds with probability at least 1/e. [Bruss84] 4

The Arrival Process The Arrival Process Secretaries arrive in a random order (random permutation). Alternative Arrival Process Secretaries arrive at random times within the range [0, 1]. Equivalence of the Arrival Processes Random arrival times induce a random permutation. Choose n random arrival times, sort them, and assign them to the secretaries upon arrival. 1/2 1/3 4/5 Claim Presenting and analyzing algorithms for secretary problems under this alternative arrival process is easier. 5

Alternative Algorithm Alternative Algorithm for the Secretary Problem 1. Inspect all secretaries till time t = 1/e; let v be the best secretary among these. 2. Interview the rest of the secretaries; hire the first one with value over v. Remarks This algorithm is not identical to the previous one. For example, this algorithm might inspect no secretaries in step 1. Since this is a very simple case, the algorithms and analysis for both arrival processes are very similar. For more complex cases, the alternative arrival process yields cleaner proofs. 6

Analysis of the Alternative Algorithm Theorem The alternative algorithm succeeds with probability at least 1/e. Proof Let x be the arrival time of the best secretary. If x t, the algorithm fails. If x > t, the algorithm succeeds if: The best secretary in the range [0,x) arrives before time t. Success probability: t/x x~ U(0, 1), thus, the success probability is: 1 1 t = = ln dx t t x e t Success Fail t x 7

Set Functions Definition Given a ground set E, a set function f : 2E assigns a number to every subset of the ground set. Properties Property Definition f( ) = 0 Normalization Monotonicity For every two sets A B E: f(A) f(B) Submodularity For all sets A, B E: f(A) + f(B) f(A B) + f(A B) 8

The Improtance of Submodularity Alternative (more intuitive) Definition A function f is submodular if for sets A B E and e B: fe(A) fe(B). The economy of scale feeling of this definition made submodular functions common in economics and game theory. Submodular Function in Combinatorics Submodular functions appear frequently in combinatorial settings. Here are two simple examples: Ground Set Submodular Function Nodes of a graph The number of edges leaving a set of nodes. Collection of sets The number of elements in the union of a sub-collection. 9

Variants of the Secretary Problem Many variants of the secretary problem were considered. For example: Maximize the probability of every secretary to get hired, given that this probability must be independent of the arrival time of the secretary. [BJS10] Hire up to k secretaries with maximum total value. [Kleinberg05] Hire a set of secretaries with maximum total value which is independent in a given matroid. [BIK07] Two kinds of objectives: Complete the job with maximum probability. Maximize a given objective functions. For the second kind of objectives, algorithms are usually evaluated by their competitive ratio. 10

Competitive Ratio Notation I An instance of a secretary problem. ALG(I) The value of an algorithm ALG on I. Notice that ALG(I) is a random variable of: The arrival times. The randomness of ALG itself. OPT(I) The value of the optimal offline algorithm on I. An offline algorithm know all secretaries from the beginning. Competitive Ratio Definition: OPT ( ) ( ) I E ALG I inf I Remark: This definition of the competitive ratio is adjusted for secretary problems. 11

Submodular Secretary Problems What is it? A secretary problem where the objective function is to maximize a given submodular objective function. What problems were considered? Constraint Objective Function Previous Result Our Result 5.55 10-5 [GRST10] Partition matroid constraint (given k predefined sets, hire at most one secretary from each set) NS - 5.55 10-5 [GRST10] 0.153 NMS Uniform matroid constraint (hire up to k secretaries) NS 0.0169 [BHZ10] - NMS 0.0903 [BHZ10] 0.170 Knapsack constraint NMS 0.0104 [BHZ10] 0.0184 NMS Normalized Monotone Submodular NS Nonnegative Submodular 12

The Secretary Problem over a Partition Matroid Definition Each secretary belongs to one of k sets G1,G2, ,Gk. At most one secretary of each set can be hired. Objective: maximize a given objective function over the set of hired secretaries. Such a black box reduction works only for the alternative arrival process. Remark Algorithm for linear objectives Apply the algorithm for the standard secretary problem to each set Gi, independently. Theorem The above algorithm is e-1-competitive. Proof Follows from the linearity of the expectation since each set is a completely independent instance of the secretary problem. 13

The Secretary Problem over a Partition Matroid (cont.) Algorithm for submodular objectives 1. Inspect all secretaries till time t = . 2. Interview the rest of the secretaries. Hire secretary s from set Gi, if: No secretary of Gi was hired before. Among the secretaries of Gi seen so far, s maximizes fs(R), where R is the set of secretaries hired so far. Remark For linear functions the above algorithm degenerates to the previous one, with a different threshold time. Theorem The above algorithm is (1 ln 2) / 2 0.153-competitive. 14

The Secretary Problem over a Uniform Matroid Definition Hire at most k secretaries. Objective: maximize a given objective function over the set of hired secretaries. Algorithm for linear objectives Divide time into k intervals. Apply the algorithm for the classical secretary problem to each interval separately. Theorem The above algorithm is (e 1) e-2-competitive. Remarks The above algorithm is the analog for the alternative arrival process of the algorithm of [BHZ10]. Better algorithms are known for the linear case. 15

The Secretary Problem over a Uniform Matroid (cont.) Lemma Let si be the best secretary in the ith interval, then: ( ) s w E i = 1 1 k e OPT i e Proof The probability that an interval will get no secretary of OPT is: 1 1 k k 1 e For every interval i, let us select a random representative ri from the secretaries of OPT in interval i. Interval i 16

The Secretary Problem over a Uniform Matroid (cont.) There are k intervals and in expectation at least (1-e-1)k representatives. By symmetry, every secretary is a representative with probability at least 1-e-1. By linearity of the expectation: ( ) e r w E i 1 1 k e = = 1 1 ( ) OPT OPT i e Proof of the Theorem [the algorithm s compeitive ratio] Fix the distribution of secretaries among intervals. In expectation, the value collected in the ith interval is at least e-1 w(si). The expected value of the algorithm is at least: = 1 2 1 k e ( ) s w 1 e E OPT i e i 17

The Secretary Problem over a Uniform Matroid (cont.) Algorithm for submodular objectives Same as the algorithm for linear objectives. Inside every intervals, consider the marginal contributions of the secretaries, instead of their weights. Remark For linear functions the above algorithm degenerates to the previous one. Theorem The above algorithm is (e 1) / (e2 + e) 0.170- competitive. 18

Questions ?