REAL

Parameterized Complexity of Candidate Nomination for Elections based on Positional Scoring Rules

Schlotter, Ildikó and Cechlárová, Katarína and Trellová, Diana (2024) Parameterized Complexity of Candidate Nomination for Elections based on Positional Scoring Rules. AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS, 38. No.-28. ISSN 1387-2532 (print); 1573-7454 (online)

[img]
Preview
Text
s10458-024-09658-5.pdf
Available under License Creative Commons Attribution.

Download (2MB) | Preview

Abstract

Consider elections where the set of candidates is partitioned into parties, and each party must nominate exactly one candidate. The Possible President problem asks whether some candidate of a given party can become the unique winner of the election for some nominations from other parties. We perform a multivariate computational complexity analysis of Possible President for several classes of elections based on positional scoring rules. We consider the following parameters: the size of the largest party, the number of parties, the number of voters and the number of voter types. We provide a complete computational map of P ossible P resident in the sense that for each choice of the four possible parameters as (i) constant, (ii) parameter, or (iii) unbounded, we classify the computational complexity of the resulting problem as either polynomial-time solvable or -complete, and for parameterized versions as either fixed-parameter tractable or [1]-hard with respect to the parameters considered.

Item Type: Article
Uncontrolled Keywords: Computational social choice, Candidate nomination, Positional scoring rules, Parameterized complexity
Subjects: J Political Science / politológia > JA Political science (General) / politológia általában
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 04 Jul 2024 07:45
Last Modified: 04 Jul 2024 07:45
URI: https://real.mtak.hu/id/eprint/199303

Actions (login required)

Edit Item Edit Item