  In the area of matching-based market design, existing models using cardinal
utilities suffer from two deficiencies, which restrict applicability: 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 [Vazirani, Yannakakis 2021], [Chen
et al 2022]. Second, there is an extreme paucity of such models. This led
[Hosseini and Vazirani 2021] 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 implementations using
available solvers and very encouraging experimental results.
  [Hosseini and Vazirani 2021] raised the question of finding efficient
combinatorial algorithms, with proven running times, for these models. In this
paper, we address this question by giving algorithms based on the techniques of
multiplicative weights update (MWU) and conditional gradient descent (CGD).
Additionally, we make the following conceptual contributions to the proposal of
[Hosseini and Vazirani 2021] in order to set it on a more firm foundation:
  1) We establish a connection between HZ and Nash-bargaining-based models via
the celebrated Eisenberg-Gale convex program, thereby providing a theoretical
ratification.
  2) Whereas HZ satisfies envy-freeness, due to the presence of demand
constraints, the Nash-bargaining-based models do not. We rectify this to the
extent possible by showing that these models satisfy approximate equal-share
fairness notions.
  3) We define, for the first time, a model for non-bipartite matching markets
under cardinal utilities. It is also Nash-bargaining-based and we solve it
using CGD.
