Efficient Algorithms for Hard Problems on Structured Electorates

Computational social choice is a rapidly evolving research trend concerned with the design and analysis of methods for collective decision making. In this talk, we will focus mostly on voting-inspired scenarios, where we have multiple agents (voters) expressing their preferences over a fixed set of alternatives (candidates), and the goal is to find a consensus (a winner or a committee or a ranking) that, as far as possible, reflects the collective opinions of all the agents. We will survey some algorithmic developments in the context of problems like winner determination, committee formation, and manipulation, all of which are fundamental to voting scenarios. In particular, we will survey various restricted domains, both in the context of rankings and dichotomous preferences. We will consider examples that demonstrate how the structure in these domains can be exploited to make otherwise hard problems tractable. We will also describe some ideas for detecting whether a given instance belongs to these domains, and more generally, if the instance is close to a structured domain. In the context of the latter, the notion of closeness will usually be based on candidate or voter deletion. Some results that will be described here are based on joint work with Palash Dey.