Social choice theory traditionally focuses on selecting a single winner from a pool of candidates. However, modern applications—ranging from choosing a representative political committee to curating web search results and movie recommendations—require selecting a set of items or representatives. As Craig Boutilier highlights in Preference Elicitation and Preference Learning in Social Choice, scaling collective decision-making to modern AI environments requires a shift toward algorithms that can handle massive preference profiles efficiently.
When selecting a committee of size $k$, the goal is often to ensure proportional representation, meaning that cohesive groups of voters receive a share of the committee proportional to their size. Axioms like Proportional Justified Representation (PJR) and Extended Justified Representation (EJR) formalize this requirement.
Unfortunately, optimizing these representation metrics globally is an NP-hard problem. Even worse, verifying whether a given committee satisfies PJR or EJR is coNP-complete, as demonstrated by Haris Aziz et al. in On the Complexity of Extended and Proportional Justified Representation. This creates a fundamental computational bottleneck. To bypass this intractability, researchers have turned to greedy sequential selection and local search heuristics, discovering that these polynomial-time approximations do not merely trade off accuracy for speed—they often preserve or even enhance the axiomatic fairness of the system.
Greedy Sequential Selection as a Representation Engine
Instead of evaluating all possible committees globally, a greedy sequential algorithm constructs the committee one member at a time. In each round, the algorithm selects the candidate who maximizes the marginal utility of the voters.
To prevent a majority group from dominating every single slot on the committee, these algorithms employ weight-reduction mechanisms. Once a candidate approved by a group of voters is selected, the voting weight or influence of those specific voters is scaled down for subsequent rounds. This ensures that minority groups gain substantial voting power in later iterations, naturally enforcing diversity.
This simple iterative approach is remarkably powerful. Edith Elkind et al. demonstrate in Proportional Justified Representation that greedy approximation methods can satisfy complex representation axioms in polynomial time. For instance, Markus Brill et al. show in Phragmén's Voting Methods and Justified Representation that a sequential load-balancing rule (originally proposed by Lars Edvard Phragmén) guarantees PJR without ever needing to solve a global optimization problem. Similarly, Luis Sánchez Fernández 0001 et al. introduce a sequential selection strategy via linear programming in The Maximin Support Method: An Extension of the D'Hondt Method to Approval-Based Multiwinner Elections, providing a 2-approximation for maximizing the support of the least-represented candidate.
In practice, the loss in representation quality compared to exact optimization is negligible. Empirical evaluations by Martin Lackner et al. in A Quantitative Analysis of Multi-Winner Rules and Piotr Faliszewski et al. in An Experimental Comparison of Multiwinner Voting Rules on Approval Elections reveal that committees produced by greedy heuristics are often nearly indistinguishable from their mathematically optimal, NP-hard counterparts. This viability extends directly to real-world applications; for example, Grzegorz Gawron demonstrates in Using multiwinner voting to search for movies that greedy approximations perform on par with intensive optimization techniques like simulated annealing when used to control diversity dials in movie recommendation engines.
Escaping Local Optima via Local Search
While sequential greedy selection builds a committee from the ground up, another paradigm starts with an arbitrary committee and refines it iteratively: local search.
Local search algorithms operate by evaluating local "swaps"—replacing a single committee member with a non-member if the swap improves a global fairness or stability objective. This approach is highly effective for achieving core stability, a gold-standard fairness guarantee where no coalition of voters can deviate and choose a smaller committee that they all strictly prefer.
In the context of approval-based apportionment, Markus Brill et al. in Approval-Based Apportionment and Dominik Peters et al. in Approval-based apportionment prove that while finding an optimal committee under general proportional rules is hard, a local-search algorithm can identify a core-stable committee in polynomial time.
The intuition behind why this works is that local search bypasses the need to verify the entire combinatorial space. By focusing purely on whether a single-item swap can increase a group's utility, the algorithm navigates the solution space efficiently. This principle applies broadly across fair division problems:
- Indivisible Goods: Vincent Conitzer et al. show in Group Fairness for the Allocation of Indivisible Goods that local search can efficiently find allocations that guarantee group fairness "up to one good."
- Sequential Decisions: Shashwat Goel et al. apply local search heuristics to time-series voting in Proportional Aggregation of Preferences for Sequential Decision Making, showing that iteratively swapping outcomes satisfies rigorous fairness axioms across a sequence of collective decisions.
The Surprising Axiomatic Advantages of Heuristics
The traditional view of approximation algorithms is that they are a necessary compromise—trading mathematical perfection for computational tractability. However, a profound insight from computational social choice is that greedy heuristics can actually outperform exact algorithms axiomatically.
In Properties of multiwinner voting rules, Piotr Skowron 0001 et al. demonstrate that greedy approximations can introduce specific axiomatic properties that are completely absent in the original optimal formulations. For example, a greedy approach to committee selection can satisfy fairness criteria like the solid coalitions property, which the exact, globally optimized mathematical solution fails to meet.
Why does this happen? Global optimization can make highly non-intuitive, brittle trade-offs to maximize a single global score, occasionally sacrificing the representation of a cohesive local group to achieve a marginal gain elsewhere. By contrast, greedy algorithms build committees step-by-step, naturally locking in representation for large, cohesive voter blocks early in the process.
Even extreme simplifications can yield strong guarantees. For instance, Ulle Endriss et al. prove in Binary Aggregation by Selection of the Most Representative Voters that simply selecting the single most representative individual voter from a group provides a guaranteed 2-approximation of the ideal consensus outcome while remaining perfectly easy to compute and explain.
As curated by Haris Aziz et al. in the Special Issue on Fair Public Decision Making: Allocating Budgets, Seats, and Probability, these insights have transformed greedy and local search algorithms from mere computational shortcuts into deliberate design choices for engineering fair, scalable, and robust collective decision-making systems.
Key Foundational Work
Preference Elicitation and Preference Learning in Social Choice (2011) — contributed 1 concept elements to this direction.
Fully Proportional Representation as Resource Allocation: Approximability Results (2013) — contributed 1 concept elements to this direction.