View PDF

Abstract:We propose a numerical algorithm for computing feasible and approximately optimal solutions of the matching for teams problem. Specifically, we introduce the notion of approximate matching equilibrium as a feasible approximation of a matching equilibrium with relaxed rationality, and we show that a true equilibrium is recovered in the limit of a sequence of approximate matching equilibria with sub-optimality approaching 0. In our approximation scheme, we parametrize the so-called transfer functions, and we show that tackling the resulting parametric primal and dual optimization problems yields two approximate matching equilibria as well as provable and computable lower and upper bounds for the optimal social welfare. Under a flexible Euclidean setting, we show that the approximation error of our scheme can be controlled to be arbitrarily close to 0, we derive an explicit computational complexity bound, and we develop an algorithm for computing approximate matching equilibria that is efficient for large-scale problems involving a large number of agent populations. We study three problems in our numerical experiments: a retail business problem, the Wasserstein barycenter problem, and a large-scale problem involving up to 1000 agent populations. We show that the proposed algorithm can produce nearly optimal approximate matching equilibria to provide quantitative managerial insights for policymakers, and that the computed sub-optimality estimates are much less conservative than theoretical estimates.

Submission history

From: Ariel Neufeld [view email]
[v1] Mon, 7 Aug 2023 12:58:40 UTC (2,866 KB)
[v2] Tue, 27 Feb 2024 09:36:41 UTC (3,140 KB)
[v3] Mon, 26 May 2025 10:37:51 UTC (5,708 KB)
[v4] Sun, 30 Aug 2026 08:31:07 UTC (2,074 KB)