Time-Efficient Algorithms for Nash-Bargaining-Based Matching Market Models

Ioannis Panageas, Thorben Tröbst, Vijay V. Vazirani

TL;DR

This paper tackles the computational intractability of existing Nash-bargaining-based matching market models, which use cardinal utilities. The authors introduce novel, time-efficient algorithms using multiplicative weights update (MWU) and conditional gradient descent (CGD) to solve these models, including a new model for non-bipartite matching markets. This work makes matching markets with cardinal utilities more practical and efficient for real-world applications.

What Problem Does This Paper Address?

Designing efficient and fair markets is a crucial problem in economics and computer science. Matching markets, where agents are matched with goods or services, are a prime example. While mechanisms like the Hylland-Zeckhauser (HZ) mechanism offer desirable game-theoretic properties (like Pareto optimality and envy-freeness) for matching markets with cardinal utilities, they suffer from extreme computational intractability. This has led to a scarcity of such models and efficient algorithms.

A promising alternative is the Nash-bargaining-based approach, which can be formulated as convex programs. While these programs are theoretically solvable in polynomial time, existing implementations are often too slow for practical use. Furthermore, extending these models to more complex scenarios like non-bipartite matching markets has been a challenge. This paper aims to bridge this gap by providing fast algorithms with proven running times for a rich class of Nash-bargaining-based matching market models, including a new model for non-bipartite matching.

Methods

The core of this paper lies in developing efficient algorithms for solving Nash-bargaining-based matching market models. The authors leverage two key algorithmic techniques:

  • Multiplicative Weights Update (MWU): This meta-algorithm is used to find approximate Nash bargaining solutions. The approach involves transforming the problem into a feasibility program and then using MWU to find an approximate feasible solution. This technique is adapted to handle the specific constraints of matching markets, including endowments. The paper presents MWUA (Algorithm 1) for linear utilities and a modified version (Algorithm 2) for piecewise-linear concave utilities.
  • Conditional Gradient Descent (CGD): This first-order optimization method is employed for problems where the objective function might not be smooth or Lipschitz. The authors adapt CGD to handle the specific structure of the convex programs arising from Nash bargaining in matching markets. They introduce a "quadratic extension" of the objective function to ensure smoothness and use combinatorial matching algorithms for efficient projection steps. This leads to Algorithm 3 for linear utilities and Algorithm 4 for SPLC utilities in non-bipartite matching markets.

The paper also introduces a new model for non-bipartite matching markets under cardinal utilities, which is then solved using CGD.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Theory and Practice: The paper successfully bridges the gap between theoretically sound but computationally intractable mechanisms (like HZ) and practical, efficient algorithms for Nash-bargaining-based matching markets.
  • MWU for Feasibility: A key insight is the application of MWU not just for optimization but also for finding approximately feasible solutions to a transformed "feasibility program." This connection between feasibility and KKT conditions is crucial for proving optimality.
  • CGD with Combinatorial Primitives: The authors demonstrate how to effectively use CGD by replacing expensive projection steps with efficient combinatorial matching algorithms, making the approach practical.
  • New Non-Bipartite Model: The introduction of a Nash-bargaining-based model for non-bipartite matching markets is a significant contribution, opening up new avenues for research in this area.
  • Approximate Fairness Guarantees: The paper shows that these models satisfy approximate equal-share fairness properties, which are important game-theoretic guarantees.

Key Results

  • Time-Efficient Algorithms: The paper provides algorithms with proven running times for various Nash-bargaining-based matching market models, including linear, SPLC, one-sided, two-sided, and non-bipartite settings. For instance, MWUA for LiAD runs in $O(\frac{n \log n}{\epsilon^2})$ time, and CGD for linear utilities runs in $O(\frac{1}{\epsilon^2})$ iterations.
  • New Non-Bipartite Model: A novel Nash-bargaining-based model for non-bipartite matching markets is introduced.
  • Approximate Equal-Share Fairness: The authors prove that their models satisfy approximate equal-share fairness properties, with the exact factor depending on the utility function. For linear utilities, this is shown to be at least $1/2$.
  • Practical Implementations: The algorithms are designed to be efficient and amenable to practical implementation, leveraging standard optimization techniques and combinatorial algorithms.

Limitations and Future Work

  • Approximation Guarantees: The algorithms provide $\epsilon$-approximate solutions. While efficient, achieving exact solutions might still be computationally challenging.
  • SPLC Utility Complexity: The analysis for SPLC utilities, while successful, involves more complex algorithms and potentially higher computational costs compared to linear utilities.
  • Generalizations: The paper focuses on specific types of utility functions (linear, SPLC). Exploring other utility classes or more complex market structures could be future work.
  • Experimental Validation: While the paper mentions encouraging experimental results in [33], this specific paper focuses on theoretical algorithm design and analysis. Further experimental validation of the proposed algorithms would be valuable.

Summary updated

Abstract

In the area of matching-based market design, existing models using cardinal utilities suffer from two deficiencies: First, the Hylland-Zeckhauser (HZ) mechanism, which has remained a classic in economics for one-sided matching markets, is intractable; computation of even an approximate equilibrium is PPAD-complete. Second, there is an extreme paucity of such models. This led Hosseini and Vazirani (2022) to define a rich collection of Nash-bargaining-based models for one-sided and two-sided matching markets, in both Fisher and Arrow-Debreu settings, together with very fast implementations using available solvers and very encouraging experimental results. In this paper, we give fast algorithms with proven running times for the models introduced by Hosseini and Vazirani, using the techniques of multiplicative weights update (MWU) and conditional gradient descent (CGD). Additionally, we make the following contributions: (1) By Tröbst and Vazirani (2024), a linear one-sided Nash-bargaining-based matching market satisfies envy-freeness within factor two. We show that the other models satisfy approximate equal-share fairness, where the exact factor depends on the utility function being used in the particular model. (2) We define a Nash-bargaining-based model for non-bipartite matching markets and give fast algorithms for it using conditional gradient descent.
BibTeX
@inproceedings{panageas2024time,
  author = {Ioannis Panageas and Thorben Tröbst and Vijay V. Vazirani},
  title = {{Time-Efficient Algorithms for Nash-Bargaining-Based Matching Market Models}},
  booktitle = {WINE},
  year = {2024},
  doi = {10.1007/978-3-032-08560-3\_7},
}
Figure