  We study a class of Bayesian online selection problems with matroid
constraints. Consider a vendor who has several items to sell, with the set of
sold items being subject to some structural constraints, e.g., the set of sold
items should be independent with respect to some matroid. Each item has an
offer value drawn independently from a known distribution. Given distribution
information for each item, the vendor wishes to maximize their expected revenue
by carefully choosing which offers to accept as they arrive.
  Such problems have been studied extensively when the vendor's revenue is
compared with the offline optimum, referred to as the "prophet". In this
setting, a tight 2-competitive algorithm is known when the vendor is limited to
selling independent sets from a matroid [Kleinberg and Weinberg, 2012]. We turn
our attention to the online optimum, or "philosopher", and ask how well the
vendor can do with polynomial-time computation, compared to a vendor with
unlimited computation but with the same limited distribution information about
offers.
  We show that when the underlying constraints are laminar and the arrival of
buyers follows a natural "left-to-right" order, there is a Polynomial-Time
Approximation Scheme for maximizing the vendor's revenue. We also show that
such a result is impossible for the related case when the underlying
constraints correspond to a graphic matroid. In particular, it is
$\texttt{PSPACE}$-hard to approximate the philosopher's expected revenue to
some fixed constant $\alpha < 1$; moreover, this cannot be alleviated by
requirements on the arrival order in the case of graphic matroids.
