An Introduction to Computa­tional Social Choice

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 survey some recent algorithmic developments in the context of problems that arise in voting; including issues such as winner determination, manipulation, control and bribery. Specifically, we will discuss the use of computational intractability as an effective workaround in the light of axiomatic impossibility results. On the other hand, we will also provide an overview of positive algorithmic efforts for winner determination problems, with a focus on voting rules that are NP-hard to compute.