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 Shift Toward Open and Reproducible AI Research," Under Review, 2026. doi: 10.48550/arXiv.2606.16974..
Computational Complexity of Verifying the Group No-show Paradox
Authors: Farhad Mohsin, Qishen Han, Sikai Ruan, Pin-Yu Chen, Francesca Rossi, Lirong Xia
IJCAI 2024 | Venue PDF | LLM Run Details | Input Tokens: 18,344 Total number of tokens sent to the LLM as input for this paper's analysis. | Output Tokens: 6,114 Total number of tokens produced by the LLM (including reasoning/thinking tokens) for this paper's analysis.
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results on synthetic data illustrate that the former is efficient when the number of unique rankings in a profile is not too high, and the latter is efficient for a small number of agents. With the help of these algorithms, we observe that group no-show paradoxes rarely occur in real-world data. |
| Researcher Affiliation | Collaboration | 1College of the Holy Cross, Worcester, MA 2Rensselaer Polytechnic Institute, Troy, NY 3IBM Research, Yorktown Heights, NY |
| Pseudocode | No | The paper describes algorithms (search-based and ILP-based) but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | Yes | The codes for our implementation of the verification algorithms is provided in the following repository: https://github.com/farhadmohsin/Axiom Verification. |
| Open Datasets | Yes | We perform experiments on both synthetic data and Pref Lib election data [Mattei and Walsh, 2013] (Section 5). |
| Dataset Splits | No | The paper describes the datasets used (synthetic and Pref Lib) but does not provide specific training/validation/test split information or refer to predefined splits for reproducibility. |
| Hardware Specification | Yes | All experiments were implemented in Python 3 and were run on a Windows laptop with 3.2 GHz AMD Ryzen 7 5800 CPU and 16 GB memory and the Gurobi solver was used for solving ILPs. |
| Software Dependencies | No | The paper mentions 'Python 3' and 'Gurobi solver' but does not specify the version number for the Gurobi solver, which is a key software component. |
| Experiment Setup | Yes | To create the ranking data, for each sample profile, all agent rankings are i.i.d. samples from the same distribution. We run experiments on a number of popular models for ranking, such as Impartial Culture (IC), single-peaked preferences [Conitzer, 2009], Mallows [Mallows, 1957] and more. For each model, for different values of n between 10 and 1000 and m [3, 10], we sample 1,000 preference profiles and calculate the occurrences of GNSP and the run-times. |