Proportionality Guarantees in Elections with Interdependent Issues

Proportionality Guarantees in Elections with Interdependent Issues

Markus Brill, Evangelos Markakis, Georgios Papasotiropoulos, Jannik Peters

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2537-2545. https://doi.org/10.24963/ijcai.2023/282

We consider a multi-issue election setting over a set of possibly interdependent issues with the goal of achieving proportional representation of the views of the electorate. To this end, we employ a proportionality criterion suggested recently in the literature, that guarantees fair representation for all groups of voters of sufficient size. For this criterion, there exist rules that perform well in the case where all the issues have a binary domain and are independent of each other. In particular, this has been shown for Proportional Approval Voting (PAV) and for the Method of Equal Shares (MES). In this paper, we go two steps further: we generalize these guarantees for issues with a non-binary domain, and, most importantly, we consider extensions to elections with dependencies among issues, where we identify restrictions that lead to analogous results. To achieve this, we define appropriate generalizations of PAV and MES to handle conditional ballots. In addition to proportionality considerations, we also examine the computational properties of the conditional version of MES. Our findings indicate that the conditional case poses additional challenges and differs significantly from the unconditional one, both in terms of proportionality guarantees and computational complexity.
Keywords:
Game Theory and Economic Paradigms: GTEP: Computational social choice