Introduction
In many economic environments, the true value of a potential transaction is not known upfront. Consider a job market: neither the employer nor the candidate can fully assess their compatibility without investing significant time and resources into an interview process. This scenario is a classic extension of the Pandora’s Box problem, where an agent must pay an inspection cost to reveal the hidden value of an option.
While the single-sided version—where one agent chooses among multiple boxes—is well-understood via Weitzman’s indices, real-world matching is inherently two-sided. Both parties incur costs and derive values. This paper investigates the complexity of maximizing social welfare in two-sided matching markets under uncertainty, particularly when match values can be negative.
Problem Formulation
The goal is to find a matching that maximizes total welfare, defined as the sum of revealed values minus the total inspection costs incurred. In this two-sided setting, each edge $(u, w)$ in a bipartite graph has two hidden values ($v_{u,w}$ and $v_{w,u}$) and two associated inspection costs ($c_{u,w}$ and $c_{w,u}$).
A critical challenge in this research is the inclusion of negative values. In many prior models, values were assumed to be non-negative. However, in a matching context, a "bad" match (e.g., a toxic workplace or an incompetent hire) can be significantly worse than remaining unmatched. This adds a layer of complexity: an algorithm must not only decide which edges to explore but also when to stop exploring a specific edge to avoid further costs or negative outcomes.
Impossibility Results
The authors first examine several intuitive classes of algorithms to see if they can provide a constant-factor approximation of the optimal welfare. They identify three major failures:
- Bundled Algorithms: These force both sides of an edge to be inspected simultaneously.
- Vertex-based Algorithms: These make inspection decisions based solely on the properties of individual nodes, ignoring the specific interaction between partners.
- Edge-based Fixed-Orientation Algorithms: These use a deterministic rule to always inspect one specific side of an edge first.
The paper proves that all three classes fail to achieve a constant-factor approximation. To illustrate the failure of bundled algorithms, the authors propose a "bundled star graph" construction.
In the figure above, a central node $u$ is connected to many nodes $w_1, \dots, w_n$. If the system forces "bundled" inspections, both $u$ and $w_i$ must pay their costs ($c_{u,w_i}$ and $c_{w_i,u}$) at once. However, if $c_{w_i,u}$ is very high (e.g., 1) and $c_{u,w_i}$ is very low (e.g., $1/n$), it is far more efficient for $u$ to inspect first. If $u$ discovers the match is poor, $w_i$ can avoid the high cost of 1 entirely. Bundling prevents this optimization, leading to $o(1)$-approximation performance.
The Nested Box Framework
To overcome these limitations, the authors map the matching problem to the Pandora’s Nested-Box Problem. In this abstraction, opening a box reveals not a value, but another box. This perfectly mirrors the two-stage inspection process of a match: the first person's inspection reveals whether it is worth it for the second person to inspect.
The authors provide a new, constructive optimal solution for this multi-stage inspection problem. They utilize generalized Weitzman Indices, which act as "reservation prices." These indices allow the algorithm to rank potential inspections by their expected marginal benefit relative to their cost, even across multiple stages of discovery.
The 1/4-Approximation Algorithm
Building on the nested box solution, the authors develop a strategy to handle the global matching problem. The core difficulty lies in "orientation"—deciding which side of each edge should be the "outer box" (inspected first).
They propose two main approaches:
- Randomized Orientation: For every potential match, the algorithm randomly decides which side inspects first. This simple randomization breaks the symmetry that causes deterministic fixed-orientation algorithms to fail.
- Best-of-Two-Worlds: This is a deterministic alternative. It compares a global orientation of all inspections against its complete reverse and selects the one that yields higher welfare.
These approaches result in a 1/4-approximation algorithm for the general-values setting. This is a significant theoretical result because it provides a constant guarantee even when match values are correlated (e.g., if a candidate likes a firm, the firm is more likely to like the candidate).
Key Insights and Conclusion
The research highlights several counter-intuitive truths about two-sided uncertainty:
- Asynchronicity is Essential: Mandatory simultaneous evaluations (bundling) are mathematically inefficient. Sequential inspection allows the system to "fail fast" and save costs.
- Orientation Matters: The order of inspection is a primary driver of welfare. Choosing the wrong side to go first can turn a potentially positive-welfare edge into a net loss.
- Robustness to Correlation: The 1/4-approximation holds regardless of the correlation between the two sides' values, making it applicable to realistic scenarios where mutual interest is common.
While the 1/4-approximation is a milestone, it leaves an open gap compared to the 1/2-approximation typically seen in standard greedy matching. Future work may explore whether this gap can be closed or if the added complexity of inspection costs imposes a fundamental limit on achievable welfare.
Summary updated