Complexity of clustering binary strings with missing data for voting design
Binary $k$-Center under a Hard Threshold with Applications to Delegated Voting
Computer Science and Game Theory
Summary
This paper explores the problem of grouping binary strings—sequences made of just zeros and ones—when some data may be missing. The goal is to find a fixed number of representative strings (centers) so that every original string is close enough to some center. The authors focus mainly on how this applies to voting systems where voters can delegate their choices to representatives. They analyze how hard it is to solve this problem depending on the number of centers and the strictness of agreement needed, providing a detailed map of the computing challenges involved.
What this means in practice
- •For election system designers: Determine how to form representative groups so most voters accept delegation in multi-issue approval voting setups.
- •For bioinformatics tool developers: Understand limits on clustering incomplete binary data common in genetic sequence analysis.
A theory result. No direct application yet.
Authors
Jakub Dargaj, Aris Filos-Ratsikas, Paul W. Goldberg
Abstract
We study the problem of covering binary strings of the same length, possibly with missing entries, by a fixed number of center strings, such that each input string is within a given relative distance of the closest center. The problem has applications in binary $k$-center clustering and bioinformatics, but our main motivation comes from computational social choice. In the setting of multi-issue approval voting, we consider an algorithmic question that precedes any election: how should representatives be designed so that as many voters as possible are willing to delegate? We study the problem in two dimensions, namely the number of centers and the agreement threshold, parameters that are application-specific, and provide a complete picture of its computational complexity when entries may be missing. For the special case without missing entries, we extend our hardness results to any number of centers and large values of threshold, leaving a narrow range of thresholds unresolved.