用二维地图可视化选举相似性,揭示选举间的结构关系。
Drawing a Map of Elections
- 构建选举地图框架,基于位置距离度量相似性。
- 在2D空间中布局选举点,相似度高的点更靠近。
- 适合研究选举结构或算法性能的学者使用。
本文提出选举地图框架,包含三个核心要素:(1)选举数据集(即候选人集合上的序数投票集合),(2)衡量选举间相似性的方法,(3)将选举在二维欧氏空间中表示为点,使得相似性高的选举点更接近。我们主要使用合成选举数据集,但也展示了真实选举的示例。由于同构交换距离计算复杂度过高,无法实用,因此提出可多项式时间计算的位置距离作为替代。在二维表示上,主要采用Kamada-Kawai算法,也展示两种备选方案。我们建立了必要的理论基础,并通过实验验证地图的准确性和可信性。此外,通过按获胜候选人得分、整数线性规划求解器运行时间、特定算法近似比等标准对选举着色,有助于分析多项实验结果。
原文摘要 · Abstract (English)
Our main contribution is the introduction of the map of elections framework. A map of elections consists of three main elements: (1) a dataset of elections (i.e., collections of ordinal votes over given sets of candidates), (2) a way of measuring similarities between these elections, and (3) a representation of the elections in the 2D Euclidean space as points, so that the more similar two elections are, the closer are their points. In our maps, we mostly focus on datasets of synthetic elections, but we also show an example of a map over real-life ones. To measure similarities, we would have preferred to use, e.g., the isomorphic swap distance, but this is infeasible due to its high computational complexity. Hence, we propose polynomial-time computable positionwise distance and use it instead. Regarding the representations in 2D Euclidean space, we mostly use the Kamada-Kawai algorithm, but we also show two alternatives. We develop the necessary theoretical results to form our maps and argue experimentally that they are accurate and credible. Further, we show how coloring the elections in a map according to various criteria helps in analyzing results of a number of experiments. In particular, we show colorings according to the scores of winning candidates or committees, running times of ILP-based winner determination algorithms, and approximation ratios achieved by particular algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。