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; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Recognizing Top-Monotonic Preference Profiles in Polynomial Time
Authors: Krzysztof Magiera, Piotr Faliszewski
JAIR 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide the first polynomial-time algorithm for recognizing if a profile of (possibly weak) preference orders is top-monotonic. Our algorithm proceeds by reducing the recognition problem to the SAT2CNF problem. |
| Researcher Affiliation | Academia | Krzysztof Magiera EMAIL Piotr Faliszewski EMAIL AGH University, Krakow, Poland |
| Pseudocode | No | The algorithm consists of the following five steps: 1. We first compute the set T. ... 2. We elliminate indistinguishable alternatives: ... 3. We generate our SAT-2CNF formula. ... 4. We solve the formed SAT-2CNF formula ... 5. In the final step we prepare the top-monotonic order.... The paper describes the steps of the algorithm in prose, rather than providing structured pseudocode or an algorithm block. |
| Open Source Code | No | The paper does not provide any explicit statements about open-source code availability for the methodology described, nor does it include links to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and complexity using abstract 'preference profiles' and 'alternatives'. It does not use or provide access to any specific datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets; therefore, no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical, presenting an algorithm and its complexity. It does not describe any experiments that would require specific hardware, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper mentions reducing the problem to 'SAT-2CNF problem' and solving it with a 'standard linear-time algorithm' but does not specify any software names, libraries, or version numbers used for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical, focusing on algorithm design and complexity analysis. It does not include any experimental evaluation, and thus no experimental setup details such as hyperparameters or training configurations are provided. |