Computational Social Choice and Computational Complexity: BFFs (Best Friends Forever)?

Lane A. Hemaspaandra

University of Rochester, USA

Abstract:

We discuss the connection between computational complexity and computational social choice (aka "comsoc," which for this talk will mostly be the study of computational aspects of election systems: who wins, how elections can be manipulatively attacked, etc.). We stress the work so far on, and urge continued focus on, two less-recognized aspects of this connection. Firstly, this is very much a two-way street: Everyone knows complexity classification is used in comsoc, but we also highlight benefits to complexity that have arisen from its use in comsoc. Secondly, less-known complexity tools often can be very productively used in comsoc.

This is an updated version of a talk first presented in the AAAI 2018 Senior Member Track. No prior knowledge of computational social choice or computational complexity is required to understand this talk.