In traditional computational social choice, we often assume that as the number of voters ($n$) grows, the difficulty of solving an election problem—like finding a winner or detecting manipulation—grows exponentially. This "curse of dimensionality" suggests that large-scale democracy is computationally inscrutable.
However, recent research suggests that the total number of individuals is a misleading metric for complexity. Instead, the true bottleneck is diversity. By grouping participants into discrete "types" based on shared preferences or attributes, researchers have shown that many NP-hard problems become efficiently solvable (Fixed-Parameter Tractable) as long as the number of distinct types remains small.
The Shift from Individuals to Profiles
The core intuition behind this research direction is a change in representation. Instead of treating an electorate as a list of $n$ distinct preference rankings, we treat it as a frequency vector of voter types.
If there are only $m$ candidates, there are $m!$ possible ways to rank them. While $m!$ grows quickly, in many real-world scenarios, voters cluster into a handful of ideological blocks or "echo chambers." As Junlin Wu and Yevgeniy Vorobeychik demonstrate in Manipulating Elections by Changing Voter Perceptions, when a society is polarized into a small number of these clusters, the search space for manipulation strategies collapses.
When we view the input this way, the complexity of the algorithm scales with the number of types rather than the number of people. This allows us to use powerful mathematical tools like Presburger Arithmetic—a way of solving logical formulas over integers. Martin Koutecký and Nimrod Talmon use this in Multi-Party Campaigning to prove that finding optimal campaign strategies is efficient when the number of candidates and rounds is limited, regardless of how many millions of voters are involved.
Why Homogeneity Simplifies the Search
Why does grouping help? Consider the "Possible President" problem: can a party nominate a candidate such that they win under a specific voting rule? In Parameterized complexity of candidate nomination for elections based on positional scoring rules, Ildikó Schlotter and Katarína Cechlárová show that the number of distinct preference profiles is a far better predictor of tractability than the number of voters.
If every voter is unique, an algorithm must consider every possible interaction between individuals. But if 10,000 voters share the same "type," the algorithm only needs to decide what happens to that group once. This reduces the problem from a combinatorial explosion to a set of integer constraints. This same logic applies to the "Necessary President" problem, where Schlotter and Cechlárová found in Necessary President in Elections with Parties that even coNP-complete problems (which are usually thought to be harder than NP-complete ones) become manageable when the electorate consists of clustered ideological blocks.
Applications Beyond Voting
This "type-based" approach isn't limited to ballots. It extends to any resource allocation problem where participants can be categorized.
In Parameterized Algorithms for Kidney Exchange, Arnab Maiti and Palash Dey apply this to the "clearing problem" in medical exchange networks. By grouping patients and donors into discrete compatibility profiles (based on blood type and tissue markers), they show that the optimization problem becomes fixed-parameter tractable. Even if a national registry has thousands of patients, the number of biological "types" is relatively small, making the optimal matching of kidneys a solvable task in practice.
The Double-Edged Sword of Structure
While these findings are a boon for researchers trying to solve hard optimization problems, they also highlight a vulnerability in social systems.
As explored by Hodaya Barr and Sarit Kraus in Control for Coalitions in Parliamentary Elections, structured preferences (like "single-peaked" preferences where everyone agrees on a left-to-right political spectrum) make it easier to calculate how to control or manipulate a coalition.
The intuition is sobering: the more predictable and clustered a population becomes, the more "computationally efficient" it is for an external actor—whether a campaign manager or a malicious brier—to find the exact lever needed to change the outcome. Complexity, it turns out, is a form of protection that diversity provides to democracy. When that diversity vanishes into a few discrete types, the system becomes much easier to "solve"—and thus, easier to game.