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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Necessarily Optimal One-Sided Matchings
Authors: Hadi Hosseini, Vijay Menon, Nisarg Shah, Sujoy Sikdar5481-5488
AAAI 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design efficient algorithms to check if a given matching is NPO or NRM, and to check whether such a matching exists given top-k partial preferences. We also study online algorithms for eliciting partial preferences adaptively, and prove bounds on their competitive ratio. |
| Researcher Affiliation | Academia | 1 College of Information Sciences and Technology, Penn State University 2 David R. Cheriton School of Computer Science, University of Waterloo 3 Department of Computer Science, University of Toronto 4 Department of Computer Science, Binghamton University |
| Pseudocode | Yes | Algorithm 1: A 2( n+1)-competitive elicitation algorithm; Algorithm 2: Algorithm to compute sigopt P (S, T, F) and arg sigopt P (S, T, F); Algorithm 3: Algorithm to check if a given matching is NRM given a top-k preference profile; Algorithm 4: Algorithm to check if an NRM matching exists given a top-k preference profile. |
| Open Source Code | No | The paper does not provide a direct link to source code or explicitly state that the code for the methodology is being released. |
| Open Datasets | No | This is a theoretical paper focusing on algorithm design and proofs; it does not involve training models on datasets. |
| Dataset Splits | No | This is a theoretical paper, and thus does not involve validation datasets or splits. |
| Hardware Specification | No | This is a theoretical paper, and therefore does not specify hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not mention specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This is a theoretical paper and does not describe an experimental setup with hyperparameters or training settings. |