Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu

This paper addresses two deficiencies of models in the area of matching-based market design. The first arises from the recent realization that the most prominent solution that uses cardinal utilities, namely the Hylland-Zeckhauser (HZ) mechanism, is intractable; in particular, the problem of computing even an approximate equilibrium for it is PPAD-complete. The second is the extreme paucity of models that use cardinal utilities; this stands in sharp contrast with general equilibrium theory, which has defined and extensively studied several fundamental market models to address a number of specialized and realistic situations. Our paper addresses both these issues by proposing Nash-bargaining-based matching market models. Since the Nash bargaining solution is captured by a convex program, efficiency follow; in addition, it possesses a number of desirable game-theoretic properties. Our approach yields a rich collection of models: for one-sided as well as two-sided markets, for Fisher as well as Arrow-Debreu settings, and for a wide range of utility functions, all the way from linear to Leontief. We also give very fast implementations for these models which solve large instances, with $n = 2000$, in one hour on a PC, even for a two-sided matching market. A number of new ideas were needed, beyond the standard methods, to obtain these implementations.