Matching with Nested and Bundled Pandora Boxes

Robin Bowers, Bo Waggoner

We consider max-weighted matching with costs for learning the weights, modeled as a "Pandora's Box" on each endpoint of an edge. Each vertex has an initially-unknown value for bein…