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

This paper addresses the paucity of models of matching markets, both one-sided and two-sided, when utility functions of agents are cardinal. The classical Hylland-Zeckhauser scheme \cite{hylland}, which is the most prominent such model in economics, can be viewed as corresponding to the linear Fisher model, which is most elementary model in market equilibria. Although HZ is based on the attractive idea of using a pricing mechanism, from the viewpoint of use in applications, it has a serious drawback, namely lack of computational efficiency, due to which solving instances of size even 4 or 5 is difficult. We propose a variety of Nash-bargaining-based models, several of which draw from general equilibrium theory, which has defined a rich collection of market models that generalize the linear Fisher model in order to address more specialized and realistic situations. The Nash bargaining solution satisfies Pareto optimality and symmetry and the allocations it yields are remarkably fair. Furthermore, since the solution is captured via a convex program, it is polynomial time computable. In order to be used in "industrial grade" applications, we give implementations for these models that are extremely time efficient, solving large instances, with $n = 2000$, in one hour on a PC, even for a two-sided matching market. The idea underlying our work has its origins in Vazirani (2012), which viewed the linear case of the Arrow-Debreu market model as a Nash bargaining game and gave a combinatorial, polynomial time algorithm for finding allocations via this solution concept, rather than the usual approach of using a pricing mechanism.