Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic Preferences
We studied the stable marriage problem with dynamic preferences. The dynamic preference model allows the agent to change its preferences at any time, which may cause instability in a matching. However, preference changing in SMP instances does not necessarily break all pairs of an existing match. So...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-02-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/24/2/263 |
| _version_ | 1797480564367818752 |
|---|---|
| author | Akhmad Alimudin Yoshiteru Ishida |
| author_facet | Akhmad Alimudin Yoshiteru Ishida |
| author_sort | Akhmad Alimudin |
| collection | DOAJ |
| description | We studied the stable marriage problem with dynamic preferences. The dynamic preference model allows the agent to change its preferences at any time, which may cause instability in a matching. However, preference changing in SMP instances does not necessarily break all pairs of an existing match. Sometimes, only a few couples want to change their partners, while others choose to stay with their current partners; this motivates us to find stable matching on a new instance by updating an existing match rather than restarting the matching process from scratch. By using the update mechanism, we try to minimize the revision cost when rematching occurs. The challenge when updating a matching is that a cyclic process may exist, and stable matching is never achieved. Our proposed mechanism can update a match and avoid the cyclic process. |
| first_indexed | 2024-03-09T22:01:53Z |
| format | Article |
| id | doaj.art-bced62183887448d86b1cbf1a019cb8d |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-09T22:01:53Z |
| publishDate | 2022-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-bced62183887448d86b1cbf1a019cb8d2023-11-23T19:48:35ZengMDPI AGEntropy1099-43002022-02-0124226310.3390/e24020263Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic PreferencesAkhmad Alimudin0Yoshiteru Ishida1Department of Computer Science and Engineering, Toyohashi University of Technology, Toyohashi 441-8580, JapanDepartment of Computer Science and Engineering, Toyohashi University of Technology, Toyohashi 441-8580, JapanWe studied the stable marriage problem with dynamic preferences. The dynamic preference model allows the agent to change its preferences at any time, which may cause instability in a matching. However, preference changing in SMP instances does not necessarily break all pairs of an existing match. Sometimes, only a few couples want to change their partners, while others choose to stay with their current partners; this motivates us to find stable matching on a new instance by updating an existing match rather than restarting the matching process from scratch. By using the update mechanism, we try to minimize the revision cost when rematching occurs. The challenge when updating a matching is that a cyclic process may exist, and stable matching is never achieved. Our proposed mechanism can update a match and avoid the cyclic process.https://www.mdpi.com/1099-4300/24/2/263stable marriage problemupdate matchingdynamic preferences |
| spellingShingle | Akhmad Alimudin Yoshiteru Ishida Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic Preferences Entropy stable marriage problem update matching dynamic preferences |
| title | Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic Preferences |
| title_full | Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic Preferences |
| title_fullStr | Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic Preferences |
| title_full_unstemmed | Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic Preferences |
| title_short | Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic Preferences |
| title_sort | matching updating mechanism a solution for the stable marriage problem with dynamic preferences |
| topic | stable marriage problem update matching dynamic preferences |
| url | https://www.mdpi.com/1099-4300/24/2/263 |
| work_keys_str_mv | AT akhmadalimudin matchingupdatingmechanismasolutionforthestablemarriageproblemwithdynamicpreferences AT yoshiteruishida matchingupdatingmechanismasolutionforthestablemarriageproblemwithdynamicpreferences |