Parameterized Algorithmics for Computational Social Choice: Nine Research Challenges

Computational Social Choice is an interdisciplinary research area involving Economics, Political Science, and Social Science on the one side, and Mathematics and Computer Science (including Artificial Intelligence and Multiagent Systems) on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics, on the occasion of his 60th birthday.

• Publication year

  2014

• Venue

  arXiv.org

• Publication date

  2014-07-08

• Fields of study

  Computer Science, Economics, Political Science

• Identifiers
  DOI 10.1109/TST.2014.6867518arXiv 1407.2143
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Partially Polynomial Kernels for Set Cover and Test Cover

  2016cited by this paper
• Fully Proportional Representation with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time

  2015cited by this paper
• Prices matter for the parameterized complexity of shift bribery

  2014cited by this paper
• Combinatorial voter control in elections

  2014cited by this paper
• Are there any nicely structured preference profiles nearby?

  2013cited by this paper
• Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity

  2013cited by this paper
• N-Person Cake-Cutting: There May Be No Perfect Division

  2013cited by this paper
• Theoretical and empirical evaluation of data reduction for exact Kemeny Rank Aggregation

  2013cited by this paper
• Complexity of Control Behaviors in k-Peaked Elections for a Variant of Approval Voting

  2013cited by this paper
• How to Put Through Your Agenda in Collective Binary Decisions

  2013cited by this paper
• A characterization of the single-crossing domain

  2013cited by this paper
• Parameterized complexity of control and bribery for d-approval elections

  2013cited by this paper
• Parameterized Enumeration of Neighbour Strings and Kemeny Aggregations

  2013cited by this paper
• Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems

  2013cited by this paper
• Fundamentals of Parameterized Complexity

  2013cited by this paper
• How to Cut a Cake Before the Party Ends

  2013cited by this paper
• A Multivariate Complexity Analysis of Lobbying in Multiple Referenda

  2012cited by this paper
• Studies in Computational Aspects of Voting - A Parameterized Complexity Perspective

  2012influential reference
• A characterization of the single-crossing domain

  2012influential reference
• Bounded Single-Peaked Width and Proportional Representation

  2012cited by this paper
• Kernelization - Preprocessing with a Guarantee

  2012cited by this paper
• Computational Aspects of Nearly Single-Peaked Electorates

  2012cited by this paper
• Computing socially-efficient cake divisions

  2012cited by this paper
• Clone structures in voters' preferences

  2011cited by this paper
• The complexity of manipulative attacks in nearly single-peaked electorates

  2011cited by this paper
• Confronting intractability via parameters

  2011cited by this paper
• Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard

  2011cited by this paper
• Handbook of Social Choice and Welfare

  2011cited by this paper
• Campaign Management Under Approval-Driven Voting Rules

  2011cited by this paper
• Computational Social Choice: Prospects and Challenges

  2011cited by this paper
• A characterization of the single-peaked domain

  2011cited by this paper
• Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates

  2010cited by this paper
• The Complexity of Manipulating k-Approval Elections

  2010cited by this paper
• Recognizing one-dimensional Euclidean preference profiles

  2010cited by this paper
• Parameterized complexity of control problems in Maximin election

  2010cited by this paper
• Average parameterization and partial kernelization for computing medians

  2010cited by this paper
• Approximation Algorithms for Campaign Management

  2010cited by this paper
• Making decisions based on the preferences of multiple agents

  2010influential reference
• Reflections on Multivariate Algorithmics and Problem Parameterization

  2010cited by this paper
• Multivariate Complexity Analysis of Swap Bribery

  2010influential reference
• W-Hierarchies Defined by Symmetric Gates

  2010cited by this paper
• Using complexity to protect elections

  2010influential reference
• Essai Sur L'Application de L'Analyse a la Probabilite Des Decisions Rendues a la Pluralite Des Voix

  2009cited by this paper
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control

  2009cited by this paper
• Fixed-parameter algorithms for Kemeny rankings

  2009cited by this paper
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control

  2009cited by this paper
• Parameterized computational complexity of control problems in voting systems

  2009cited by this paper
• Kernelization: New Upper and Lower Bound Techniques

  2009cited by this paper
• On the complexity of crossings in permutations

  2009cited by this paper
• Swap Bribery

  2009cited by this paper
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms

  2009cited by this paper
• Computational Complexity: A Modern Approach

  2009cited by this paper
• Parameterized computational complexity of Dodgson and Young elections

  2008cited by this paper
• A fixed-parameter algorithm for the directed feedback vertex set problem

  2008cited by this paper
• Parameterized complexity of candidate control in elections and related digraph problems

  2008cited by this paper
• On Parameterized Intractability: Hardness and Completeness

  2008cited by this paper
• Parameterized Complexity and Approximation Algorithms

  2008influential reference
• Combinatorial Optimization on Graphs of Bounded Treewidth

  2008cited by this paper
• Parameterized Complexity of Vertex Cover Variants

  2007cited by this paper
• Invitation to fixed-parameter algorithms

  2007cited by this paper
• Uncertainty in Preference Elicitation and Aggregation

  2007cited by this paper
• A Short Introduction to Computational Social Choice

  2007influential reference
• Invitation to data reduction and problem kernelization

  2007cited by this paper
• Parameterized Complexity Theory

  2006cited by this paper
• Treewidth: Characterizations, Applications, and Computations

  2006cited by this paper
• Approximability and Computational Feasibility of Dodgson's Rule

  2006cited by this paper
• Approximability and Computational Feasibility of Dodgson's Rule

  2006cited by this paper
• Strong computational lower bounds via parameterized complexity

  2006cited by this paper
• How Hard Is Bribery in Elections?

  2006cited by this paper
• Anyone but him: The complexity of precluding an alternative

  2005cited by this paper
• Tight lower bounds for certain parameterized NP-hard problems

  2004cited by this paper
• A Structural View on Parameterizing Problems: Distance from Triviality

  2004cited by this paper
• Parameterized Complexity of Vertex Colouring

  2003cited by this paper
• A Logic For Causal Reasoning

  2003cited by this paper
• Rank Aggregation Revisited

  2002cited by this paper
• 《Tsinghua Science and Technology》网上国际审稿

  2002cited by this paper
• Chapter 4 Voting procedures

  2002cited by this paper
• Rank aggregation methods for the Web

  2001cited by this paper
• Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts

  1999cited by this paper
• Cake-cutting algorithms - be fair if you can

  1998cited by this paper
• Parameterized Complexity

  1998cited by this paper
• Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP

  1997cited by this paper
• Advice Classes of Parameterized Tractability

  1997cited by this paper
• Graph Theory

  1997cited by this paper
• On limited nondeterminism and the complexity of the V-C dimension

  1993cited by this paper
• Mathematics without Numbers

  1993cited by this paper
• How hard is it to control an election? Math

  1992cited by this paper
• Voting schemes for which it can be difficult to tell who won the election

  1989cited by this paper
• Minkowski's Convex Body Theorem and Integer Programming

  1987cited by this paper
• An application of simultaneous diophantine approximation in combinatorial optimization

  1987cited by this paper
• Integer Programming with a Fixed Number of Variables

  1983cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982influential reference
• Methods of amalgamation

  1982cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• Voting over income tax schedules

  1977cited by this paper
• Fair and reasonable election systems

  1975cited by this paper
• On the Rationale of Group Decision-making

  1948cited by this paper
• Voting Procedures

  year unknowncited by this paper
• Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence Kemeny Elections with Bounded Single-Peaked or Single-Crossing Width

  year unknowncited by this paper

• Committee Elections with Candidate Attribute Constraints

  2026cites this paper
• Policy Strategies for Training Public Sector Executives to Develop Artificial Intelligence Skills

  2024cites this paper
• Committee Elections with Candidate Attribute Constraints

  2024cites this paper
• Computational Social Choice: Parameterized Complexity and Challenges

  2024cites this paper
• Complexity of shift bribery for iterative voting rules

  2022cites this paper
• Fine-Grained Liquid Democracy for Cumulative Ballots

  2022cites this paper
• Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules

  2022cites this paper
• Resolute control: Forbidding candidates from winning an election is hard

  2022cites this paper
• Gehrlein Stable Committee with Multi-modal Preferences

  2022cites this paper
• Fine-Grained Complexity and Algorithms for the Schulze Voting Method

  2021cites this paper
• Broadening the Research Agenda for Computational Social Choice: Multiple Preference Profiles and Multiple Solutions

  2021cites this paper
• Thou Shalt Love Thy Neighbor as Thyself When Thou Playest: Altruism in Game Theory

  2021cites this paper
• Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP

  2020cites this paper
• Beyond the Worst-Case Analysis of Algorithms

  2020cites this paper
• Participatory Budgeting with Project Groups

  2020cites this paper
• Integer programming in parameterized complexity: Five miniatures

  2020cites this paper
• Assessing the public policy-cycle framework in the age of artificial intelligence: From agenda-setting to policy evaluation

  2020cites this paper
• Towards Reality: Smoothed Analysis in Computational Social Choice

  2020cites this paper
• Computational Social Choice and challenges оf voting in multi-agent systems

  2019cites this paper
• Problems in Computational Mechanism Design

  2019cites this paper
• Understanding success through the diversity of collaborators and the milestone of career

  2018cites this paper
• Some Hard Stable Marriage Problems: A Survey on Multivariate Analysis

  2018cites this paper
• A Unifying Framework for Manipulation Problems

  2018cites this paper
• Voting and Bribing in Single-Exponential Time

  2018cites this paper
• Stable Marriage with Multi-Modal Preferences

  2018cites this paper
• A reliable path between target users and clients in social networks using an inverted ant colony optimization algorithm

  2017cites this paper
• On the Computational Complexity of Variants of Combinatorial Voter Control in Elections

  2017cites this paper
• Mixed Integer Programming with Convex/Concave Constraints: Fixed-Parameter Tractability and Applications to Multicovering and Voting

  2017cites this paper
• Balanced Stable Marriage: How Close is Close Enough?

  2017cites this paper
• Resolving the Complexity of Some Fundamental Problems in Computational Social Choice

  2017cites this paper
• Combinatorial n-fold integer programming and applications

  2017cites this paper
• Stable Matching Games: Manipulation via Subgraph Isomorphism

  2017cites this paper
• Having a Hard Time? Explore Parameterized Complexity!

  2017cites this paper
• Integer Programming in Parameterized Complexity: Three Miniatures

  2017cites this paper
• Parameterized Complexity News 2 Johan Kwisthout TOP grant

  2017cites this paper
• Parameterization in Computational Social Choice

  2016cites this paper
• Parameterized Complexity of Winner Determination in Minimax Committee Elections

  2016cites this paper
• Approximation and Parameterized Complexity of Minimax Approval Voting

  2016cites this paper
• Beyond Intractability: A Computational Complexity Analysis of Various Types of Influence and Stability in Cooperative Games

  2016cites this paper
• Algorithmic aspects of manipulation and anonymization in social choice and social networks

  2016cites this paper
• From Election Fraud to Finding the Dream Team: A Study of the Computational Complexity in Voting Problems and Stability in Hedonic Games

  2016cites this paper
• Complexity of Shift Bribery in Committee Elections

  2016influential citation
• A method of competition result evaluation based on social choice theory

  2016cites this paper
• Exploiting structure in computationally hard voting problems

  2016cites this paper
• A trust-based probabilistic recommendation model for social networks

  2015cites this paper
• Modeling Emotion Influence in Image Social Networks

  2015cites this paper
• Multivariate complexity analysis of team management problems

  2015cites this paper
• Elections with Few Candidates: Prices, Weights, and Covering Problems

  2015cites this paper
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics

  2015cites this paper
• On the Parameterized Complexity of Minimax Approval Voting

  2015cites this paper
• Author Credit for Transdisciplinary Collaboration

  2015cites this paper
• Diffusion of “Following” Links in Microblogging Networks

  2015cites this paper
• A deep exploration of the complexity border of strategic voting problems

  2015cites this paper
• Who Influenced You? Predicting Retweet via Social Influence Locality

  2015cites this paper
• Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty

  2015cites this paper
• Multivariate Algorithmics for NP-Hard String Problems

  2014cites this paper
• Kernelization complexity of possible winner and coalitional manipulation problems in voting

  2014cites this paper
• Prices matter for the parameterized complexity of shift bribery

  2014cites this paper
• Elections with Few Voters: Candidate Control Can Be Easy

  2014cites this paper
• How to Put Through Your Agenda in Collective Binary Decisions

  2013cites this paper
• Are there any nicely structured preference profiles nearby?

  2013cites this paper