  In the Secretary Problem, one has to hire the best among n candidates. The
candidates are interviewed, one at a time, at a random order, and one has to
decide on the spot, whether to hire a candidate or continue interviewing. It is
well known that the best candidate can be hired with a probability of 1/e
(Dynkin, 1963). Recent works extend this problem to settings in which multiple
candidates can be hired, subject to some constraint. Here, one wishes to hire a
set of candidates maximizing a given set function.
  Almost all extensions considered in the literature assume the objective set
function is either linear or submodular. Unfortunately, real world functions
might not have either of these properties. Consider, for example, a scenario
where one hires researchers for a project. Indeed, it can be that some
researchers can substitute others for that matter. However, it can also be that
some combinations of researchers result in synergy (see, e.g, Woolley et al.,
Science 2010, for a research about collective intelligence). The first
phenomenon can be modeled by a submoudlar set function, while the latter
cannot.
  In this work, we study the secretary problem with an arbitrary non-negative
monotone function, subject to a general matroid constraint. It is not difficult
to prove that, generally, only very poor results can be obtained for this class
of objective functions. We tackle this hardness by combining the following:
1.Parametrizing our algorithms by the supermodular degree of the objective
function (defined by Feige and Izsak, ITCS 2013), which, roughly speaking,
measures the distance of a function from being submodular. 2.Suggesting an
(arguably) natural model that permits approximation guarantees that are
polynomial in the supermodular degree (as opposed to the standard model which
allows only exponential guarantees).
