论文笔记[8]——Allocating Indivisible Items in Categorized Domains

发表于 | 分类于

文章：Allocating Indivisible Items in Categorized Domains

  • CDAP (categorized domain allocation problem)：多个类别的不可分物品被分配给若干 agent，每个 agent 在每一类中至少获得一个物品。
    • 本文讨论的是常见的情形：一个 agent 只获取每一类的一个物品
  • CSAM (categorial sequential allocation mechanism)：serial dictatorship 的推广，将分配拆分成多个轮次，每轮每个候选人从指定类别中选取一个 bundle。
    • Serial dictatorship 的刻画：三个公理化特征
      • Strategyproofness;
      • Non-bossiness;
      • Category-wise neutrality.

分配问题的相关研究所面临的三大障碍：

  • 偏好瓶颈（Preference bottleneck）：当物品个数较多时，bundle 的偏好情况将以指数级别增长；
  • 计算瓶颈（Computational bottleneck）：即便能够使用某种偏好语言简洁地表达他们的偏好，计算“最优”分配通常也是困难的；
  • Agent 的策略（Threats of agents’ strategic behavior）：agent 可能谎报偏好，以获得更好的 bundle。这可能导致社会效率低下的分配。

主要工作

  1. 关于 Basic CDAP：每个类别中的物品数量都等于 agent 数量。
    • 首先用三条公理化特征来描述 serial dictatorship：
      • Strategyproofness：不能通过谎报偏好来获取更大好处；
      • Non-bossiness：不能在不改变自己偏好的情况下改变其他 agent 的分配；
      • Category-wise neutrality：类别标记不改变分配结果；
    • 上述三条特征可以帮我们克服“Agent 的策略”带来的影响。
  2. 为克服偏好和计算瓶颈，并且防止 serial dictatorship，定义 CSAM
    • CSAM 是一类间接机制，前文描述过其过程。
  3. 两种 myopic agent 下 CSAM 最坏情况下的效率：
    • Optimistic agent：总是选择当前可选的最优 bundle 中的物品；
    • Pessimistic agent：总是选择最坏情形下的最优项目。

Categorized Domain Allocation Problems

Def 1. 一个 categorized domain 由 \(p\geqslant 1\) 个不可分的物品类构成，用 \(\{D_1,\ldots,D_p\}\)。在一个 CDAP 中，物品被分配给 \(n\) 个 agent，每个 agent 至少获取每类中的一个物品。

  • 对于一个 basic categorized domain，\(\forall i\)，\(|D_i|=n\)，\(\mathfrak{D}=D_1\times\cdots\times D_p\)，agent 的偏好为 \(\mathfrak{D}\) 上的一个序。
  • 在 basic CDAP 中，每个 agent 在每一类中恰好得到一个物品。
  • 我们研究的主要对象是 non-sharable items，即每个物品只能分配给一个 agent；
  • \(\mathfrak{D}\) 中的元素被称为一个 bundle；
  • 对 \(\forall j\in \{1,2,\ldots,n\}\)，令 \(R_j\) 表示一个 \(\mathfrak{D}\) 上的序；
    • 用 \(P=(R_1,\ldots,R_n)\) 表示所有 agent 的偏好构成的 profile.
  • 分配 \(A\) 是 \(\{1,2,\ldots,n\}\to \mathfrak{D}\) 的一个映射，s.t. \[\bigcup\limits_{j=1}^nA(j)_i=D_i\]
  • 一个分配机制是一个函数，输入为 profile，输出为一个分配
    • 用 \(f^j(P)\) 表示机制 \(f\) 在 profile \(P\) 下分配给 agent \(j\) 的 bundle.

三条公理化性质

Strategyproofness

对于 \(\forall\) profile \(P\)，\(\forall\) agent \(j\)，以及 \(\mathfrak{D}\) 上的序 \(R_j'\)，都有： \[f^j(P)\succ_{R_j} f^j(R_j',R_{-j}).\]

Non-bossiness

  • \(f\) 满足 non-bossiness 当且仅当 agent 中不存在黑社会；
    • 黑社会：通过谎报自己的偏好来改变他人的分配结果，但不改变自己的分配结果。

对于 \(\forall\) profile \(P\)，\(\forall\) agent \(j\)，以及 \(\mathfrak{D}\) 上的序 \(R_j'\)，都有： \[[f^j(P)=f^j(R_j',R_{-j})]\Rightarrow [f(P)=f(R_j',R_{-j})].\]

Category-wise neutrality

对 \(\forall P\)，\(\forall i\)，取置换 \(\sigma\in S_n\)，将其作用在 \(D_i\) 上不改变分配结果，即总有： \[f(\sigma(P))=\sigma(f(P)).\]

Serial dictatorship 由一个 \(\{1,2,\ldots,n\}\) 上的序 \(\mathcal{K}\) 来表达，所有 agent 按照 \(\mathcal{K}\) 所规定的顺序选取物品，每次都选择当前所能选取的物品中，他所认为优先级最高的物品。

Serial dictatorship 的公理化特征

Th 1. 对于任意满足 \(p\geqslant 2\)，\(n\geqslant 2\) 的 basic CDAP，一个分配机制是 strategyproof, non-bossy, 且 category-wise neutral 的，当且仅当它是 serial dictatorship. 进一步，这三条公理是刻画 serial dictatorship 的最低要求。

  • 以下引理表明，对于任何 strategyproof 且 non-bossy 的机制 \(f\)，以及任意 profile \(P\)。若某些 agent \(j\) 谎报了偏好，但未扩大比 \(f^j(P)\) 顺位更高的 bundle 集合，则分配结果不会改变。

Lemma 1. 令 \(f\) 为一个 \(p\geqslant 2\) 的 basic categorized domain 上的一个 strategyproof 且 non-bossy 的分配机制。对任意 profile \(P,P'\)，若 \(\forall j\leqslant n\)，总有： \[\{\vec{d}\in\mathfrak{D}: \vec{d}\succ_{R_j'} f^j(P)\}\subseteq \{ \vec{d}\in\mathfrak{D}:\vec{d}\succ_{R_j} f^j(P) \}\] 则 \(f(P)=f(P')\).

对于一个 \(\mathfrak{D}\) 上的序 \(R\)以及 bundle \(\vec{d}\in\mathfrak{D}\)，若序 \(R'\) 相比 \(R\) 只提升了 \(\vec{d}\) 的位置，而不改变其他 bundle 的相对位置，则称 \(R'\) 为 \(\vec{d}\) 在 \(R\) 上的一个 pushup.

  • 以下引理表明，对于任意 strategyproof 且 non-bossy 的机制 \(f\), 若某个 agent 在谎报偏好时，报告的偏好是 \(\vec{d}\) 的 pushup，则只会导致以下两种结果之一：
    • 其他 agent 获得的东西都不改变；
    • 该 agent 获得 \(\vec{d}\).

Lemma 2. 令 \(f\) 是一个 \(p\geqslant 2\) 的 basic categorized domain 上的 strategyproof，non-bossy 的分配机制，则对任意 profile \(P\)，\(\forall j\leqslant n\)，以及 \(\forall \vec{d}\) 和 \(\vec{d}\) 在 \(R_j\) 上的一个 pushup，只有以下两种结果之一会发生：

  1. \(f(R_j',R_{-j})=f(R)\) （什么都没变）;
  2. \(f^j(R_j',R_{-j})=\vec{d}\) （agent \(j\) 得到了 \(\vec{d}\)）.

Lemma 3. 对任意 \(p\geqslant 2\) 的 basic categorized domain，所有 strategyproof，non-bossy，category-wise neutral 的分配机制都是帕累托最优的。

  • 以下引理表明，对任意 strategyproof 且 non-bossy 的机制 \(f\), 以及任意 profile \(P\) 中的一对 agent \(j_1\)，\(j_2\)，不存在这样的 bundle \(\vec{c}\)：它由 \(j_1\)，\(j_2\) 在 \(f\) 下得到的物品构成，同时 \(j_1\) 和 \(j_2\) 都更喜欢 \(\vec{c}\).

Lemma 4. 令 \(f\) 是一个 \(p\geqslant 2\)，\(n\geqslant 2\) 的 basic categorized domain 上的 strategyproof，non-bossy 的分配机制。\(\forall\) profile \(P\) 以及 \(\forall j_1\neq j_2\leqslant n\)，令 \(\vec{a}=f^{j_1}(P)\)，\(\vec{b}=f^{j_2}(P)\)，则： \[不存在 \vec{c}\in(a_1,b_1)\times\{a_2,b_2\}\times\cdots\times\{a_p,b_p\} ，s.t.~~\vec{c}\succ_{R_{j_1}} \vec{a}~~且~~\vec{c}\succ_{R_{j_2}} \vec{b}\] 其中 \(a_i\) 是 \(\vec{a}\) 的第 \(i\) 位的物品。

Proof. 用反证法：假设对某个 profile \(P\)，存在这样的 \(j_1\)，\(j_2\)，和 \(c\). 设 \(\vec{d}\) 表示 \(\vec{c}\) 在 \(\vec{a}\cup\vec{b}\) 中的补集，则 \(\forall i\)，都有 \(\{a_i,b_i\}=\{c_i,d_i\}\). 我们按照如下步骤构造反例：

  1. 令 \(\hat{R}_{j_1}=[\vec{c}\succ\vec{a}\succ\vec{d}\succ\vec{b}\succ 其他]\)，\(\hat{R}_{j_2}=[\vec{c}\succ\vec{b}\succ\vec{a}\succ\vec{d}\succ 其他]\)，其余 \(j\) 满足 \(\hat{R}_j=[f^j(P)\succ 其他]\). 则由 Lemma 1，有 \(f(\hat{P})=f(P)\).
  2. 令 \(\bar{R}_{j_2}=[\vec{c}\succ\vec{a}\succ\vec{b}\succ\vec{d}\succ 其他]\)，由于 \(\bar{R}_{j_2}\) 为 \(\vec{a}\) 在 \(\hat{R}_{j_2}\) 上的 pushup，故由 Lemma 2，\(f^{j_2}(\bar{R}_{j_2},\hat{R}_{-j_2})\) 为 \(\vec{a}\) 或 \(\vec{b}\). 可由帕累托最优性（Lemma 3）得知不可能是 \(\vec{a}\)，故只能有 \(f^{j_2}(\bar{R}_{j_2},\hat{R}_{-j_2})=\vec{b}=f^{j_2}(\hat{P})\). 故由 non-bossiness，可得 \(f(\bar{R}_{j_2},\hat{R}_{-j_2})=f(\hat{P})=f(P)\).
  3. 令 \(\bar{R}_{j_1}=[\vec{c}\succ\vec{b}\succ\vec{a}\succ\vec{d}\succ 其他]\)，与 2 类似可得 \(f(\bar{R}_{j_1},\bar{R}_{j_2},\hat{R}_{-\{j_1,j_2\}})=f(P)\).
  4. 令 \(\mathring{R}_{j_2}=[\vec{c}\succ\vec{a}\succ\vec{d}\succ\vec{b}\succ 其他]\)，由 Lemma 1 可得 \(f(\bar{R}_{j_1},\mathring{R}_{j_2},\hat{R}_{-\{j_1,j_2\}})\) 中，\(j_1\) 获得 \(\vec{b}\)，\(j_2\) 获得 \(\vec{a}\)，其余 \(j\) 所得与 \(f(P)\) 相同.
  5. 令 \(\mathring{R}_{j_1}=[\vec{c}\succ\vec{a}\succ\vec{b}\succ\vec{d}\succ 其他]\)，与 2 类似可得 \(f(\mathring{R}_{j_1},\mathring{R}_{j_2},\hat{R}_{-\{j_1,j_2\}})=f(\bar{R}_{j_1},\mathring{R}_{j_2},\hat{R}_{-\{j_1,j_2\}})\).
  6. 由于 \(\mathring{R}_{j_1}\) 是 \(\vec{b}\) 在 \(\hat{R}_{j_1}\) 上的一个 pushup，故由 Lemma 1，可得 \(f(\mathring{R}_{j_1},\bar{R}_{j_2},\hat{R}_{-\{j_1,j_2\}})=f(\hat{R}_{j_1},\bar{R}_{j_2},\hat{R}_{-\{j_1,j_2\}})\). 式子的右端便是 2 中的 profile.

由 5 和 6 得到的结果，若 agent 们的偏好为 \(\mathring{R}_{j_1}\) 和 \(\bar{R}_{j_2}\)，则 \(j_2\) 可通过将自己的偏好谎报为 \(\mathring{R}_{j_2}\) 以获取更大利益。这与 strategyproof 矛盾。Lemma 4 得证。

证明 Lemma 4 的 6 步

  • 容易验证 serial dictatorship 是 strategyproof，non-bossy，且 category-wise neutral 的，接下来我们证明满足以上三条的性质只有 serial dictatorship.

令 \(R^*\) 是 \(\mathfrak{D}\) 上满足以下几条的序：

  1. \((1,\ldots,1)\succ (2,\ldots,2)\succ\cdots\succ (n,\ldots,n)\);
  2. \(\forall j<n\)，\((j,\ldots,j)\) 与 \((j+1,\ldots,j+1)\) 之间的 bundle 都满足以下两条（记为 \(B_j\)）：
    1. 至少有一维是 \(j\)；
    2. 所有维度的值都在 \(\{j,j+1,\ldots,n\}\) 中.
  3. \(\forall j\) 以及 \(\forall \vec{d},\vec{e}\in B_j\)，若 \(\vec{d}\) 中 \(j\) 的数量严格多余 \(\vec{e}\)，则 \(\vec{d}\succ\vec{e}\).

Thenextclaimstatesthatf agreeswithaserialdictatorship on the profile (R ∗ ,…,R ∗ ) where all agents have the same preferences R ∗ that we have just defined. We will later show that f agrees with the same serial dictatorship on all profiles.

Claim 1. 令 \(P^*=(R^*,\ldots,R^*)\)，则对 \(\forall l\leqslant n\)，存在 \(j_l\leqslant n\)，s.t. \(f^{j_1}(P)=(l,\ldots,l)\).

事实上，这个定理是比较负面的一个结果。因为它意味着同时满足三条的分配机制并不好，因此我们需要舍弃其中至少一条。其中 non-bossy 是比较不自然的。

Categorial Sequencial Allocation Mechanisms (CSAM)

给定 \(\{1,\ldots,n\}\times\{1,\ldots,p\}\) 上的序 \(\mathcal{O}\)，由 \(\mathcal{O}\) 生成的 CSAM \(f_\mathcal{O}\) 的过程分为 \(np\) 个步骤：

  • 在第 \(t\) 步中，设 \(\mathcal{O}\) 的第 \(t\) 顺位为 \((j,i)\).
  • Agent \(j\) 被称为第 \(t\) 步中的 active agent，他将选择（可选择的）物品 \(d_{j,i}\in D_i\)；
  • 将 \(d_{j,i}\) 广播给所有的 agent.

Protocol of CSAM

后面是一些效率的问题，先略过。