17 December 2012, Computational Social Choice Seminar, Justin Kruger

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 (ulle.endriss at uva.nl).