Social Choice in a Social Context: A Multivariate Algorithmics Perspective

点击翻译按钮获取中文摘要

The goal of this research project is to revise and extend established models of Computational Social Choice in order to capture effects induced by the social neighborhood of the agents (e.g. voters in an election). Such effects may be of cooperative flavor (e.g. agents may cooperate if they know each other), of competitive flavor (e.g. agents behave strategically and anticipate their opponents to also behave strategically), or based on privacy issues (e.g. agents prefer not to reveal their complete preferences). I propose to analyze the influence of such effects on the algorithmic complexity. To this end, concepts from algorithmic game theory, multivariate algorithmics, social networks, and voting theory will be used. For the identification of tractable cases, restricted domains of preferences will play a decisive role.