12 January 2015, Computational Social Choice Seminar, Maria Polukarov

Abstract

Multi-agent decision problems, in which independent agents have to agree on a joint plan of action or allocation of resources, are central to various applications. Often in such settings, agents' individual preferences over available alternatives may vary, and they may try to reconcile these differences by voting. Based on the fact that agents may have incentives to vote strategically and misreport their real preferences, much of the literature in computational social choice focuses on evaluating voting rules by their resistance to strategic behaviours and uses computational complexity as a barrier to them. In contrast, more recent works (counting from 2010) take another natural approach and analyse voting scenarios from a game-theoretic perspective, viewing strategic parties as players and examining possible stable outcomes of their interaction (i.e., equilibria). Finally, the candidates themselves may also have preferences about the outcome and try to affect it by strategically choosing whether to stand for election or not.

We model such strategic behaviours by voters and candidates as voting/candidacy games, and analyse the existence of stable game outcomes, as well as their reachablity by natural iterative processes, such as best-response dynamics or its restricted variants. Convergence of such procedures is a highly desirable property of the game, since, from a system-wide perspective, it implies that a system has a deterministic stable state that can be reached by the agents without any centralised control and/or communication. The talk will give an overview of the existing results and present some work in progress.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle.endriss at uva.nl).