Universiteit van Amsterdam

Archives

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

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

Please note that this newsitem has been archived, and may contain outdated information or links.