Transcript Slides - University of Virginia, Department of Computer Science

Matroids, Secretary Problems,
and Online Mechanisms
Nicole Immorlica, Microsoft Research
Joint work with Robert Kleinberg and Moshe Babaioff
The Secretary Problem

Company wants to hire a secretary





There are n secretaries available, each of whom
will accept any offer they receive
Each secretary i has an inherent value vi
Secretaries interview in a random order, revealing
their value at the interview
Hiring decision must be made at the interview
Question: Can the company design an
interviewing procedure to guarantee that it hires
the (approximately) best secretary?
The Secretary Algorithm

Algorithm:




Observe first n/e elements. Let v=maximum.
Pick the next element whose value is > v.
Theorem: Pr(picking max elt. of S) > 1/e.*
Proof: Select best elt. if i’th best elt is best in first 1/e elts and
best elt is first among best (i-1) elts.
2nd best through (i-1)st best
i’th best
best
Threshold time t = n/e
Happens with probability (1/e) ¢ (1-1/e)i ¢ (1/i).
* Elements come in a random order.
time t = n
Generalized Secretary Problems

Input


Set of secretaries {1, …, n}, each has a value vi
Feasible or independent family of subsets of {1, …, n}
Secretaries arrive in random order, and alg. must
decide online whether to select each secretary
 Goal is to select maximum weight feasible set
 Performance measure is competitive ratio:
E[weight of selected set]/[weight of max ind. set]

Example


Multicast in a network
Each node wants an edge-disjoint path to source
Value: $7
Value: $8
Value: $10
Value: $12
Special Cases

Standard secretary problem: independent sets are
all singletons
Thm [Dynkin ‘63]: There is an algorithm with competitive
ratio (1/e).

k-Secretary problem: independent sets are all sets
of size at most k
Thm [Kleinberg ‘05]: There is an algorithm with
competitive ratio 1-Θ(k-1/2)
Matroid Secretary Problems

Defn.: A matroid consists of a universe of elements and a
family of distinguished subsets called independent sets
which satisfy:




Subsets of independent sets are independent.
Exchange property: If S,T are independent and |S| < |T| then S U
{t} is independent for some t in T.
A matroid secretary problem is a generalized secretary
problem in which the independent sets form a matroid.
The standard and k-secretary problems are matroid
secretary problems.
More Examples

Gammoid Matroids:



Graphical Matroids:



Elements (customers) are sources in a graph
Set S of sources is independent if there exist edge-disjoint paths
routing each source in S to the sink
Elements are the edges of an undirected graph G = (V;E)
Set of edges is independent if it does not contain a cycle
Truncated Partition Matroids of rank k:


Elements (items) are partitioned into m sets
Set of elements is independent if it contains at most one item
from each partition and at most k items in total (production
constraint)
Open Question
Is there a constant-competitive
secretary algorithm for all matroids?

Intuition:



In matroids, a single mistake can only ruin your chance of picking
one element of the best set
If algorithm could discard a previously selected element, matroid
properties guarantee the greedy algorithm always selects optimal
set.
Thm.: If independent sets are allowed to be an arbitrary
set system closed under containment, no algorithm can
be constant-competitive.
Our Results
1.
2.
3.
4.
O(log k)-competitive algorithm for general matroids,
where k is the rank.
16-competitive algorithm for graphical matroids.
4d-competitive algorithm for transversal matroids, where
d is the max size of an agent’s set of desired items.
If M has a c-competitive algorithm, then every truncation
of M has a 48c-competitive algorithm.
Lower bound for general set systems
Proof of lower bound





Suppose the algorithm makes its first selection at time t, and that it
chooses an element x in Si. All future selections must be elements of Si.
Let Ti be the subset of Si which have not yet been observed at time t.
The values of the elements of Ti are independent of all the information
observed up to time t; there are less than k elements in Ti and each of
them has expected value 1/k, so the expected combined value of all
remaining elements is less than 1.
The only element selected up to time t is x, whose value is at most 1.
This proves that the expected value of the set selected by the
algorithm is less than 2.
Let j = k/(2 ln(k)). Probability that at least one Si has j elements of value
1 is 1-o(1).
Therefore the maximum-weight element of I has weight lower
bounded by j=(ln n /2 ln ln n)
O(log k)-competitive algorithm
1.
2.
3.
4.
Assume the algorithm knows an integer s between
log(k)-1 and log(k).*
Sample the first n/2 elements without selecting any of
them. Let v* be the maximum value observed so far.
Pick random r in {1,…,s}.
Set threshold value w = v*/2r.
From then on, select every element independent of
previous selections whose value is at least w.
* This assumption is not needed. We can estimate s using the rank of the sample.
Single Threshold Algorithms

An algorithm which computes a threshold value v
and stopping time  and then selects every
feasible element after  whose value is at least v


O(log k)-competitive algorithm is single threshold
Counterexample: single threshold algorithms are
not constant competitive (lower-bound)


Partition matroid with k sets of size n/k
Set i has (k-1) values =1/(ci) and 1 value =1/i
Greedy Algorithms

Algorithm


Counterexample: greedy algorithms
can not be constant competitive
Weight i
Node i
Weight n-i
…

1
…

Observe a constant fraction of the input
without selecting any element
Compute a maximum weight basis among
elements observed so far
Select any feasible element which can be
exchanged with an element in the basis to
improve its weight
Open Questions


Is there a constant-competitive algorithm for general
matroids? If so, is it e-competitive?
Relaxations:



Matroid structure known in advance.
Values assigned randomly to the matroid elements.
Special cases:


Transversal matroids, gammoid matroids
Is the class of constant-competitive matroids closed under
contraction?