  In many practical scenarios, a population is divided into disjoint groups for
better administration, e.g., electorates into political districts, employees
into departments, students into school districts, and so on. However, grouping
people arbitrarily may lead to biased partitions, raising concerns of
gerrymandering in political districting, racial segregation in schools, etc. To
counter such issues, in this paper, we conceptualize such problems in a voting
scenario, and propose FAIR DISTRICTING problem to divide a given set of people
having preference over candidates into k groups such that the maximum margin of
victory of any group is minimized. We also propose the FAIR CONNECTED
DISTRICTING problem which additionally requires each group to be connected. We
show that the FAIR DISTRICTING problem is NP-complete for plurality voting even
if we have only 3 candidates but admits polynomial time algorithms if we assume
k to be some constant or everyone can be moved to any group. In contrast, we
show that the FAIR CONNECTED DISTRICTING problem is NP-complete for plurality
voting even if we have only 2 candidates and k = 2. Finally, we propose
heuristic algorithms for both the problems and show their effectiveness in UK
political districting and in lowering racial segregation in public schools in
the US.
