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.
翻译:在本文中,我们提议在审计和重新划分地区计划时采用地方公平概念;在重新划分地区计划时,分化群体是一个人口平衡的毗连地区,大多数个人都具有同样的利益,而且属于各自地区的少数;这样一群人对重新划分计划如何制定有合理的抱怨;一个没有分化群体的重新划分计划称为地方公平;我们表明,对地方公平计划的审计问题已经完成;我们为审计和重新划分计划提出了MCMC方法;我们还为审计问题提出了一个动态的基于规划的算法,我们用这种算法来显示我们的MCMC方法的有效性;我们利用这些工具,检验真实世界的选举数据是否公平,表明确实有可能找到几乎或完全公平的计划;此外,我们表明,这种计划可以产生,同时很少牺牲紧凑性和现有的公平措施,例如地区或计划席位份额的竞争力。