Combinatorial Markov Search

A decisionmaker faces n alternatives, each of which represents a potential reward. After investing costly resources into investigating the alternatives, the decisionmaker selects one (or more generally a feasible subset), and receives the associated reward(s). We model each alternative as a Markov Search Process (MSP), a type of undiscounted Markov Decision Process on a finite acyclic graph, and call this problem Combinatorial Markov Search (CMS). CMS broadly generalizes recent NP-hard problems of interest such as Pandora's Box with nonobligatory inspection. Despite the seemingly adaptive and interactive nature of the problem, we construct online algorithms for CMS that explore each alternative sequentially, either selecting or discarding it before moving to the next. We first show that any ex-ante prophet inequality can be converted into an (inefficient) online algorithm for CMS with the same approximation guarantee. Then, for any matroid feasibility constraint, we construct a polynomial-time (1/2 -ϵ)-approximation algorithm for CMS. Our construction also implies incentive-compatible mechanisms with constant Price of Anarchy for a strategic version of the problem that generalizes auctions with inspection costs.