{"id":1487,"date":"2015-09-07T08:26:56","date_gmt":"2015-09-07T12:26:56","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1487"},"modified":"2015-09-08T16:29:50","modified_gmt":"2015-09-08T20:29:50","slug":"the-matroid-secretary-problem","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1487","title":{"rendered":"The Matroid Secretary Problem"},"content":{"rendered":"

In this post, I am going to discuss the\u00a0matroid secretary problem,\u00a0<\/em>which is a very nice problem introduced by Babaioff, Immorlica, and Kleinberg [1]. \u00a0I will try to give an up-to-date account, but am far from an expert in this area, so please feel free to comment if I miss or muddle anything.<\/p>\n

Let’s warm up with the\u00a0classical secretary problem<\/em>, which has the following setup. \u00a0We want to hire a secretary. \u00a0There is a set $X$ of $n$ candidates, and each $x \\in X$ has a competency\u00a0$w(x)$. \u00a0We know that there are $n$ candidates, but\u00a0we do not know the competency\u00a0function. \u00a0The secretaries are then\u00a0presented to us in a random order. \u00a0Once a secretary is presented to us, we interview him\u00a0and discover his\u00a0competence. \u00a0We then have to make an irrevocable decision to hire him\u00a0or not. \u00a0If we hire him on the spot, the process ends. \u00a0If not, then\u00a0due to a hyper-competitive labour market, he will be hired by another firm, and we must move on to the next candidate.<\/p>\n

Let OPT be the maximum competency of all secretaries. \u00a0Our goal is to devise an\u00a0algorithm\u00a0that\u00a0hires a secretary with\u00a0competency close to OPT. \u00a0Say that an algorithm\u00a0$\\mathcal A$ is $\\alpha$-competitive if OPT \/ $\\mathbb{E} (\\mathcal A) \\leq \\alpha$, where $\\mathbb{E} (\\mathcal A)$\u00a0is the expected\u00a0competency outputted by $\\mathcal A$ for\u00a0a random permutation $\\sigma$ of $X$.<\/p>\n

Here is a $4$-competitive algorithm\u00a0for the classical secretary problem. \u00a0We reject each of first $\\frac{n}{2}$ candidates but we keep track of the highest competency, say $h$, of the first\u00a0$\\frac{n}{2}$ candidates. \u00a0We then hire the first candidate with competency at least $h$ (if none exists, we just hire the last secretary). \u00a0This algorithm\u00a0is\u00a0$4$-competitive because the\u00a0probability that the most competent secretary is in the second\u00a0half and the second most competent secretary is in the first half is more than\u00a0$\\frac{1}{4}$. \u00a0Interestingly, if we instead reject\u00a0$\\frac{1}{e}$ of the initial candidates, we obtain an $e$-competitive algorithm, which turns out to be best possible over all possible algorithms\u00a0[2].<\/p>\n

The matroid secretary problem has the same setup as above, except that there is a matroid $\\mathcal M$ on the underlying set $X$ of secretaries. \u00a0We now want to hire a\u00a0set<\/em> of secretaries, subject to the condition that our hired set is independent in\u00a0$\\mathcal M$. \u00a0Again, there is an unknown weight\u00a0function $w:X \\to \\mathbb R_+$, and\u00a0the secretaries are presented to us in a random order. \u00a0After interviewing $x$, we must make an irrevocable decision to add or not add $x$ to our currently constructed independent set $I$. \u00a0Again, the goal is to devise an algorithm\u00a0whose expected output is close to the maximum weight independent set.<\/p>\n

Note that we recover the classical secretary problem when $\\mathcal M$ is a rank-$1$ uniform matroid. \u00a0The generalization to matroids might seem like abstract nonsense, but the matroidal version is actually relevant in the theory of auctions, and has garnered a lot of interest. \u00a0The big (and still open) problem is the following conjecture.<\/p>\n

Conjecture 1 (Babaioff, Immorlica, and Kleinberg [1]). \u00a0<\/strong>For every matroid $\\mathcal M$, there is a $O(1)$-competitive algorithm.<\/p>\n

Using a clever modification of the\u00a0threshold price algorithm\u00a0<\/em>that we discussed for the classical secretary problem,\u00a0Babaioff, Immorlica, and Kleinberg [1] proved that there is a $O(\\log r)$-competitive algorithm, where $r$ is the rank of $\\mathcal M$. \u00a0In a breakthrough paper, Chakraborty and Lachish [3] devised a $O(\\sqrt{ \\log r})$-competitive algorithm. \u00a0Their algorithm is a patchwork of a few different algorithms, and is quite complicated. \u00a0Finally, the state-of-the-art is a\u00a0$O( \\log \\log r)$-competitive algorithm of Lachish [4]. \u00a0Using different tools, Feldman, Svensson, and Zenklusen [5] have also obtained a $O( \\log \\log r)$-competitive algorithm for general matroids.<\/p>\n

Another line of research is to weaken the problem slightly, in the hope of obtaining a constant-competitive algorithm. \u00a0Perhaps the most important modification is known as the\u00a0random assignment model<\/em>.\u00a0\u00a0<\/em>Note that in the original matroid secretary problem, we may as well assume that the weight function is chosen by an adversary. \u00a0In the random assignment model, we weaken the adversary, by only allowing her\u00a0to choose the\u00a0set<\/em> of weights. \u00a0The weights are then randomly assigned to the set of secretaries. \u00a0Soto [6] proved that there is a constant-competitive algorithm for all matroids in the random assignment model.<\/p>\n

Theorem 2 (Soto [6]).<\/strong> For each matroid\u00a0$\\mathcal M$, there is a $O(1)$-competitive algorithm in the random assignment model.<\/p>\n

Soto’s algorithm uses the classic decomposition of a matroid into its\u00a0principal minors.<\/em>\u00a0 See the recent paper\u00a0of Fujishige [7] for a survey of this theory. \u00a0The principal minors of a matroid are\u00a0uniformly dense\u00a0<\/em>($\\mathcal M$ is uniformly dense if $\\max_{A \\subseteq E} \\frac{|A|}{r(A)}$ is obtained by $E$). Using the decomposition, one\u00a0can reduce to the case of uniformly dense matroids, and Soto proved that there is indeed a $O(1)$-competitive algorithm for uniformly dense matroids. Note that\u00a0his proof crucially assumes that we are in the\u00a0random assignment model.<\/p>\n

There are also many other interesting variants\u00a0of the original matroid secretary problem. See Section 3 of Dinitz [8] for a nice overview.<\/p>\n

I will finish by discussing the original matroid secretary problem for restricted classes of matroids. \u00a0In [1], it is proved that Conjecture 1 holds for graphic matroids, uniform matroids, partition matroids, and bounded-degree transversal matroids. \u00a0The bounded-degree condition for transversal matroids was later removed by Dmitrov and Plaxton [9].<\/p>\n

Here is another class of matroids for which Conjecture 1 holds. \u00a0Let $\\mathcal F$ be a laminar family and $c: \\mathcal F \\to \\mathbb{N}$. \u00a0If we let $\\mathcal I$ be the set of all $I$ such that $|I \\cap F| \\leq c(F)$ for all $F \\in \\mathcal F$, then $\\mathcal I$ is the set of independent sets of a matroid. \u00a0Matroids arising in this way are called\u00a0laminar matroids. \u00a0<\/em>Note that the class of laminar matroids contains the partition matroids. \u00a0Im and Wang [10] showed that there is a constant-competitive matroid secretary algorithm for the class of laminar matroids.<\/p>\n

Finally, Dinitz and Kortsarz gave a $O(1)$-competitive algorithm for the matroid secretary problem on regular matroids<\/em>. \u00a0Their proof uses Seymour’s decomposition theorem for regular matroids [11]. \u00a0Note that graphic matroids, cographic matroids, and $R_{10}$ all have\u00a0$O(1)$-competitive matroid secretary algorithms.<\/p>\n

Using the structure theorem for $\\mathbb F$-representable matroids proved by Geelen, Gerards and Whittle [12], it may be possible to prove the following special case of Conjecture 1.<\/p>\n

Conjecture 3.<\/strong> \u00a0For every finite field $\\mathbb F$, there is a $O(1)$-competitive algorithm for the matroid secretary problem on the class of $\\mathbb F$-representable matroids.<\/p>\n

I suspect this might be tricky\u00a0since one basic class of\u00a0$\\mathbb F$-representable matroids are those representable over a subfield\u00a0$\\mathbb F’$ of\u00a0$\\mathbb F$, and I don’t see how to get a $O(1)$-competitive matroid secretary algorithm for\u00a0 $\\mathbb F’$-representable matroids unless we are doing some cunning\u00a0induction.<\/p>\n

On the other hand, the structure theorem for binary matroids is slightly simpler (due to the absence of subfields), so the following special case of Conjecture 3 may be doable.<\/p>\n

Conjecture 4.\u00a0<\/strong>There is a $O(1)$-competitive\u00a0algorithm for the matroid secretary problem on binary matroids.<\/p>\n

References<\/strong><\/p>\n

[1] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proc. SODA<\/em>, pages 434\u2013443, 2007.<\/p>\n

[2] E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Math. Dokl<\/em>, 4, 1963.<\/p>\n

[3] Sourav Chakraborty and Oded Lachish. Improved competitive ratio for the matroid secretary problem. In Proc. SODA<\/em>, pages 1702\u20131712, 2012.<\/p>\n

[4]\u00a0Lachish, Oded. O(log log rank)-competitive ratio for the matroid secretary problem. Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on<\/i>. IEEE, 2014.<\/p>\n

[5]\u00a0Feldman, Moran, Ola Svensson, and Rico Zenklusen. \u00a0A simple O(log log (rank))-competitive algorithm for the matroid secretary problem. \u00a0Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms<\/i>. SIAM, 2015.<\/p>\n

[6] Jos\u00e9 A. Soto. Matroid secretary problem in the random assignment model. In Proc. SODA<\/em>, pages 1275\u20131284, 2011.<\/p>\n

[7]\u00a0S. Fujishige. Theory of principal partitions revisited. In Research Trends in Combinatorial Optimization<\/em>, pages 127\u2013162, 2009.<\/p>\n

[8]\u00a0Dinitz, Michael. Recent advances on the matroid secretary problem. ACM SIGACT News<\/em> 44 (2013), no. 2, 126–142.<\/p>\n

[9] Nedialko B. Dimitrov and C. Greg Plaxton. Competitive weighted matching in transversal matroids. In Proc. ICALP<\/em>, pages 397\u2013408, 2008.<\/p>\n

[10] Sungjin Im and Yajun Wang. Secretary problems: laminar matroid and interval scheduling. In Proc. SODA<\/em>, pages 1265\u20131274, 2011.<\/p>\n

[11] P. D. Seymour. Decomposition of regular matroids. J. Combin. Theory Ser. B<\/em>, 28(3):305\u2013359, 1980.<\/p>\n

[12]\u00a0J. Geelen, B. Gerards, G. Whittle. Structure in minor-closed-classes of matroids. Surveys in Combinatorics, London Mathematical Society Lecture Note Series 409<\/em>, 327\u2013362, 2013.<\/p>\n","protected":false},"excerpt":{"rendered":"

In this post, I am going to discuss the\u00a0matroid secretary problem,\u00a0which is a very nice problem introduced by Babaioff, Immorlica, and Kleinberg [1]. \u00a0I will try to give an up-to-date account, but am far from an expert in this area, … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1487","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1487","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1487"}],"version-history":[{"count":39,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1487\/revisions"}],"predecessor-version":[{"id":1528,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1487\/revisions\/1528"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1487"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1487"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1487"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}