  In this paper, we propose to use the concept of local fairness for auditing
and ranking redistricting plans. Given a redistricting plan, a deviating group
is a population-balanced contiguous region in which a majority of individuals
are of the same interest and in the minority of their respective districts;
such a set of individuals have a justified complaint with how the redistricting
plan was drawn. A redistricting plan with no deviating groups is called locally
fair. We show that the problem of auditing a given plan for local fairness is
NP-complete. We present an MCMC approach for auditing as well as ranking
redistricting plans. We also present a dynamic programming based algorithm for
the auditing problem that we use to demonstrate the efficacy of our MCMC
approach. Using these tools, we test local fairness on real-world election
data, showing that it is indeed possible to find plans that are almost or
exactly locally fair. Further, we show that such plans can be generated while
sacrificing very little in terms of compactness and existing fairness measures
such as competitiveness of the districts or seat shares of the plans.
