The stable matching problem has many practical applications in two-sided markets, like those that assign doctors to hospitals or students to schools. Usually it is assumed that all agents in each side explicitly express a preference ordering over those in the other side. This can be unfeasible and impractical when the set of agents is very big. However, usually this set has a combinatorial structure, since each agent is often described by some features. To tackle these scenarios, we define a framework for stable matching problems where agents are allowed to express their preferences over those of the other group in a compact way, via soft constraints over the features describing these agents. We focus on a special kind of soft constraints, namely fuzzy constraints. We provide a solving engine for this new kind of stable matching problems that does not increase the time complexity of the classical Gale-Shapley algorithm, while maintaining stability of the matching returned. We then eval...

Compact Preference Representation via Fuzzy Constraints in Stable Matching Problems: Theoretical and Experimental Studies

Pini M. S.;Rossi F.;Venable K. B.
2018

Abstract

The stable matching problem has many practical applications in two-sided markets, like those that assign doctors to hospitals or students to schools. Usually it is assumed that all agents in each side explicitly express a preference ordering over those in the other side. This can be unfeasible and impractical when the set of agents is very big. However, usually this set has a combinatorial structure, since each agent is often described by some features. To tackle these scenarios, we define a framework for stable matching problems where agents are allowed to express their preferences over those of the other group in a compact way, via soft constraints over the features describing these agents. We focus on a special kind of soft constraints, namely fuzzy constraints. We provide a solving engine for this new kind of stable matching problems that does not increase the time complexity of the classical Gale-Shapley algorithm, while maintaining stability of the matching returned. We then eval...
2018
Proceedings of the 17th International Conference of the Italian Association for Artificial Intelligence
17th Conference of the Italian Association for Artificial Intelligence, AI*IA 2018
9783030038397
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3289439
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact