Characterization of Dynamics of Stable Matchings: Attractors Mapped from Stable Matchings

摘要

This note characterizes the dynamic structure of stable matchings of the stable marriage problem (SMP). The characterization focuses on the dynamic process of how the stable matching will be attained. To this end, the discrete problem of the SMP will be mapped to nonlinear dynamical models whose attractors include the counterparts of the stable matchings in the original SMP. A simple measure of decision-making difficulty is introduced. We use two types of diagram: a cross section diagram (and its 3D imaging) of a lattice to visualize the decision-making difficulty, and a radiation diagram to visualize the time evolution to a matching. Both diagrams are used to examine the dynamic structure of the neighborhood of an attractor and its basin as well as the region between basins in the dynamical model mapped from the SMP.