A Map of Diverse Synthetic Stable Roommates Instances

N. Boehmer, K. Heeger, S. Szufa
AAMAS 2023
Abstract
Focusing on Stable Roommates (SR), we contribute to the toolbox for conducting experiments for stable matching problems. We introduce the polynomial-time computable mutual attraction distance 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.

Experiments:

Election type Culture Candidates Voters Instances Parameters
Ordinal Euclidean 1D {200} {200} 1 Uniform 1D {[0,1]}
Ordinal Euclidean 2D {200} {200} 1 Uniform 2D ($[0,1]^2$)
Ordinal Hand-Crafted {200} {200} 1 None
Ordinal Impartial Culture {200} {200} 1 None
Ordinal Mallows {200} {200} 1 $\phi \in \{0.2, 0.4, 0.6, 0.8 \}$