  We consider prophet inequalities in a setting where agents correspond to both
elements in a matroid and vertices in a graph. A set of agents is feasible if
they form both an independent set in the matroid and an independent set in the
graph. Our main result is an ex-ante 1/(2d+2)-prophet inequality, where d is a
graph parameter upper-bounded by the maximum size of an independent set in the
neighborhood of any vertex.
  We establish this result through a framework that sets both dynamic prices
for elements in the matroid (using the method of balanced thresholds), and
static but discriminatory prices for vertices in the graph (motivated by recent
developments in approximate dynamic programming). The threshold for accepting
an agent is then the sum of these two prices.
  We show that for graphs induced by a certain family of interval-scheduling
constraints, the value of d is 1. Our framework thus provides the first
constant-factor prophet inequality when there are both matroid-independence
constraints and interval-scheduling constraints. It also unifies and improves
several results from the literature, leading to a 1/2-prophet inequality when
agents have XOS valuation functions over a set of items and use them for a
finite interval duration, and more generally, a 1/(d+1)-prophet inequality when
these items each require a bundle of d resources to procure.
