A Map of Diverse Synthetic Stable Roommates Instances
This provides a tool for researchers in stable matching problems to better understand and compare synthetic instances, though it is incremental as it builds on existing statistical cultures and extends to other matching problems.
The authors tackled the problem of visualizing and comparing synthetic Stable Roommates (SR) instances by introducing a polynomial-time pseudometric to measure similarity and creating a map of 460 instances from ten statistical cultures, demonstrating its utility as a non-aggregate visualization tool and highlighting dataset diversity.
Focusing on Stable Roommates (SR) instances, we contribute to the toolbox for conducting experiments for stable matching problems. We introduce a polynomial-time computable pseudometric to measure the similarity of SR instances, analyze its properties, and use it to create a map of SR instances. This map visualizes 460 synthetic SR instances (each sampled from one of ten different statistical cultures) as follows: Each instance is a point in the plane, and two points are close on the map if the corresponding SR instances are similar to each other. Subsequently, we conduct several exemplary experiments and depict their results on the map, illustrating the map's usefulness as a non-aggregate visualization tool, the diversity of our generated dataset, and the need to use instances sampled from different statistical cultures. Lastly, to demonstrate that our framework can also be used for other matching problems under preference, we create and analyze a map of Stable Marriage instances.