Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

17 December 2012, Computational Social Choice Seminar, Justin Kruger

Speaker: Justin Kruger
Title: Convergence of Iterative Voting in Small Cases
Date: Monday 17 December 2012
Time: 11:45
Location: Room B0.209, Science Park 904, Amsterdam

Abstract

It is a well-known result that every reasonable social choice function is manipulable. Iterative voting attempts to turn this into an advantage, describing a process in which convergence to a Nash equilibrium may occur. After everyone initially votes, individual agents are given the opportunity to change their vote. Depending on various conditions, the process may be guaranteed to converge, e.g., when Plurality voting and a linear order tie-breaking rule are used.

For certain conditions, however, counterexamples have been found showing that convergence is not certain. In this talk, after presenting the framework, I will strengthen one such previous negative result by giving smaller counterexamples for cases that have not yet been considered. Conversely, it will be shown that in small enough cases convergence is guaranteed. Finally, I will give some examples of what happens if the framework is modified in an unconsidered, but plausible, way: allowing individuals to change their votes according to rankings of sets of outcomes.

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

Please note that this newsitem has been archived, and may contain outdated information or links.