Maintaining Stability for a Matching Problem Under Dynamic Preference

Abstract

This study investigates two-sided matching and considers dynamic preference. In a stable matching problem, dynamic preference is a situation that often happens in real-world situations where the agent cannot express their preference with certainty. This study proposes a new concept to find stable matching using the blocking pair perspective. A stable matching is determined by identifying a matching by finding a matching with the minimum blocking pairs in multiple instances. In addition, the definition of stability is extended for the stable matching problem under dynamic preference to propose three new notions of stability. The proposed concept demonstrates more detailed information to assist in determining a stable matching with a dynamic preference. Moreover, the experiment results show that matching with the lowest expected value of the blocking pair gains the highest satisfaction score of agents in the market.

Keywords

• Stable matching
• dynamic preference
• blocking pair
• expected value