Preferences Single-Peaked on a Circle
Authors: Dominik Peters, Martin Lackner
JAIR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give a fast recognition algorithm of this domain, provide a characterisation by finitely many forbidden subprofiles, and show that many popular single- and multi-winner voting rules are polynomial-time computable on this domain. In particular, we prove that Proportional Approval Voting can be computed in polynomial time for profiles that are single-peaked on a circle. In contrast, Kemeny’s rule remains hard to evaluate, and several impossibility results from social choice theory can be proved using only profiles in this domain. |
| Researcher Affiliation | Academia | Dominik Peters EMAIL Carnegie Mellon University Computer Science Department 5000 Forbes Avenue, Pittsburgh, PA 15213, USA Martin Lackner EMAIL TU Wien Databases and Artificial Intelligence Group Favoritenstraße 9-11, 1040 Vienna, Austria |
| Pseudocode | Yes | Algorithm 1 Recognising SP Input: a profile P = (v1, v2, . . . , vn) of weak orders, where vg is a linear order Output: Is P single-peaked? 1: Label alternatives such that cm g cm 1 g g c1 2: Set AL and AR c1 3: for i = 2, . . . , m do 4: if for no voter vk = vg we have either (R1) or (R2) then 5: place ci on the right: AR ci, AR 6: else if for no voter vs = vg we have either (L1) or (L2) then 7: place ci on the left: AL AL, ci 9: (for some vk we have (R1) or (R2) and for some vs we have (L1) or (L2)) 10: return P is not single-peaked 12: end for 13: return P is single-peaked on the axis = AL, AR |
| Open Source Code | No | No explicit statement about the release of source code or a repository link for the methodology described in this paper was found. |
| Open Datasets | No | No mention of specific open datasets with concrete access information was found. The paper deals with theoretical properties of preference profiles using abstract alternatives and voters. |
| Dataset Splits | No | The paper does not report on experiments using datasets, thus no dataset split information is provided. |
| Hardware Specification | No | No hardware specifications were mentioned, as the paper presents theoretical results and algorithms rather than empirical experiments. |
| Software Dependencies | No | No specific software dependencies with version numbers for experimental replication were mentioned. The paper describes algorithms and integer linear programming formulations at a theoretical level. |
| Experiment Setup | No | No specific experimental setup details such as hyperparameters or training configurations are provided, as this is a theoretical paper focusing on algorithms and proofs. |