8 min read
On this page

Computational Social Choice

Voting Rules

Setting

A set of voters N = {1, ..., n} with preferences over a set of alternatives (candidates) A = {a_1, ..., a_m}. Each voter submits a ranking (linear order) over A. A voting rule f maps a preference profile (collection of all voters' rankings) to a winning alternative or a set of tied winners.

Positional Scoring Rules

Assign points based on position in each voter's ranking. Score vector s = (s_1, s_2, ..., s_m) with s_1 >= s_2 >= ... >= s_m and s_1 > s_m.

Plurality: s = (1, 0, ..., 0). Each voter votes for their top choice; the candidate with the most first-place votes wins. Simple but suffers from vote splitting and strategic voting. Widely used in practice (FPTP in elections).

Borda count: s = (m-1, m-2, ..., 1, 0). Candidate ranked k-th by a voter receives m-k points. Summed across all voters. Tends to elect consensus candidates (broadly acceptable rather than polarizing). Satisfies participation, monotonicity, and reversal symmetry.

Antiplurality (veto): s = (1, 1, ..., 1, 0). Each voter vetoes their least-preferred candidate. Winner is the candidate with the fewest vetoes.

Condorcet-Consistent Rules

A Condorcet winner beats every other candidate in pairwise majority comparison. Condorcet-consistent rules always select the Condorcet winner when one exists.

Copeland: Score each candidate by (number of pairwise wins) - (number of pairwise losses). Condorcet-consistent. Does not provide fine-grained ranking when no Condorcet winner exists.

Schulze method: Constructs a strongest-path tournament. For each pair (a, b), find the path from a to b where the minimum pairwise margin along the path is maximized. Candidate a is preferred to b if the strongest path from a to b has greater strength than from b to a. This relation is always a total order (no cycles). Condorcet-consistent, clone-independent, monotone. Used by Debian, Wikimedia, and many organizations.

Ranked Pairs (Tideman): Lock in pairwise margins from largest to smallest, skipping any that would create a cycle. The resulting DAG determines the winner. Condorcet-consistent, independent of clones.

Single Transferable Vote (STV) / Instant-Runoff Voting (IRV)

Iterative elimination:

  1. Count first-place votes for each candidate
  2. Eliminate the candidate with the fewest first-place votes
  3. Transfer eliminated candidate's votes to voters' next preferences
  4. Repeat until one candidate remains (or has majority)

Properties: Not Condorcet-consistent, not monotone (a candidate can lose by gaining support), satisfies majority criterion. Used in Australian federal elections, various US jurisdictions.

Computational properties: Winner determination is polynomial. However, manipulation is NP-hard (Bartholdi-Tovey-Trick), providing a computational barrier to strategic voting.

Approval Voting

Each voter approves a subset of candidates (binary: approved or not). The candidate with the most approvals wins. Simple, reduces strategic burden. Satisfies monotonicity. Not Condorcet-consistent in general.

Other Rules

  • Maximin (Simpson-Kramer): Winner is the candidate whose worst pairwise result is best: argmax_a min_b margin(a, b). Condorcet-consistent.
  • Bucklin: Iteratively expand the set of considered ranks until some candidate has majority support.
  • Kemeny: Find the ranking that minimizes total Kendall tau distance to all voters' rankings. NP-hard to compute but axiomatically well-motivated.

Arrow's Impossibility Theorem

Statement

For |A| >= 3, no social welfare function (aggregating individual rankings into a social ranking) satisfies all of:

  1. Unrestricted domain: Works for all preference profiles
  2. Pareto efficiency (unanimity): If all voters prefer a to b, then a is socially preferred to b
  3. Independence of irrelevant alternatives (IIA): The social ranking of a vs. b depends only on individual rankings of a vs. b
  4. Non-dictatorship: No single voter determines the social ranking

Proof Sketch

Using the field expansion lemma and group contraction lemma: a group decisive over one pair is decisive over all pairs; a decisive group can be contracted to a single voter. Therefore some voter is a dictator.

Escape Routes

Arrow's theorem motivates relaxations:

  • Restrict domain: Single-peaked preferences allow non-dictatorial, IIA-satisfying rules (median voter)
  • Weaken IIA: Borda count satisfies all other axioms
  • Allow cardinal utilities: Utilitarianism satisfies natural axioms for cardinal preferences
  • Social choice functions (not welfare functions): Gibbard-Satterthwaite addresses this setting

Manipulation (Strategic Voting)

Gibbard-Satterthwaite Revisited

For |A| >= 3 and surjective SCFs on the universal domain, strategyproofness implies dictatorship. Therefore, all reasonable voting rules are manipulable.

Computational Complexity of Manipulation

Bartholdi-Tovey-Trick (1989): Can we hope that manipulation is computationally hard, even if theoretically possible?

| Voting Rule | Constructive Manipulation | Destructive Manipulation | |---|---|---| | Plurality | P | P | | Borda | NP-hard (Betzler et al.) | P | | STV/IRV | NP-hard | NP-hard | | Copeland | NP-hard | NP-hard | | Schulze | P (Parkes-Xia) | P | | Maximin | NP-hard (weighted) | P | | Kemeny | NP-hard | NP-hard |

Constructive manipulation: Can a coalition of manipulators report false preferences to make their preferred candidate win?

Destructive manipulation: Can they prevent a specific candidate from winning?

Critiques of Computational Barriers

  • Worst-case hardness: NP-hardness means some instances are hard, but many practical instances may be easy. Average-case or smoothed analysis may show manipulation is often tractable.
  • Junta manipulation: A single manipulator can often find a successful manipulation in polynomial time, even when coalitional manipulation is NP-hard.
  • Frequency of manipulability: As the number of alternatives grows, the fraction of profiles where manipulation is possible may decrease (Friedgut-Kalai-Nisan) or increase, depending on the rule.

Bribery and Control

Bribery

An external agent can pay voters to change their votes. Each voter has a bribery cost. Goal: make a preferred candidate win with minimum total cost.

  • $-bribery (unit costs): NP-hard for Borda, Copeland, maximin; P for plurality
  • Weighted bribery: Generally harder
  • Shift bribery: Can only shift a preferred candidate up in voters' rankings

Control

An election chair controls the structure of the election:

  • Adding/deleting candidates: Introduce or remove alternatives
  • Adding/deleting voters: Include or exclude voters
  • Partition of candidates/voters: Run preliminary elections

Resistance: A voting rule is resistant to a type of control if the corresponding decision problem is NP-hard. Immunity: If the control action can never change the winner.

| Control Type | Plurality | Condorcet | Copeland | STV | |---|---|---|---|---| | Adding candidates | Resistant | Immune | Resistant | Resistant | | Deleting candidates | Resistant | Immune | Resistant | Resistant | | Adding voters | Resistant | Resistant | Resistant | Resistant | | Deleting voters | Resistant | Resistant | Resistant | Resistant |

STV is resistant to all standard control types (Bartholdi-Tovey-Trick), making it robust against structural manipulation.

Judgment Aggregation

Setting

Agents express judgments (true/false) on a set of logically interconnected propositions. Goal: aggregate into a consistent collective judgment.

Doctrinal paradox: Three judges vote on premises p, q, and conclusion p AND q. Individual judgments may be consistent while majority aggregation is inconsistent (majority says p=true, q=true, but p AND q = false).

Impossibility results: List-Pettit theorem shows that no aggregation rule satisfies universal domain, collective rationality, systematicity (propositionwise independence), and anonymity for sufficiently connected agendas. This generalizes Arrow's theorem to the judgment aggregation setting.

Approaches

  • Premise-based: Aggregate on premises; derive conclusions logically
  • Conclusion-based: Aggregate directly on conclusions
  • Distance-based: Find the consistent judgment set minimizing distance to the profile (Kemeny-like; NP-hard in general)

Liquid Democracy

Concept

Voters can either vote directly or delegate their vote to a trusted proxy, who may further delegate. Creates a delegation graph; votes flow through the graph to the final voter who casts them.

Properties and Challenges

  • Transitivity: Delegations chain; final voters cast accumulated weight
  • Cycles: Delegation cycles must be handled (break cycles, void votes)
  • Super-voters: Delegation concentration gives some voters enormous weight, potentially undermining the rationale
  • Incentives: Delegating to better-informed voters can improve outcomes (Condorcet jury theorem argument), but may also amplify biases
  • Platforms: LiquidFeedback, Google Votes (internal), various blockchain governance systems

Theoretical Analysis

Kahng-Mackenzie-Procaccia (2018) showed that liquid democracy can be worse than direct democracy if voters delegate based on insufficient information about delegates' competence. The benefit depends critically on the quality of the delegation graph.

Participatory Budgeting

Setting

Citizens vote on how to allocate a public budget across projects. Each project has a cost; total budget is B. Citizens express preferences (approval, ranking, or cardinal scores) over projects.

Aggregation Rules

  • Greedy by approval score: Sort projects by approval votes; fund in order until budget exhausted. Simple but can be inefficient (ignores cost-effectiveness).
  • Knapsack optimization: Maximize total utility subject to budget. NP-hard in general; FPTAS exists.
  • Method of equal shares (Proportional approval voting for PB): Gives each voter an equal share of the budget; a project is funded if its supporters can collectively afford it from their shares. Satisfies proportionality (extended justified representation).

Proportionality

A key fairness criterion: a cohesive group of k/n of the voters who all support a common set of projects with total cost at most k/n * B should see some of those projects funded.

Extended justified representation (EJR): Formal proportionality axiom adapted from multi-winner voting. The method of equal shares satisfies EJR for participatory budgeting.

Practical Deployment

Implemented in cities worldwide (Paris, Madrid, Lisbon, New York, many others). Typically uses approval voting (each citizen approves a subset of projects). Computational challenges include project interactions (substitutes, complements), geographic fairness, and minimum funding thresholds.

Multi-Winner Elections and Committee Selection

Proportional Representation

Elect a committee of k candidates reflecting voter preferences proportionally.

  • Proportional Approval Voting (PAV): Approval-based; maximizes a harmonic welfare function: W(S) = sum_i H(|A_i intersect S|) where H is the harmonic function. NP-hard; satisfies extended justified representation. Sequential variant (seq-PAV/Reweighted Approval Voting) is polynomial.
  • Single Transferable Vote: Iterative; satisfies Droop proportionality criterion.
  • Monroe's rule: Assign voters to committee members; maximize total satisfaction. NP-hard.

Proportionality axioms (justified representation, extended JR, proportional JR) formalize the desiderata for multi-winner rules, paralleling single-winner axiomatics.