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.

REFERENCES

• 1: Moshe Babaioff, Ron Lavi, and Elan Pavlov. Mechanism design for single-value domains. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005), pages 241--247, 2005.
• 2: Maria-Florina Balcan , Avrim Blum, Mechanism Design via Machine Learning, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.605-614, October 23-25, 2005 [doi>10.1109/SFCS.2005.50]
• 3: E. B. Dynkin. The optimum choice of the instant for stopping a markov process. Sov. Math. Dokl., 4, 1963.
• 4: Uriel Feige, Abraham Flaxman, Jason D. Hartline, and Robert D. Kleinberg. On the competitive ratio of the random sampling auction. In WINE, pages 878--886, 2005.
• 5: Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509921]
• 6: P. R. Freeman. The secretary problem and its extensions: a review. Internat. Statist. Rev., 51(2):189--206, 1983.
• 7: 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]
• 8: Jason D. Hartline , Robert McGrew, From optimal limited to unlimited supply auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.175-182, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064028]
• 9: David Karger. Random sampling and greedy sparsification for matroid optimization problems. Mathematical Programming, 82:41--81, 1998.
• 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: 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
• 12: Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
• 13: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 14: Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada