Archives

Institute for Logic, Language and Computation


11 November 2011, Computational Social Choice Seminar, Francesca Rossi

Speaker: Francesca Rossi (Padova)
Title: Bribery in Voting over Combinatorial Domains is Easy
Date: Friday 11 November 2011
Time: 16:00
Location: Room A1.10, Science Park 904, Amsterdam

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 ().


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