Explainable Voting

The design of voting rules is traditionally guided by desirable axioms. Recent work shows that, surprisingly, the axiomatic approach can also support the generation of explanations for voting outcomes. However, no bounds on the size of these explanations is given; for all we know, they may be unbearably tedious. We prove, however, that outcomes of the important Borda rule can be explained using $O(m^2)$ steps, where $m$ is the number of alternatives. Our main technical result is a general lower bound that, in particular, implies that the foregoing bound is asymptotically tight. We discuss the significance of our results for AI and machine learning, including their potential to bolster an emerging paradigm of automated decision making called virtual democracy.

Authors

• Dominik Peters CNRS, LAMSADE, Université Paris Dauphine - PSL
• Ariel D. Procaccia Harvard University
• Alexandros Psomas
• Zixin Zhou

Keywords

No keywords are indexed for this paper.