论文笔记[6]——Fair assignment of indivisible objects under ordinal preferences

发表于 | 分类于

文章：Aziz H , Gaspers S , Mackenzie S , et al. Fair assignment of indivisible objects under ordinal preferences[J]. Artificial Intelligence, 2015, 227:71-92.

离散物品，公平分配

主要结果

基础知识

  • Assignment problem 是一个三元组 \((N,O,\succeq)\)：
    • \(N=\{1,2,\cdots,n\}\)：参与者；
    • \(O=\{o_1,\cdots,o_m\}\)：待分配物品（离散物品）；
    • \(\succeq=\{\succeq_1,\cdots,\succeq_n\}\)：人对物品的偏好（单物品偏好，Ordinal preference）；
  • 考虑到偏好可能是非严格的，因此将所有被选手 \(i\) 视为等值的物品记为一个等价类；
    • 选手 \(i\) 的等价类共有 \(k_i\) 个；
    • 按照顺序为 \(E_i^1,\cdots,E_i^{k_i}\)；
    • 若某个 \(E_i^j\) 只包含一个物品 \(o\)，则我们在表示该等价类时，不区分 \(o\) 与 \(\{o\}\) 的区别；
    • 若所有 \(E_i^j\) 都只包含一个物品，则此时的偏好是 严格 的。
  • 设有 \(O'\subseteq O\)，定义如下两个记号：
    • \(\max_{\succeq_i}(O')=\{o\in O':o\succeq_i o', \forall o'\in O'\}\)；
    • \(\min_{\succeq_i}(O')=\{o\in O':o'\succeq_i o, \forall o'\in O'\}\)；
  • 一个分数分配（fractional assignment）\(p\) 是指一个 \((n\times m)\) 双随机矩阵 \([p(i)(o_j)]\)；
    • 实际上就是 Bogomolnaia 和 Moulin 所著 “A New Solution to the Random Assignment Problem” 一文中的随机性分配（random assignment），参见 论文笔记[1]——随机分配问题的PS算法和依次有效性 一文；
      • 本文中对此的理解与 “New solution” 一文不同，没有以概率的眼光看待 \(p(i)(o_j)\)，而是认为 \(i\) 得到了 \(o_j\) 的一部分。两种思路其实是等价的；
    • 一个分数分配是 离散 的（discrete），如果所有的 \(p(i)(o_j)\) 不是 \(1\) 就是 \(0\)。
    • 平均分配（uniform assignment）是指 “每个人，都得到每个物品的 \(1/n\)” 的一个分数分配；
  • 随机占优（stochastic dominance）的定义如下：

Def 1.（随机占优） 参考 论文笔记[1]——随机分配问题的PS算法和依次有效性 一文中随机占优关系的定义。 这里记为 \(p(i)\succeq_i^{SD} q(i)\)。

  • 严格随机占优 就是指 \(p(i)\) 随机占优于 \(q(i)\)，但反之不然；
  • 所有与偏好 \(\succeq_i\) 相容的效用函数构成的集合记为 \(\mathcal{U}(\succeq_i)\)。

Def 2.（无嫉妒） 若对 \(\forall i\)，都有 \[u_i(p(i))\geqslant u_i(p(j)),~\forall j\in N\] 则称 \(p\) 是无嫉妒的。（基本上都是这个定义吧）

Def 3.（Proportional） 若 \(\forall i\)，都有 \[u_i(p(i))\geqslant u_i(O)/n\] 则称 \(p\) 是 Proportional 的。（可以将其翻译为“按比例满足”）

现在给出如下定理：

Th 1.（随机占优的等价命题） 对于 离散 的分配 \(p\) 和 \(q\)，下列命题等价：

  1. \(p(i)\succeq_i^{SD} q(i)\)；
  2. \(\forall u_i\in \mathcal{U}(\succeq_i)\)，有 \(u(p(i))\geqslant u_i(q_i))\)；
  3. \(p(i)\succeq_i^{RS} q(i)\)；

Proof. 首先，1 \(\iff\) 2 是显然的；

接下来我们证明 3 \(\Rightarrow\) 2：由于 \(p(i)\succeq_i^{RS} q(i)\)，故可以建立一个从 \(q(i)\) 到 \(p(i)\) 的单射，且 \(p(i)\) 中的物品比 \(q(i)\) 中的对应物品更受 \(i\) 的喜爱（即效用值更大）。因此 2 成立。

最后我们证明 1 \(\Rightarrow\) 3：假设 \(p(i)\not\succeq_i^{RS} q(i)\)。以 \(V=q(i)\cup p(i)\) 为结点构造二分图 \(G(V,E)\)，其中 \(\{o,o'\}\in E\) 当且仅当 \(o\in q(i)\)，\(o'\in p(i)\)，且 \(o'\succeq_i o\)。由于 \(p(i)\not\succeq_i^{RS} q(i)\)，故 \(G\) 不存在填满 \(q(i)\) 的匹配，因而不存在完美匹配。由 Hall 定理，可得结论。

公平性定义框架

Proportional

弱 SD-proportional

没有人更 SD-喜欢 平均分配，即 \(\lnot[(1/n,,cdots,1/n)\succ_i^{SD} p(i)]\)，\(\forall i\in N\)；

可能 proportional

对每个人，都存在效用函数，使得在该效用下这个分配是 proportional 的，即 \(\forall i\in N\)，\(\exists u_i\in\mathcal{U}(\succeq_i)\)，s.t. \(u_i(p(i))\geqslant u_i(O)/n\)；

SD proportional

每个人相比起 平均分配，都更喜欢 \(p\)，即 \(p(i)\succeq_i^{SD} (1/n,\cdots,1/n)\)，\(\forall i\in N\)；

必然 proportional

对每个人来说，只要是与偏好相容的效用函数，效用都不低于 平均分配，即 \(\forall i\in N\)，\(\forall u_i\in\mathcal{U}(\succeq_i)\)，总有 \(u_i(p(i))\geqslant u_i(O)/n\)；

无嫉妒

弱 SD-无嫉妒

每个人都不 SD-严格喜欢其他人所得的物品，即 \(\lnot[p(j)\succ_i^{SD} p(i)]\)，\(\forall i\in N\)；

可能 SD-无嫉妒

对每个人，都存在与其偏好相容的效用函数，使得在该函数下，这个分配是无嫉妒的，即 \(\forall i\in N\)，\(\exists u_i\in\mathcal{U}(\succeq_i)\)，s.t. \(u_i(p(i))\geqslant u_i(p(j))\)，\(\forall j\in N\)。

可能完全无嫉妒

对每个人 \(i\)，都存在一个集合的弱序（weak order），使得该弱序与 \(i\) 的偏好的某个 responsive 扩展相容，且在该弱序下，\(i\) 认为自己得到的东西优于其他人。

  • （虽然一眼看不懂是啥，但是后面好像证明了这玩意儿和 弱 SD-无嫉妒 等价…

SD-无嫉妒

每个人都不会 SD-更喜欢其他人得到的东西，即 \(\forall i\in N\)，总有 \(p(i)\succeq_i^{SD} p(j)\)，\(\forall j\in N\)；

必然无嫉妒

所有与参与者偏好相容的效用函数，都会使得该分配是无嫉妒的，即 \(\forall i,j\in N\)，\(\forall u_i\in\mathcal{U}(\succeq_i)\)，有 \(u_i(p(i))\geqslant u_i(p(j))\)；

必然完全无嫉妒

对每个人 \(i\)，对于任一个集合的全序（total order），只要该全序与 \(i\) 的偏好的某个 responsive 扩展相容，那么在该全序下，\(i\) 就会认为自己得到的东西优于其他人。

  • （虽然一眼看不懂是啥，但是后面好像证明了这玩意儿和 SD-无嫉妒 等价…

以上定义之间的关系

Th 2.（等价关系） 对于任意数量的参与者和物品，有：

  1. 弱 SD-proportional \(\iff\) 可能 proportional；
  2. SD-proportional \(\iff\) 必然proportional；
  3. 弱 SD-无嫉妒 \(\iff\) 可能完全无嫉妒；
  4. SD-无嫉妒 \(\iff\) 必然无嫉妒 \(\iff\) 必然完全无嫉妒。

Th 3.（强弱关系） 对于以上公平性定义，有：

  1. SD-无嫉妒 \(\Rightarrow\) SD-proportional；
  2. SD-proportional \(\Rightarrow\) 弱 SD-proportional；
  3. 可能无嫉妒 \(\Rightarrow\) 弱 SD-proportional；
  4. 可能无嫉妒 \(\Rightarrow\) 弱 SD-无嫉妒。

对于两个参与者的情形，有：

Th 4.（退化情形） 只有 \(2\) 个参与者时，有：

  1. proportional \(\iff\) 无嫉妒；
  2. SD-proportional \(\iff\) SD-无嫉妒；
  3. 可能无嫉妒 \(\iff\) 弱 SD-proportional；
  4. 可能无嫉妒 \(\iff\) 弱 SD-无嫉妒。

可将几种定义的关系总结如下：

几种定义的关系图

计算复杂度

主要关心的问题：

  • 是否存在满足某一公平性条件的离散分配；
    • 若存在，如何得到这样的分配；
  • 验证给定分配方案是否满足某一公平性定义；
    • 这个显然很容易做…

Remark 1. 对于所有的公平性定义，都可以在 \(m\) 和 \(n\) 的多项式时间内验证某一给定分配方案是否满足该公平性定义。

Remark 2. 对于常数个物品和任一种公平性定义，均可以在多项式时间内判定是否存在满足条件的离散分配方案。

Th 5. 若 \(p\) 是一个 SD-proportional 的分配，则 \(n~|~m\)，且分配方案中一定是每个人得到 \(m/n\) 个物品。

Th 6. 可以在多项式时间内判定是否存在 SD-proportional 的分配，即便偏好不是严格的。（原文用 agents are allowed to express indifference between objects.）

Th 7. 在严格的偏好下，存在 弱 SD-proportional 的分配，当且仅当：

  1. \(m=n\) 且存在一个匹配方案，使得每个人都不会得到他最不喜欢的物品；
  2. \(m>n\)。

进一步，该过程显然是多项式时间的，这说明 弱 SD-prop 是可以在多项式时间内判定存在性的。

Th 8. 可以在多项式时间内判定是否存在 SD-proportional 的分配，即便偏好不是严格的。（原文用 agents are allowed to express indifference between objects.）