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!