Institute for Logic, Language and Computation

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


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 or contact Ulle Endriss ().

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X