Nash-Bargaining-Based Models for Matching Markets, with Implementations and Experimental Results

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, not only for one-sided, but also two-sided, markets. In order to be used in "industrial grade" applications, we demonstrate very fast implementations for these models. These are able to 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. For matching market models with linear utilities, we use the Frank-Wolfe algorithm. For the more challenging models, with non-linear utility functions, we use the cutting-plane algorithm.