An Algorithm for the Assignment Game Beyond Additive Valuations
For economists and computer scientists studying matching markets, this work extends algorithmic tractability to a more general setting, but the result is incremental as it combines existing techniques.
The paper presents an efficient algorithm for computing competitive equilibria in assignment games with both imperfectly transferable utility and gross substitutes valuations, and shows NP-hardness for two mild generalizations.
The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is assumed that payments lead to transferable utility and that buyers have unit-demand valuations for items. Two important and mostly independent lines of work have studied more general settings with imperfectly transferable utility and gross substitutes valuations. Multiple efficient algorithms have been proposed for computing a competitive equilibrium, the standard solution concept in assignment games, in these two settings. Our main result is an efficient algorithm for computing competitive equilibria in a setting with both imperfectly transferable utility and gross substitutes valuations. Our algorithm combines augmenting tree techniques from maximum matching and algorithms for matroid intersection. We also show that, in two mild generalizations of our model, computing a competitive equilibrium is NP-hard.