Very Hard Electoral Control Problems
Authors: Zack Fitzsimmons, Edith Hemaspaandra, Alexander Hoover, David E. Narváez1933-1940
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In our tests using Clingo 4.5.4 and Preflib (Mattei and Walsh 2013) (the standard dataset of real-world preference data), we noticed the above encoding suffers from the so-called grounding bottleneck. That is, even on instances of Kemeny CCAC with around 10 candidates, we are faced with prohibitively large programs after all variables are instantiated. ... For a preliminary test of our encoding, we attempted to solve the Kemeny-CCAC problem for all elections from Preflib with 4 or more candidates having complete strict order votes... There were 215 elections in total, and we were able to solve 114 of them using a timeout of 1 hour and a limit of 16GB of memory. Some noteworthy instances we could solve are summarized in Table 2. |
| Researcher Affiliation | Academia | Zack Fitzsimmons College of the Holy Cross Worcester, MA 01610 Edith Hemaspaandra Rochester Inst. of Technology Rochester, NY 14623 Alexander Hoover University of Chicago Chicago, IL 60637 David E. Narv aez Rochester Inst. of Technology Rochester, NY 14623 |
| Pseudocode | Yes | Figure 1: Rules of the guess part of Kemeny-CCAC. Figure 2: Rules of the check part of Kemeny-CCAC. Figure 3: Rules of the saturation part of Kemeny-CCAC. |
| Open Source Code | No | The paper discusses the encoding and its testing but does not provide any statement or link for publicly available source code for their implementation. |
| Open Datasets | Yes | In our tests using Clingo 4.5.4 and Preflib (Mattei and Walsh 2013) (the standard dataset of real-world preference data), we noticed the above encoding suffers from the so-called grounding bottleneck. |
| Dataset Splits | Yes | For a preliminary test of our encoding, we attempted to solve the Kemeny-CCAC problem for all elections from Preflib with 4 or more candidates having complete strict order votes, making the first candidate the preferred candidate and holding out the last fifth of the candidates as unregistered with an add limit equal to one third of the number of unregistered candidates. |
| Hardware Specification | Yes | The times reported were obtained on AMD Opteron(tm) 6180 SE ( ) and AMD Opteron(tm) 6282 SE ( ) processors. |
| Software Dependencies | Yes | In our tests using Clingo 4.5.4 and Preflib (Mattei and Walsh 2013) (the standard dataset of real-world preference data)... |
| Experiment Setup | Yes | For a preliminary test of our encoding, we attempted to solve the Kemeny-CCAC problem for all elections from Preflib with 4 or more candidates having complete strict order votes, making the first candidate the preferred candidate and holding out the last fifth of the candidates as unregistered with an add limit equal to one third of the number of unregistered candidates. ... There were 215 elections in total, and we were able to solve 114 of them using a timeout of 1 hour and a limit of 16GB of memory. |