  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 being matched to a neighbor, and an algorithm must
pay some cost to observe this value. The goal is to maximize the total matched
value minus costs. Our model is inspired by two-sided settings, such as
matching employees to employers. Importantly for such settings, we allow for
negative values which cause existing approaches to fail.
  We first prove upper bounds for algorithms in two natural classes. Any
algorithm that "bundles" the two Pandora boxes incident to an edge is an
$o(1)$-approximation. Likewise, any "vertex-based" algorithm, which uses
properties of the separate Pandora's boxes but does not consider the
interaction of their value distributions, is an $o(1)$-approximation. Instead,
we utilize Pandora's Nested-Box Problem, i.e. multiple stages of inspection. We
give a self-contained, fully constructive optimal solution to the nested-boxes
problem, which may have structural observations of interest compared to prior
work. By interpreting each edge as a nested box, we leverage this solution to
obtain a constant-factor approximation algorithm. Finally, we show any
``edge-based'' algorithm, which considers the interactions of values along an
edge but not with the rest of the graph, is also an $o(1)$-approximation.
