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

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

Publikation: Beitrag in Buch/KonferenzbandBeitrag in Konferenzband

Abstract

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.
OriginalspracheEnglisch
Titel des SammelwerksEconomics of Grids, Clouds, Systems, and Services. GECON 2013
Herausgeber*innen GECON 2013
ErscheinungsortSpain
Seiten149 - 160
PublikationsstatusVeröffentlicht - 2013

Zitat