Necessarily Optimal One-Sided Matchings
Authors: Hadi Hosseini, Vijay Menon, Nisarg Shah, Sujoy Sikdar5481-5488
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | 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. |