论文笔记[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

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