Compact Preference Representation via Fuzzy Constraints in Stable Matching Problems: Theoretical and Experimental Studies
| Autor: | Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | AI*IA 2018 – Advances in Artificial Intelligence ISBN: 9783030038397 AI*IA |
| DOI: | 10.1007/978-3-030-03840-3_16 |
| Popis: | 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 evaluate the approach experimentally. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|