15 October 2010, Computational Social Choice Seminar, Krzysztof Apt

Abstract

We study social networks in which the nodes influenced by the neighbours can adopt one out of several alternatives. We provide polynomial time algorithms that allow us to determine whether in a given social network a specific alternative can, respectively has to, be adopted by all nodes. We also provide a polynomial time algorithm that allows us to determine whether a given social network yields a unique outcome and a linear time algorithm that yields the answer for a natural class of networks. Joint work with E. Markakis.

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