Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
A Map of Diverse Synthetic Stable Matching Instances
Authors: Niclas Boehmer, Klaus Heeger, Stanisław Szufa
JAIR 2024 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Focusing on Stable Roommates (SR), we contribute to the toolbox for conducting experiments for stable matching problems. ... Subsequently, we conduct several illustrative 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, we extend our approach to the bipartite Stable Marriage problem. ... Note that in this paper, we focus on computational experiments (also known as numerical experiments or simulations). This explicitly excludes other forms of experiments such as lab or live experiments. |
| Researcher Affiliation | Academia | Niclas Boehmer EMAIL Klaus Heeger EMAIL Technische Universit at Berlin, Berlin, Germany Stanis law Szufa EMAIL AGH University, Krak ow, Poland |
| Pseudocode | No | The paper describes algorithms and problem formulations (e.g., ILP for minimizing blocking pairs) but does not include any explicitly labeled or formatted pseudocode or algorithm blocks. |
| Open Source Code | Yes | The code for generating the map and conducting our experiments is available at https://github.com/szufix/mapel. The generated datasets of SR and SM instances are available at https://github.com/szufix/mapel_data. |
| Open Datasets | Yes | The generated datasets of SR and SM instances are available at https://github.com/szufix/mapel_data. |
| Dataset Splits | No | The paper describes generating a dataset of 460 synthetic SR instances and 460 SM instances from various statistical cultures. These instances are then analyzed or used as input for experiments. The concept of training/test/validation splits, as typically applied in machine learning for model evaluation, does not directly apply to the methodology described, which focuses on generating and mapping instances rather than training a model. |
| Hardware Specification | No | The paper mentions solving Integer Linear Programs (ILP) using Gurobi Optimization, LLC (2021) but does not specify any hardware details like CPU, GPU models, or memory. |
| Software Dependencies | No | The paper mentions using "Gurobi Optimization, LLC (2021)" for solving ILPs. However, this refers to the company and publication year of the reference manual, not a specific version number of the Gurobi solver used in the experiments. No other specific software versions are provided. |
| Experiment Setup | Yes | We first describe our dataset of 460 SR instances generated from the following statistical cultures (see Table 1 for an overview). To the best of our knowledge, only the Impartial Culture, Attributes, Mallows, and Euclidean models have been previously considered. ... To draw a map of our dataset, we compute for each pair of instances/matrices their mutual attraction distance. Subsequently, we embed the instances as points in the two-dimensional Euclidean space. Our goal is that the Euclidean distance between two points reflects the mutual attraction distance between the two respective instances. To obtain the embedding, we use a variant of the force-directed algorithm of Kamada and Kawai (1989). ... As computing the minimum number of blocking pairs in an SR instance is NP-hard (Abraham, Bir o, & Manlove, 2005), we solve this problem using an ILP. ... For this, for each instance, we sampled 100 perfect matchings uniformly at random from the set of all possible perfect matchings of agents and for each counted the number of blocking pairs. |