Matroids, secretary problems, and online mechanisms

Abstract

We study a generalization of the classical secretary problem which we call the "matroid secretary problem". In this problem, the elements of a matroid are presented to an online algorithm in random order. When an element arrives, the algorithm observes its value and must make an irrevocable decision regarding whether or not to accept it. The accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. This paper presents an O(log k)-competitive algorithm for general matroids (where k is the rank of the matroid), and constant-competitive algorithms for several special cases including graphic matroids, truncated partition matroids, and bounded degree transversal matroids. We leave as an open question the existence of constant-competitive algorithms for general matroids. Our results have applications in welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid.