Preference-based resource allocation: Using heuristics to solve two-sided matching problems with indifferences

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationEconomics of Grids, Clouds, Systems, and Services - 10th International Conference, GECON 2013, Proceedings
Pages149-160
Number of pages12
DOIs
StatePublished - 2013
Externally publishedYes
Event10th International Conference on the Economics of Grids, Clouds, Systems, and Services, GECON 2013 - Zaragoza, Spain
Duration: Sep 18 2013Sep 20 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8193 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on the Economics of Grids, Clouds, Systems, and Services, GECON 2013
Country/TerritorySpain
CityZaragoza
Period9/18/139/20/13

Keywords

  • Heuristics
  • Multiple Objectives
  • Preferences with Indifferences
  • Two-Sided Matching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Preference-based resource allocation: Using heuristics to solve two-sided matching problems with indifferences'. Together they form a unique fingerprint.

Cite this