- 用杨表和 tabloid 来描述偏好和选票；
- 将计票过程是为模同态，进而应用 Schur 引理等表示论的内容来研究投票过程.
基础知识
整数划分与 tabloid
- 称 \(\lambda=(\lambda_1,\ldots,\lambda_m)\)，s.t. \(\sum\limits_{i=1}^m \lambda_i=n\) 为 \(n\) 的一个分解(composition)，若该序列是递减的，则称为一个划分(partition)；
- 给定 \(n\) 的划分 \(\lambda\)，考虑 \(n\) 个方块的一个图表，第 \(i\) 行有 \(\lambda_i\) 个格子，这样的图表称为形状为 \(\lambda\) 的杨表；
- 现给出杨表的一个等价关系：每行的元素集合相等，则两个杨表等价，容易验证这是一个等价关系；
- 杨表在该等价关系下的一个等价类叫做一个（形状为 \(\lambda\) 的） tabloid.
- 形状为 \(\lambda\) 的全体 tabloid 记为 \(X^\lambda\)；
- \(X^\lambda\) 上所有函数 \(f: X^\lambda\to\mathbb{Q}\) 记作 \(M^\lambda\).
- \(X^\lambda\) 中所有元的示性函数构成 \(M^\lambda\) 的一组基，进而有 \(\dim M^\lambda=|X^\lambda|\).
与投票建立联系
- 偏好与 tabloid：\(i\succ j\iff i\) 在 \(j\) 的上层；\(i\sim j\iff i\) 与 \(j\) 在同一层.
- 换言之，一个序就是一个 tabloid.
- 进一步，给定 \(\lambda\) 之后，一个 profile 就是一个 \(p\in M^\lambda\).
- 偏序与全序的转化：
- 偏序 \(\to\) 全序：同一行的权重均分；
- 转化的映射：\(\iota: M^\lambda\to M^{(1,\ldots,1)}\).
对称群 \(S_n\) 的作用
\(S_n\) 在 \(X^\lambda\) 上有自然的左乘作用. 可通过定义 \((\sigma p)(x)=p(\sigma^{-1}x)\) 将该作用提升到 \(M^\lambda\) 上. 进一步可扩展为 \(\mathbb{Q}S_n\) 的作用.
这说明什么？？？这意味着什么？？？意味着 \(M^\lambda\) 是 \(\mathbb{Q}S_n\)-模.
从现在开始，主要讨论全序（\(\lambda=(1,\ldots,1)\)）情形.
对投票过程的分析
投票？模同态！
这里主要讨论的是位置投票(positional voting) 以及孔多塞投票 (Condorcet voting)
位置投票制
核心：权重向量 \(w=[w_1,\ldots,w_n]^T\).
- 计票：映射 \(T_w: M^{(1,\ldots,1)}\to M^{(1,n-1)}\).
- 这个映射的线性性很好验证.
位置投票的中立性告诉我们 \(\forall \sigma\in S_n\)，总有 \(T_w(\sigma p)=\sigma T_w(p)\).
这意味着什么？？？意味着 \(T_w\) 与群运算相容. 换言之，\(T_w\) 是模同构！
孔多塞投票
定义这里不多赘述. 其核心是拉两个元素出来配对比较. 因而其计票过程是一个配对映射 \(P: M^{(1,\ldots,1)}\to M^{(1,1,n-2)}\)（同样可以验证其线性性）
类似地，\(P\) 也是模同态.
那这样，我们用群表示的芝士知识来分析分析吧.
首先，\(\mathbb{Q}\) 是一个特征为 \(0\) 的域，因此我们可以做什么？可以用 Maschke 定理. 即所有的 \(M^\lambda\) 都是半单的，即可以分解为 \(\mathbb{Q}S_n\) 单模的直和. - 这里在GTM 203里有经典的结果：specht module. 这个结果正是利用整数拆分来做的.
那我们就把 \(M^\lambda\) 拆成不可约模的直和，然后呢？
然后可以用 Schur 引理啊！这样我们就可以知道哪些选票是有用的，哪些是无用的了. 进一步还可以得到一些其他的结果.
值得一提的是，这些结果与 Saari 先前的一些结果能够相互印证.
部分序情形：Approval voting
这一部分讨论给全序加断点后的故事，即 \(\lambda=(1,\ldots,1,n-k)\).
Borda count 的特殊性
总的来说，我觉得这篇文章没有真正落实作者的豪言壮语…“重建了一些 voting paradox”…嗯？没找着…