11 November 2011, Computational Social Choice Seminar, Francesca Rossi

Abstract

We investigate the computational complexity of finding optimal bribery and manipulation schemes in voting domains where the candidate set is the Cartesian product of a set of variables and agents' preferences are represented as CP-nets. We find that this change in the domain structure, which may lead to an exponential number of candidates in the size of the input, causes many existing computational results for bribery to break down. We provide new algorithms and complexity results which show that, in most cases, bribery in combinatorial domains is easy. This also holds for some cases of k-approval, where bribery is difficult in traditional domains. Joint work with N. Mattei, K.B. Venable, and M.S. Pini.

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