acceptodds
Under review as a conference paper at ICLR 2027

Learning Second-Best Mechanism in Matching Markets

Abstract

We study the sample complexity of learning the Bayesian second-best gains from trade in matching markets with unknown value and cost distributions. For independent distributions, we give a sample-based learning algorithm that always outputs a universally dominant-strategy incentive-compatible and ex-post individually rational mechanism and, with high probability, outputs an ex-ante weakly budget-balanced mechanism whose expected gains from trade are within of the second-best benchmark. For a market with unknown marginal distributions supported on and maximum feasible matching size , we establish a per-marginal sample complexity of , which is tight up to logarithmic factors. The upper bound uses a critical-contact decomposition to localize the effect of marginal perturbations, with the aggregate exposure controlled by the maximum feasible matching size . For the lower bound, we construct hard instances on star forests and show that the dependence on both and is unavoidable.

Primary area:
learning theory
Keywords:
matching market, sample complexity, gains from trade

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_5zazOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the sample complexity of learning mechanisms that approximate the Bayesian second-best gains from trade in two-sided matching markets with independent, unknown agent-type distributions. The second-best benchmark is the maximum expected gains that can be achieved using a mechanism that satisfies three properties: Bayesian incentive compatibility, interim individual rationality, and ex-ante weak budget balance, assuming the underlying distributions are known. The main result is a tight characterization, up to polylogarithmic factors, of the per-marginal sample complexity as Θ~(drh2/ε2)\widetilde{\Theta}(drh^2/\varepsilon^2), where dd is the number of agents, rr is the maximum feasible matching size, and hh bounds the agents' types. This extends the work of (Shi et al. 2026), who established tight sample-complexity bounds for learning the second-best gains from trade in bilateral trade, to the more general setting of matching markets.

The upper bound approach relies on an algorithm that uses samples of the agents' values and costs to construct a mechanism whose expected gains are close to the second-best benchmark. The approach uses a Lagrangian relaxation of the budget-balance constraint to reduce the problem to a family of optimization problems parameterized by a single multiplier. The difficulty here is that small errors in estimating individual distributions may substantially change the optimal matching. The paper shows that the effect of these errors can be controlled by examining individual agents' trading decisions. This allows one to bound the overall estimation error in terms of the maximum number of simultaneous trades. Finally, it uses additional samples to estimate the expected revenue of candidate mechanisms and combines them in a resulting mechanism that is budget-balanced, and has the desired approximation guarantee.

For the lower bound, the work first establishes a sample-complexity lower bound for one-seller star markets using statistically hard-to-distinguish distributions. It then constructs a forest of disjoint stars to obtain the full Ω(drh2/ε2)\Omega(drh^2/\varepsilon^2) lower bound. This matches the upper bound up to polylogarithmic factors.

Critical strengths

-- The paper establishes nearly matching upper and lower bounds on the sample complexity of learning the second-best gains from trade in general matching markets, extending the bilateral-trade results of Shi et al. (2026). This is a solid extension of the existing results. Problems of this type are relevant to the ML community, particularly at the intersection of learning theory and mechanism design.

-- The proofs contain some interesting and non-trivial technical ideas. The upper-bound analysis shows that estimation errors can be controlled in terms of the maximum matching size, rather than the number of possible buyer–seller pairs. For the lower bound, the authors construct hard instances on forest graphs that preserve the desired sample complexity even when the mechanism can use revenue from one part of the market to pay for trades in other parts.

Critical weaknesses

-- The novelty of the technical contributions is not sufficiently clear. Several central ingredients, including the Lagrangian characterization, the structure of the optimal matching mechanisms, and the critical-contact property, come from previous work. The paper does not adequately explain which parts of the analysis are new or how they differ from existing approaches. This makes it difficult to assess the extent of the technical advance beyond the narrow scope of this particular problem. A conclusion with a discussion about further applications would have been very useful.

-- Some of the main technical arguments could be explained better. In particular, Section 3 gives little intuition on why the distribution estimation procedure is designed as it is, or how the analysis obtains a dependence on the maximum matching size rather than the number of possible buyer–seller pairs. I found Sections 4 and 5 much better in terms of intuition and overall flow.

Additional points:

  • Please provide the full statement of Theorem 1, with all required assumptions in its main statement and not outside it.
  • I found the AI statement much more terse than I would normally expect given the ICLR guidelines.
Questions for authors
  1. Which steps in the upper-bound analysis go beyond the existing Lagrangian characterization and critical-contact results? In particular, what new difficulties arise when extending the bilateral-trade result of Shi et al. (2026) to matching markets? More concretely, is equation (2.4) the same as the one in line 090 (approx)? The introduction claims this type of lagrangean relaxation as a conceptual contribution.

  2. The upper bound explicitly includes a success probability of at least (1-\gamma), whereas Theorem 5.2 does not specify a corresponding success probability for the lower bound. Could the authors clarify the success probability assumed in Theorem 5.2, and how the two statements can be properly compared

Reviewer_maknOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the sample complexity of learning Bayesian second-best mechanisms in matching markets with unknown value and cost distributions. The authors propose a sample-based algorithm that achieves approximately optimal gains from trade while satisfying incentive compatibility, individual rationality, and ex-ante weak budget balance. By introducing a critical-contact decomposition and a star-forest lower-bound construction, the paper establishes nearly tight per-marginal sample complexity of Θ~(drh2/ϵ2)\widetilde{\Theta}(drh^2/\epsilon^2).

Critical strengths
  1. The paper extends learning second-best mechanisms from bilateral trade to general matching markets, where allocation decisions are coupled through feasibility constraints. This is a meaningful and nontrivial extension of previous work.

2.The critical-contact decomposition provides an interesting approach to controlling distributional perturbations without directly tracking changes in optimal matchings. The nearly matching upper and lower sample-complexity bounds are theoretically significant.

Critical weaknesses

The approach appears to build on established techniques, including Lagrangian duality, virtual values, distribution shading, and structural properties of maximum-weight matchings from Babaioff et al. (2026). While their combination is meaningful, the paper could more clearly highlight its novel technical contributions and distinguish them from adaptations of existing mechanism-design and learning techniques.

Questions for authors

1.Could the authors clarify which parts of the critical-contact decomposition and distributional stability analysis are fundamentally new compared with existing structural results for matching markets and sample-based bilateral trade?

Reviewer_b2jCOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper study the problem of the sample complexity of approximating up to ϵ\epsilon in high probability the expected Gain For Trade of the second best mechanism in matching markets with unknown distribution.

The authors uses a Lagrangian approach over the problem minλ≥0sup⁡M{GFT(M)+λRev(M)}min_{\lambda\ge 0} \sup_M \{GFT(M) + \lambda Rev(M) \} where MM is the set of all mechanisms that are feasible Bayesian incentive compatible and interim individually rational. The optimal mechanism is the solution of that optimization problem.

In particular the paper proves that to compute a mechanism that is almost optimal in term of the Lagrangian function for the true unknown distribution, simultaneously for all λ\lambda one can uses a number of samples proportional to (1/ϵ2)(1/\epsilon^2). Then, they suggest a binary search across all possible λ\lambda to find the best feasible mechanism.

To conclude the authors provide a sample complexity of O~(drh2/ϵ2)\tilde{\mathcal{O}}(drh^2/\epsilon^2) and a matching lower bound, where h denotes the support of the valuations, rr the maximum number of possible matches, and d is the number of agents.

Critical strengths
  • The paper is well written and the model is of general interest
  • The results are well explained
Critical weaknesses

.

Questions for authors

Could the authors clarify what is the canonical score mechanism MD,λM_{D,\lambda} ?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.