Gerrymandering Over Graphs

In many real-life scenarios, voting problems consist of several phases: an overall set of voters is partitioned into subgroups, each subgroup chooses a preferred candidate, and the final winner is selected from among those candidates. The attempt to skew the outcome of such a voting system through strategic partitioning of the overall set of voters into subgroups is known as “gerrymandering”. We investigate the problem of gerrymandering over a network structure; the voters are embedded in a social network, and the task is to divide the network into connected components such that a target candidate will win in a plurality of the components. We first show that the problem is NP-complete in the worst case. We then perform a series of simulations, using random graph models incorporating a homophily factor. In these simulations, we show that a simple greedy algorithm can be quite successful in finding a partition in favor of a specific candidate.

Authors

• Amittai Cohen-Zemach Hebrew University of Jerusalem
• Yoad Lewenberg
• Jeffrey S. Rosenschein

Keywords

• Voting
• Social Choice
• Gerrymandering
• Districts
• Social Networks