论文笔记[10]——Voting, the Symmetric Group, and Representation Theory

  • 用杨表和 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"...嗯?没找着...