Preference-based Resource Allocation: Using Heuristics to Solve Two-Sided Matching Problems with Indifferences

Christian Haas, Steven O. Kimbrough, Simon Caton, Christof Weinhardt

Publication: Chapter in book/Conference proceedingContribution to conference proceedings


The allocation of resources between providers to consumers is a well-known problem and has received significant attention, typically using notions of monetary exchanges. In this paper, we study resource matching in settings without monetary transactions by using a two-sided matching approach, e.g., in social and collaborative environments where users define preferences for with whom they may be matched. Whereas two-sided matching for strict and complete preference rankings (i.e., without indifferences) has been extensively studied, it is known that the matching problem is NP-hard for more realistic preference structures. We study, via simulation, the applicability of a heuristic procedure in settings with indiffernces in preferences, and compare its performance to existing algorithms. We study performance metrics like fairness and welfare in addition to the classic stability objective. Our results show interesting trade-offs between performance metrics and promising performance of the heuristic. {\textcopyright} 2013 Springer International Publishing.
Original languageEnglish
Title of host publicationEconomics of Grids, Clouds, Systems, and Services. GECON 2013
Editors GECON 2013
Place of PublicationSpain
Pages149 - 160
Publication statusPublished - 2013

Cite this