2024/06/19 by Eric Balkanski, Balkanski, Eric, Christopher En +3
Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2406.13620
openalex publication_date 2024/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.