Complexity seminar

Presburger meets Cambridge Analytica

Martin Koutecký

IUUK MFF UK

Friday, 1. November 2019 - 13:30 to 15:00

in IM, rear building, ground floor

Cambridge Analytica is an infamous and now bankrupt (but sure to survive in some other way) company which helped manipulate elections all over the world (including the Brexit and Trump campaigns) through targeted advertising on social networks. We want to analyze such tasks and events from the perspective of computational complexity, asking questions such as: what is the cheapest bribery which makes my candidate win? what if opinion diffusion happens in the underlying social network? what if manipulation happens simultaneously by multiple agents? Answering these questions is helpful not only to a potential briber, but also to observers wishing to detect bribery or have meaningful measures of the (surprisingly elusive) notion of margin of victory.

Presburger arithmetic (PrA) is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger who introduced it in 1929 and proved its decidability. While the questions posed above are hard in general, we show that when the number of candidates and/or voter types is small, the problems can be formulated as model checking of short PrA sentences, and already Presburger's proof gives a fixed-parameter tractable algorithm. In this talk, I will present Cooper's algorithm from the 1970's which is faster than Presburger's original procedure. Still, many interesting questions remain open.

Presburger arithmetic (PrA) is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger who introduced it in 1929 and proved its decidability. While the questions posed above are hard in general, we show that when the number of candidates and/or voter types is small, the problems can be formulated as model checking of short PrA sentences, and already Presburger's proof gives a fixed-parameter tractable algorithm. In this talk, I will present Cooper's algorithm from the 1970's which is faster than Presburger's original procedure. Still, many interesting questions remain open.