Sequential Apportionment from Stationary Divisor Methods

这是一份关于论文《Sequential Apportionments from Stationary Divisor Methods》（基于静止除数法的序贯分配）的详细技术总结。

1. 研究背景与问题 (Problem)

背景：
在比例代表制中，除数法（Divisor Methods）被广泛用于根据政党得票比例分配席位。常见的除数法包括 D'Hondt 法（最大除数法）、Adams 法（最小除数法）和 Sainte-Laguë 法（Webster 法）。这些方法通常满足“席位单调性”（House Monotonicity），即随着总席位的增加，没有任何政党的席位会减少。这一性质使得席位可以按顺序（序贯地）分配。

核心问题：
尽管除数法在分配最终席位数量方面研究充分，但关于席位分配的顺序（即哪个政党在何时获得下一个席位）的研究相对较少。这种顺序在实际应用中至关重要，例如：

• 政治联盟与内阁组建： 在北爱尔兰等地，内阁职位的分配顺序直接决定了部长职位的归属。
• 即时生产（JIT）调度： 在工业工程中，JIT 排序问题与席位分配具有相同的数学结构，需要决定处理物品的顺序以满足需求。

具体目标：
本文旨在研究由静止除数法（Stationary Divisor Methods）生成的序贯分配序列。静止除数法由一个截断点（cutpoint）$c \in [0, 1]$ 参数化。作者试图：

1. 刻画所有可能的序贯分配序列。
2. 建立序列与参数 $c$ 之间的数学联系。
3. 确定在 $n$ 个政党情况下不同序列的数量。
4. 重新审视“规模偏差”（Size Bias）的概念，从“谁获得更多席位”转向“谁更早获得席位”。

---

2. 方法论 (Methodology)

核心定义与模型：

• 静止除数法： 定义截断点 $c \in [0, 1]$。对于拥有 $p_i$ 票且已获得 $a_i$ 席位的政党 $i$，下一个席位分配给最大化比率 $p_i / (a_i + c)$ 的政党。
  • $c=0$: Adams 法（有利于小党）。
  • $c=0.5$: Sainte-Laguë/Webster 法。
  • $c=1$: D'Hondt 法（有利于大党）。
• 序贯分配序列： 记为 $S_c(p) = (s_1, s_2, \dots)$，其中 $s_j$ 表示第 $j$ 个席位归属的政党编号。
• 周期性： 当选票为整数时，静止除数法生成的序列是周期性的。周期长度 $P = (p_1 + \dots + p_n) / \gcd(p_1, \dots, p_n)$。

分析工具：

1. 字典序排序（Lexicographical Ordering）： 将分配序列视为向量，通过字典序比较不同 $c$ 值生成的序列。
2. 两党模型分析（Two-Party Analysis）： 首先解决 $n=2$ 的情况，利用弱比例性（Weak Proportionality）和齐次性（Homogeneity）推导序列结构。
3. 提升算法（Lifting Algorithm）： 利用除数法的一致性（Consistency）性质，即任意两个政党之间的子序列与仅考虑这两个政党时生成的序列相同。通过组合所有 $\binom{n}{2}$ 个两党序列来构建 $n$ 党序列。
4. 容斥原理（Inclusion-Exclusion Principle）： 用于计算 $n$ 党情况下不同序列的总数，通过统计所有两党对产生的截断点区间的并集。

---

3. 主要贡献与结果 (Key Contributions & Results)

A. 序列的周期性与结构

• 定理 2： 证明了对于整数选票，静止除数法生成的序列是周期的，周期长度为 $P$。如果选票比例是无理数，则序列非周期。
• 两党序列刻画（第 3 节）：
  • 对于两党 $p_1 > p_2$，序列由重复模式组成，形式为 $1^{k_1}, 2, 1^{k_2}, 2, \dots$。
  • 引理 1： 小党（Party 2）永远不会连续获得两个席位。
  • 定理 3 & 4： 给出了指数 $k_i$ 的显式公式，并证明当 $c$ 在区间 $[\frac{\ell}{p_1-p_2}, \frac{\ell+1}{p_1-p_2})$ 内变化时，序列保持不变。
  • 结论： 对于互质的两党，共有 $p_1 - p_2 + 1$ 种不同的分配序列（包括 $c=1$ 的特殊情况）。

B. 字典序与偏差的重新定义

• 命题 2： 序列的字典序与截断点 $c$ 严格相关。若 $c > c'$，则 $S_c \le S_{c'}$（在字典序下）。
  • $c=0$ (Adams) 生成字典序最大的序列（大党最早获得席位）。
  • $c=1$ (D'Hondt) 生成字典序最小的序列（小党相对较晚获得席位，或者说大党获得席位的时间点被推后，但实际是 Adams 法让大党在序列开头就获得席位，而 D'Hondt 法让大党在序列中分布更均匀但整体靠后？修正：根据论文 Proposition 2 证明，$c$ 越大，序列在字典序上越小。这意味着 $c=0$ 时，大党（Party 1）在序列中出现得更早/更频繁地占据前几位；$c=1$ 时，序列“更小”，意味着小党（Party 2）在序列中相对更早出现，或者说大党获得席位的间隔变大。）
  • 核心洞察： 规模偏差（Size Bias）不再仅仅是关于最终席位的数量，而是关于获得席位的时间点。Adams 法让大党在序列早期就获得席位，而 D'Hondt 法则让大党在序列中分布得更晚（相对而言）。

C. 多党序列的构建与计数（第 4 节）

• 提升算法（Algorithm 1）： 提出了一种算法，通过合并所有 $\binom{n}{2}$ 个两党序列来构建 $n$ 党序列。该算法利用了一致性性质：在任意时刻，有且仅有一个政党在 $n-1$ 个两党子序列的“最左侧”出现，该政党获得下一个席位。
• 序列计数定理（Theorem 8）：
  • 利用容斥原理计算 $n$ 党情况下不同序列的数量。
  • 公式为：$1 + |\bigcup_{k \in M} A_k|$，其中 $A_k$ 是每对政党产生的截断点区间端点集合，$M$ 是所有政党对的集合。
  • 具体计算涉及计算所有两党对 $(p_i, p_j)$ 的 $m_{ij} = (p_i - p_j)/\gcd(p_i, p_j)$ 的最大公约数组合。

D. Adams 法与 D'Hondt 法的新关系

• 定理 1： 揭示了 Adams 法序列 $S_0(p)$ 与 D'Hondt 法序列 $S_1(p)$ 之间的精确关系：$S_0(p)$ 的前 $n$ 项是 $(1, 2, \dots, n)$，随后的项与 $S_1(p)$ 完全相同。即 $S_0(p) = (1, 2, \dots, n, s_1, s_2, \dots)$，其中 $(s_1, s_2, \dots) = S_1(p)$。
• 这意味着 Adams 法仅仅是让每个政党先获得一个席位，然后后续的分配过程与 D'Hondt 法完全一致。

---

4. 应用案例 (Case Study)

论文以北爱尔兰议会（Northern Ireland Assembly）2022 年选举为例：

• 数据： 四个主要政党席位（作为票数代理）：Sinn Féin (27), DUP (25), Alliance (17), UUP (9)。
• 应用： 使用 D'Hondt 法（$c=1$）分配内阁职位。
• 分析：
  • 计算表明，对于该数据，存在 25 种不同的序贯分配序列（对应不同的 $c$ 值）。
  • 比较 Adams ($c=0$) 和 D'Hondt ($c=1$) 的前 8 个席位分配顺序：
    • D'Hondt: 1, 2, 3, 1, 2, 1, 4, 3
    • Adams: 1, 2, 3, 4, 1, 2, 3, 1
  • 虽然最终前 8 席的总数分配可能相同，但顺序不同，这直接影响内阁职位的分配结果（例如，第 6 个职位在 D'Hondt 下给 UUP，而在 Adams 下给 Sinn Féin）。

---

5. 意义与结论 (Significance & Conclusion)

1. 理论突破： 首次系统性地刻画了静止除数法生成的所有可能的序贯分配序列，并给出了 $n$ 党情况下不同序列数量的精确计算公式。
2. 重新定义偏差： 将“规模偏差”从静态的席位数量比较，转化为动态的时间/顺序偏差。这为理解不同除数法对政治博弈（如内阁组建）的影响提供了新的视角。
3. 算法贡献： 提出的“提升算法”提供了一种从两党序列构建多党序列的机械且有效的方法，简化了复杂系统的分析。
4. 实际应用： 为政治学家和决策者提供了工具，用于评估在不同除数法参数下，内阁职位或 JIT 调度顺序可能产生的变化，有助于减少政治谈判中的策略性博弈，或优化工业调度中的公平性。
5. 局限性： 目前主要关注整数选票和静止除数法。对于非静止除数法（如 Hill-Huntington 法，其序列可能非周期）以及非整数选票的情况，仍需进一步研究。

总结： 该论文通过严谨的数学推导，揭示了序贯分配序列的周期性、字典序结构及其与除数法参数的内在联系，为比例代表制中的席位分配顺序问题提供了全新的理论框架和计算工具。