Detecting approximate clones under approval voting

Delemazure, Théo and Faliszewski, Piotr and Janeczko, Łukasz and Knop, Dušan and Pekárková, Kristýna and Pokorný, Jan and Schierreich, Šimon and Schlotter, Ildikó Anna (2026) Detecting approximate clones under approval voting. In: AAMAS '26. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), Richland (SC), pp. 3441-3443. ISBN 9798400723179

Preview

Text Approval_Clones_AAMAS_ea.pdf - Published Version Available under License Creative Commons Attribution. Download (1MB) | Preview

Abstract

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.

Actions (login required)

Edit Item