Talk—Elections, Bribery, and Integer Programming

A former postdoc of my current advisor Shmuel Onn, Antoine Deza, organized a very nice workshop on Optimization and Discrete Geometry : Theory and Practice. I was very happy to give a talk where I tried to explain how our recent breakthroughs in computational social choice come from making connections to discrete geometry and integer programming.

First, we take a distinctly geometric viewpoint on elections, voting and bribery (paper). One implication is for example that we now see that the different computational complexity of bribery with respect to different voting rules is reflected in the geometric descriptive complexity of the set of societies where our preferred candidate wins:

  • For scoring protocols and Condorcet's rule, this set is a convex set,
  • For Copeland and many others it is a disjunction of convex sets, or, equivalently, the set of integer points of a projection of a convex sets,
  • For Dodgson and Young it is a set given by a ∀∃ quantifier alternation, that is, much more complex than the above.

Second, we observe that the original ILP (going back to the work of Bartholdi-Tovey-Trick from 1989) has a very special n-fold format, and we develop faster algorithms for ILPs of this form, thus speeding up existing algorithms significantly (paper). Intuitively, our algorithm works as follows. We start with some trivial bribery which makes our candidate win, but is too expensive. A key lemma says that if the current bribery is not optimal, then only a small number of voters need to be modified to obtain a cheaper bribery. Such a small augmenting step can then be found using dynamic programming, and repeatedly augmenting eventually brings us to the optimal solution.

Third, there's a few ideas about how to model more complex campaigning and where this gets stuck (currently). If you have any ideas on how to get unstuck, please email me, I'll be happy to collaborate!

Slides.

links

I passed on to you what was most important and what had also been passed on to me. Christ died for our sins, just as the Scriptures said. He was buried, and he was raised from the dead on the third day, just as the Scriptures said. He was seen by Peter and then by the Twelve. After that, he was seen by more than 500 of his followers at one time, most of whom are still alive, though some have died. Then he was seen by James and later by all the apostles. Last of all, as though I had been born at the wrong time, I also saw him.

Paul of Tarsus, The First Epistle to the Corinthians, likely written no more than five years after Jesus' death (one of the oldest New Testament fragments).

I believe this. If you're curious, feel free to ask!

social