论文笔记[9]——Strategy-proof allocation of indivisible goods

文章:Svensson L G. Strategy-proof allocation of indivisible goods[J]. Social Choice and Welfare, 1999, 16(4): 557-567.
其实是夏老师 Allocating Indivisible Items in Categorized Domains 一文的单类型版本.

主要结果:strategyproof, nonbossy 且中立的分配机制 \(f\) 一定是 serial dictatorial.

Lemma 1\(f\) 是 strategyproof 且 nonbossy 的,若 \(u,v\in\mathscr{U}\) 满足:\(\forall i\in N,\forall x\in A\)\(u_i(x)\leqslant u_i(f_i(u)) \Rightarrow v_i(x)\leqslant v_i(f_i(u))\),则 \(f(v)=f(u)\).

  • 换言之:\(v\) 只要没有扩大 \(u\) 中优于 \(f_i(u)\) 的集合,就不会改变分配结果.
  • 证明:先证 \(f(v_i, u_{-i})=f(u)\),再取 \(u^{p}=(v_1,\ldots,v_{p-1},u_p,\ldots u_n)\) 进行证明.

Lemma 2\(f\) strategyproof, nonbossy 且中立的机制,profile \(u\) 中所有人的偏好都相同,则其分配结果是 Pareto 最优的.

  • 证明:反证法,假设不是 Pareto efficient,则存在一个 \(a\in A-\{f_i(u): i\in N\}\),s.t. ...

Thm 1 strategyproof, nonbossy 且中立的分配机制 \(f\) 一定是 serially dictatorial.

  • 同时,也容易验证 serially dictatorial 满足上述三条性质.

值得注意的是,在 Thm 1 中,nonbossy 是必须的,否则 \(f\) 未必是 serially dictatorial. - 若将其去掉,文中给出了反例; - 若将其替换为 pareto consistency,文中也给出反例.

Lemma 3\(\forall u\in\mathscr{U}\),恰好存在一个 core allocation \(\varphi\). 同时存在一个与之相对应的 \(N\) 的划分 \(\{N_j\}_{j=1}^r,~r\leqslant n\),s.t. \[A_j=\varphi(N_j)对 \forall 1\leqslant j\leqslant r 是\text{cycle},且若 i\in N_j,则 u_i(\varphi(i))\geqslant u_i(a),~\forall a\in A-\bigcup\limits_{k=1}^{j-1}A_k.\]

Thm. 2 一个 strategyproof,individually rational 且 pareto consistent 的机制 \(f\) 是一个 core mechanism.