Computational Social Choice and Computational Complexity: BFFs?
It addresses the integration of computational complexity into social choice theory, but is incremental as it reviews existing connections and calls for further focus.
The paper discusses the bidirectional relationship between computational social choice and computational complexity, highlighting that complexity tools benefit from applications in social choice and that less-known complexity methods can be effectively used in social choice.
We discuss the connection between computational social choice (comsoc) and computational complexity. 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, more subtle, less-known complexity tools often can be very productively used in comsoc.