Constraint-based electoral districting using a new compactness measure: An application to Portugal
提出一种新的紧凑性度量方法和布尔优化模型，用于解决葡萄牙选区划分问题，满足连续性和代表性标准，并通过实验证明其有效性，同时展示了不同划分对选举结果的影响。
Since the 1960s, several approaches have been proposed to prevent the redrawing of electoral districts so that they are beneficial to a particular party or political faction (gerrymandering). In order to avoid gerrymandering, most approaches focus solely on redrawing electoral maps that try to maximize the compactness of the electoral districts. However, this problem is computationally hard, and several criteria must be satisfied when drawing electoral maps. In this work we focus on drawing electoral districts for Portugal. For that, a new compact Boolean formulation is proposed for solving the electoral districting problem. This formulation satisfies all standard criteria for building electoral maps, particularly the contiguity and representation criteria. Moreover, a new compactness measure is also proposed that does not depend on geographic centers. Additionally, a heuristic formulation is also devised for problem instances where the optimum values are hard to find. The new compactness measure and formulations are applied in the context of Portuguese parliament elections, assuming a change in the Portuguese electoral system. Experimental results on drawing electoral maps show that the proposed formulations are more effective than previous ones in drawing the electoral districts in the Portuguese context. Moreover, based on results from the last elections, gerrymandering scenarios are devised, showing that electoral outcomes can change depending on the drawing of the electoral maps.