Detecting Approximate Clones under Approval Voting

In approval elections, two candidates are called perfect clones if they are approved by exactly the same set of voters. We propose a general framework for studying approximations of this notion, and demonstrate its power using two natural approximation measures with various appealing axiomatic properties. For both of these measures, we consider two fundamental tasks: deciding whether a large approximate clone set exists in a given election, and computing a partition of the candidate set into approximate clone sets. We show that both tasks are, in general, computationally intractable. To have a better understanding of the boundary between tractable and intractable instances, we analyze the parameterized complexity of these problems with respect to several parameters, including the number of voters and candidates, the approximation threshold, the number and size of partition parts, and structural properties of the instances, such as the number of approvals per voter or per candidate. Finally, we explore how our approximation measures behave in real-world approval elections.

Authors

• Théo Delemazure ILLC, University of Amsterdam
• Piotr Faliszewski AGH University of Krakow
• Łukasz Janeczko AGH University of Krakow
• Dušan Knop Czech Technical University in Prague
• Kristýna Pekárková AGH University of Krakow
• Jan Pokorný Czech Technical University in Prague
• Šimon Schierreich AGH University of Krakow
• Ildikó Schlotter ELTE Centre for Economic and Regional Studies

Keywords

• Candidate Clones
• Approximate Clones
• Approval Elections
• Computational Complexity
• Fixed-Parameter Tractability