Parameterized Complexity in Computational Social Choice

133 concepts92 papers2 proposals

In social choice theory, many elegant voting rules and collective decision-making mechanisms suffer from a shared flaw: they are computationally intractable. Determining the winner under sophisticated multiwinner rules, detecting optimal campaign strategies, or preventing election bribery are frequently NP-hard or #P-complete.

However, worst-case complexity is a blunt instrument. An election with millions of voters but only three candidates behaves very differently from a committee of five experts choosing among hundreds of research proposals. By shifting our perspective from classical complexity to parameterized complexity, we can isolate the source of combinatorial explosions. If the hardness of a problem is confined to a specific structural parameter that remains small in practice, the problem becomes fixed-parameter tractable (FPT)—effectively solvable in polynomial time for real-world instances.

The Candidate-Count Parameterization and Lenstra's Trick

Why does fixing the number of candidates make hard problems easy? Consider the problem of election bribery or strategic manipulation. In a foundational paper on election complexity, How Hard Is Bribery in Elections?, the authors demonstrated that when the number of candidates is small and fixed, generally intractable bribery problems become solvable in polynomial time.

The core mechanism driving this tractability is an elegant application of geometry: Integer Linear Programming (ILP) parameterized by the number of variables. According to Lenstra's theorem, an ILP can be solved in polynomial time if the number of variables is bounded by a constant.

In an election with $m$ candidates, the number of distinct ways a voter can rank the candidates is $m!$. If $m$ is a small constant, $m!$ is also a constant. We can group an arbitrarily large electorate into $m!$ distinct "preference profiles" or voter types. Instead of tracking each individual voter, an algorithm can simply solve for the number of voters of each type that need to be altered. This reduces the problem to an ILP where the number of variables depends solely on $m$, completely decoupling the exponential complexity from the number of voters $n$.

As shown by Piotr Faliszewski et al. in Voting-Based Group Formation, this exact strategy allows hard group-partitioning and election subversion problems to be solved efficiently when the candidate pool is small, regardless of how large the electorate grows.

Flipping the Script: Few Voters, Many Candidates

What happens when the situation is reversed? In scenarios like hiring committees, grant panels, or meta-search engines, a small group of agents must select from a massive pool of alternatives. Here, parameterizing by the candidate count fails.

Instead, researchers look to parameterize by the number of voters or decision-makers. In Elections with Few Voters: Candidate Control Can Be Easy, Jiehua Chen et al. explored this exact paradigm, filling a critical gap in computational social choice by showing that candidate control problems often become tractable when the voter pool is small.

Similarly, Piotr Faliszewski et al. in Parameterized Algorithms for Finding a Collective Set of Items demonstrated that collective selection problems under Ordered Weighted Average (OWA) operators transition to FPT when the number of agents is small relative to the items. The intuition here is that a small number of voters can only generate a limited number of distinct interactions or constraints, bounding the search space of optimal outcomes.

Structural Parameters: Beyond Simple Counts

Fixed-parameter tractability extends far beyond simply counting voters or candidates. Often, the true bottleneck is the structural complexity of the preferences or the tournament itself.

Tournament Seeding and Feedback Arc Sets

In knockout tournaments, the Tournament Fixing Problem (TFP) asks whether a bracket can be rigged to ensure a specific player wins. In Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable, M. S. Ramanujan et al. parameterized the problem by the size of the minimum feedback arc set—the number of "upset" matches that contradict a clean, global ranking. When a tournament is "nearly acyclic" (meaning upsets are rare), the problem becomes FPT. The algorithm only needs to branch on the few unpredictable, rule-defying matches rather than exploring the astronomical space of all possible tournament outcomes.

Tree-Structured Preferences

When voter preferences are completely unstructured, finding optimal committees is notoriously difficult. However, if preferences are "single-peaked" along a hierarchical tree structure, the problem simplifies. Dominik Peters et al. in Preferences Single-Peaked on Nice Trees showed that multi-winner selection problems achieve FPT when parameterized by the number of internal nodes in the underlying preference tree. A simpler, more star-like tree drastically limits the ways voters can disagree, allowing dynamic programming to sweep through the hierarchy efficiently.

Bounded Uncertainty

Parameterization can also tame stochasticity. In resource allocation with uncertain preferences, calculating the exact probability that an allocation is Pareto optimal is generally #P-complete. However, Haris Aziz 0001 et al. in Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity showed that if only a small, fixed number of agents have uncertain preferences while the rest are stable, the problem becomes fixed-parameter tractable. The computational difficulty scales with the source of the noise rather than the size of the population. For instance, Qishen Han demonstrates in Determining Winners in Elections with Absent Votes that the problem of identifying possible winners with missing ballots transitions to polynomial time when the number of candidates or missing votes is small.

Why It Works: The Core Intuition

The unifying insight across all these facets of parameterized social choice is combinatorial isolation. NP-hardness means that somewhere in the problem, an exponential explosion occurs. Parameterized complexity succeeds by finding a mathematical boundary—a parameter $k$—and trapping the exponential explosion entirely inside $k$.

An FPT algorithm guarantees a running time of:

$$\mathcal{O}(f(k) \cdot n^c)$$

where $f(k)$ is an arbitrary function depending only on $k$, $n$ is the total input size, and $c$ is a constant independent of $k$. When $k$ is small, $f(k)$ acts as a large but constant overhead, leaving the rest of the computation to scale smoothly as a polynomial function of the input size. This paradigm transforms theoretical impossibility into practical, structured design.

Key Foundational Work

Exact Complexity of the Winner Problem for Young Elections (2001) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fixed_parameter_tractability_in_social_c_b7c366d7,
  title = {fixed-parameter tractability in social choice},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fixed-parameter-tractability-in-social-choice/rdr_b7c366d711f44b129655c2bda4fd0441},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_fixed_parameter_tractability_in_social_c_b7c366d7_v1,
  title = {fixed-parameter tractability in social choice},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fixed-parameter-tractability-in-social-choice/rdr_b7c366d711f44b129655c2bda4fd0441/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake