• Overview
• Details
• Exercises

Computational social choice (COMSOC) studies algorithms and complexity for collective decision-making: voting, preference aggregation, and fair allocations. We survey classic voting rules, complexity-theoretic barriers to manipulation and control, and algorithmic tools for winner determination, approximation, and parameterized methods.

• Preferences and profiles: Linear orders, ties, and domains (single-peaked/single-crossing) that admit efficient algorithms.
• Voting rules: Plurality, Veto, Borda, k-approval, Copeland, Maximin, STV/IRV, Ranked pairs, Schulze; Condorcet winners/cycles.
• Winner determination: Polytime for many rules; NP-hardness for others (e.g., Kemeny). Approximation and FPT on parameters (#candidates, distance to structure).
• Manipulation, bribery, control: Strategic behavior models; complexity as a barrier (NP-hard/Σp-hard) vs tractable cases.
• Impossibility and axioms: Arrow, Gibbard–Satterthwaite (high level); monotonicity, independence of irrelevant alternatives, participation.
• Proportional representation: Committee rules (STV variants, Monroe, Chamberlin–Courant); approximation and parameterized results.
• Fair division (glimpse): Cake cutting and discrete allocation; envy-freeness, proportionality, EF1/EFX (pointer to literature).
• Data and robustness: Incomplete/uncertain preferences; elicitation; noise models.

1. Given a 4-candidate profile, compute the Plurality, Borda, and Condorcet winners (if any). Compare outcomes.
2. Sketch why manipulation for Borda with unbounded candidates is NP-hard. What parameters make the problem FPT?
3. Formulate Kemeny winner determination as an optimization problem. Propose an ILP or approximation approach and discuss trade-offs.