A Framework for the Secretary Problem on the Intersection of Matroids

Abstract

The secretary problem became one of the most prominentonline selection problems due to its numerous applications inonline mechanism design. The task is to select a maximumweight subset of elements subject to given constraints, whereelements arrive one-by-one in random order, revealing aweight upon arrival. The decision whether to select anelement has to be taken immediately after its arrival. Thedifferent applications that map to the secretary problem askfor different constraint families to be handled. The mostprominent ones are matroid constraints, which both capturemany relevant settings and admit strongly competitivesecretary algorithms. However, dealing with more involvedconstraints proved to be much more difficult, and strongalgorithms are known only for a few specific settings. In thispaper, we present a general framework for dealing with thesecretary problem over the intersection of several matroids.This framework allows us to combine and exploit the largeset of matroid secretary algorithms known in the literature.As one consequence, we get constant-competitive secretaryalgorithms over the intersection of any constant numberof matroids whose corresponding (single-)matroid secretaryproblems are currently known to have a constant-competitivealgorithm. Moreover, we show that our results extend tosubmodular objectives.