The Complexity of Subelection Isomorphism Problems
Authors: Piotr Faliszewski, Krzysztof Sornat, Stanisław Szufa
JAIR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In Section 5 we use this latter problem to evaluate similarity between elections generated from various statistical cultures and some real-life elections. Specifically, given two elections, E1 and E2, both with the same number of voters, using the Max. Common Voter-Subelection problem we can compute the largest fraction of votes that we can keep in these elections while ensuring their isomorphism. For each scenario and each two of the selected models, we have generated 1000 pairs of elections. For each pair of models, we recorded the average fraction of voters in the maximum common voter subelections (expressed as a percentage value), as well as the standard deviation of this value. |
| Researcher Affiliation | Academia | Piotr Faliszewski EMAIL Krzysztof Sornat EMAIL AGH University, Kraków, Poland, Stanisław Szufa EMAIL AGH University, Kraków, Poland CNRS, LAMSADE, Université Paris Dauphine-PSL, France |
| Pseudocode | Yes | Our ILP formulation is available in Appendix A. Appendix A. ILP for Maximum Common Voter-Subelection. We have two types of variables: 1. For each pair of voters v V and u U, we have a binary variable Nv,u. ... 2. For each pair of candidates c C and d D, we have a binary variable Mc,d. ... To ensure that variables Nv,u and Mc,d describe the respective matchings, we have the following basic constraints: P u U Nv,u 1, v V, P d D Mc,d = 1, c C, P v V Nv,u 1, u U, P c C Mc,d = 1, d D. |
| Open Source Code | Yes | The source code used for the experiments is available in a Git Hub repository3. 3. https://github.com/Project-PRAGMA/Subelections |
| Open Datasets | Yes | We also conducted analogous experiments regarding 11 real-life elections from Pref Lib (Mattei & Walsh, 2013). Specifically, we analyzed city council elections in Glasgow and Aspen, elections from Dublin North and Meath constituencies (Irish), elections held by non-profit organizations, trade unions, and professional organizations (ERS), data from Tour de France (TDF) (Boehmer & Schaar, 2023), Giro d Italia (GDI) (Boehmer & Schaar, 2023), speed skating (Boehmer et al., 2021), figure skating,4 as well as preferences over Sushi (Kamishima, 2003), T-Shirt designs, and costs of living and population in different cities (Caragiannis et al., 2019). |
| Dataset Splits | No | The paper does not describe traditional dataset splits (e.g., train/test/validation percentages or specific files) but rather details the generation of election instances from various models or source elections for experimental comparison. For example: "For each scenario and each two of the selected models, we have generated 1000 pairs of elections." |
| Hardware Specification | Yes | Whenever we discuss the running time of a particular algorithm, we report experiments performed on a single thread on Apple Mac Book Air with M1 processor and 8 GB RAM. |
| Software Dependencies | No | We express it as an integer linear program (ILP) and we were solving it using the CPLEX ILP solver. No version number for the CPLEX solver is provided. |
| Experiment Setup | Yes | We consider elections with 4, 6, 8, and 10 candidates and with 50 voters. For each scenario and each two of the selected models, we have generated 1000 pairs of elections. ... urn (with α {0.1, 0.5}), Norm-Mallows (with norm-ϕ {1/3, 2/3}), and identity. |