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 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| 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. |