Scholarlink

In the area of matching-based market design, existing models using cardinal utilities suffer from two deficiencies: First, the Hylland-Zeckhauser (HZ) mechanism [17], which has remained a classic in economics for one-sided matching markets, is intractable; computation of even an approximate equilibrium is PPAD-complete [7, 27]. Second, there is an extreme paucity of such models. This led [16] 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 of [16] using the techniques of multiplicative weights update (MWU) and conditional gradient descent (CGD). Additionally, we make the following contributions:

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Ioannis Panageas,
  • Thorben Tröbst,
  • Vijay V. Vazirani

摘要

In the area of matching-based market design, existing models using cardinal utilities suffer from two deficiencies: First, the Hylland-Zeckhauser (HZ) mechanism [17], which has remained a classic in economics for one-sided matching markets, is intractable; computation of even an approximate equilibrium is PPAD-complete [7, 27]. Second, there is an extreme paucity of such models. This led [16] 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 of [16] using the techniques of multiplicative weights update (MWU) and conditional gradient descent (CGD). Additionally, we make the following contributions: