  We investigate non-adaptive algorithms for matroid prophet inequalities.
Matroid prophet inequalities have been considered resolved since 2012 when
[KW12] introduced thresholds that guarantee a tight 2-approximation to the
prophet; however, this algorithm is adaptive. Other approaches of [CHMS10] and
[FSZ16] have used non-adaptive thresholds with a feasibility restriction;
however, this translates to adaptively changing an item's threshold to infinity
when it cannot be taken with respect to the additional feasibility constraint,
hence the algorithm is not truly non-adaptive. A major application of prophet
inequalities is in auction design, where non-adaptive prices possess a
significant advantage: they convert to order-oblivious posted pricings, and are
essential for translating a prophet inequality into a truthful mechanism for
multi-dimensional buyers. The existing matroid prophet inequalities do not
suffice for this application. We present the first non-adaptive constant-factor
prophet inequality for graphic matroids.
