论文笔记[14]——Private Pareto Optimal Exchange

Justin Hsu 在其 STOC 2014 的工作中表明了,在 dp,甚至是放宽条件后的 Joint-dp 之下,都无法保证得到一个渐进 Pareto 最优的分配(在所有分配参与者都是理性的情况下). 因此,在此工作中使用了比 Joint-dp 更为宽松的 Marginal-dp,并在此条件下找到了渐进 Pareto 最优的分配.

  • 文中描述的是一个以物易物的市场,即需要给定一个初始分配.

Sampath Kannan, et al. Private pareto optimal exchange. ACM Transactions on Economics and Computation (TEAC), 2018.

MODEL

  • \(k\) 种类型的物品,类型集合记为 \(\mathcal{G}=\{g_1,\ldots,g_k\}\). \(n\) 个 agent,记为 \(N\)
    • 初始状态下,每个人都有每个物品恰好一个;
    • 每个人都对所有物品有一个偏好,记为 \(\succ_i\)
  • \(N_j=\{i: g_i=j\}\)\(n_i=|N_j|\),用以表示把物品 \(j\in\mathcal{G}\) 带入市场的 agent.
    • 由于每个人每种物品只带一个,故 \(\sum_{j\in\mathcal{G}} n_j=n\)

定义 2.3 (IR) 一个分配 \(\pi\) 若满足 \(\pi(i)\succeq_i g_i,~\forall i\in N\),则称其是 Individual Rational(IR)的.

定义 2.4 (\(\alpha\)-PO) 一个分配 \(\pi\),若对其他任何分配 \(\pi'\),若存在 \(S\subset N\),s.t. \(|S|>\alpha n\)\(\pi'(i)\succ_i \pi(i)\)\(\forall i\in S\),则必定存在一些 \(j\in N\backslash S\),s.t. \(\pi(j)\succ_j \pi'(j)\),则称 \(\pi\)\(\alpha\)-Pareto Optimal(PO)的.

  • 换言之, 一个分配是 \(\alpha-PO\) 的,如果严格提升 \(\alpha\) 比例的 agent 的收益,会严格损害至少一个 agent 的利益.

定义 2.5(Joint dp) 机制 \(M:\mathcal{X}^n\to O^n\) 满足 \((\epsilon,\delta)\)-joint dp,如果 \(\forall i\in[n]\),以及 \(x_i,x_i'\in\mathcal{X}\)\(\mathbf{x}_{-i}\in\mathcal{X}^{n-1}\),以及 \(\forall B_{-i}\subseteq O^{n-1}\),总有: \[\left.\mathbb{P}\left(M\left(\mathbf{x}_{-i}, x_{i}\right)_{-i} \in B_{-i}\right) \leq e^{\epsilon} \mathbb{P}\left(M\left(\mathbf{x}_{-i}, x_{i}^{\prime}\right)\right)_{-i} \in B_{-i}\right)+\delta.\]

本文提出了一个比联合差分隐私更宽松的隐私:边缘差分隐私:

定义 2.6 (Marginal dp) 机制 \(M:\mathcal{X}^n\to O^n\) 满足 \((\epsilon,\delta)\)-marginal dp,如果 \(\forall i\neq j\)\(\forall \mathbf{x}_{-i}\in\mathcal{X}^{n-1}\)\(\forall x_i,x_i'\in\mathcal{X}\),以及 \(\forall B\subset O\),总有: \[\mathbb{P}\left(M\left(\mathbf{x}_{-i}, x_{i}\right)_{j} \in B\right) \leq e^{\epsilon} \mathbb{P}\left(M\left(\mathbf{x}_{-i}, x_{i}^{\prime}\right)_{j} \in B\right)+\delta.\]

LOWER BOUNDS

  1. 在 Joint-dp 下,无法同时满足 IR 和 渐进PO.
  2. 在 Marginal-dp 下,所有 IR 且 \(\alpha\)-PO 的分配都需要满足 \(\alpha=\Omega(k/n)\). 其中 \(k\) 表示物品种类数.

在 Joint-dp 下的不可能结果

不可能结果是基于如下断言来证明的:

CLAIM 3.1 不存在 \((\epsilon,\delta)\)-dp 机制 \(M:\{0,1\}\to \{0,1\}\),s.t. \(\mathbb{P}(M(b)=b)>\frac{e^\epsilon+\delta}{e^\epsilon+1}\)\(b=0,1\).

  • 利用 dp 的定义即可证明.

在 exchange markets 中,设 \(\mathcal{X}=\mathcal{G}\times\mathcal{T}\),其中 \(\mathcal{G}\) 是物品的类型,\(\mathcal{T}\)\(\mathcal{G}\) 上的线性序.

  • 下面的定理说明了不能同时保证隐私性、IR、和 \(o(1)\)-PO.

定理 3.2\(\forall \epsilon,\delta,\beta>0\),若有一个机制 \(M_J:\mathcal{X}^n\to\mathcal{G}^n\) 满足 \((\epsilon,\delta)\)-Joint dp,满足 IR,且有至少 \(1-\beta\) 的概率满足 \(\alpha\)-PO,则: \[\alpha \geq 1-\frac{e^{\epsilon}+\delta}{(1-\beta)\left(e^{\epsilon}+1\right)}.\]

  • 证明:利用 Claim 3.1 进行归约. 若存在满足条件且 \(\alpha>...\) 的机制,则可以构造出与 Claim 3.1 矛盾的 \(M:\{0,1\}\to\{0,1\}\).

定理 3.3\(\forall \epsilon,\delta,\beta>0\),若有一个机制 \(M_S:\mathcal{X}^n\to\mathcal{G}^n\) 满足 \((\epsilon,\delta)\)-Marginal dp,满足 IR,且有至少 \(1-\beta\) 的概率满足 \(\alpha\)-PO,则: \[\alpha \geq \frac{k(1-\beta)}{n}\left(1-\frac{e^{\epsilon}+\delta}{e^{\epsilon}+1}\right).\]

  • 证明思路与 3.2 类似.

PRIVATE TOP TRADING CYCLE(TTC)

本节主要提出了一个算法 PTTC,能够在 marginal-dp 下得到 IR 且 \(\alpha\)-PO 的分配.

首先,什么是 TTC?

  • TTC 是一种 exchange market 的分配机制. 具体算法如下:
1
2
3
4
5
6
7
8
9
初始状态:n 个人 1,...,n,每个人有一个物品 a_1,...,a_n. 
初始状态下 a_i 在 i 手中,且可被分配的物品池为所有物品.

1. 从某个人 i 出发,找到他在当前物品池中最喜欢的物品 a_j;
2. 找到 a_j 的主人,当然是 j;
3. 重复进行步骤 1,2 直至成环;
4. 若 i -> j -> ... -> i 构成一个环,则给环上的所有人分配他们最喜欢的物品;
5. 并把这些物品从物品池中删除;
6. 若物品池非空,继续进行上述步骤,直到物品池空.

接下来是 PTTC:

  • 输入是一个 Exchange market:\(\mathbf{x}=(g_i,\succ)_{i=1}^n\)
  • 考虑有向完全图 \(G=(V,A)\)
    • 结点 \(u\in V\) 代表一个 \(\mathcal{G}\) 中的物品. \(\forall e=(u,v)\in A\)
    • 定义 \(P_{(u,v)}\) 为拥有物品 \(u\),但最喜欢 \(v\) 的人所构成的集合,i.e. \(P_{(u,v)}=\{i\in N: g_i=u~且~v\succeq_i g,~\forall g\in V\}\)
  • 弧的权重(Arc weight):\(w_e=|P_e|\)\(\forall e\in A\).
  • \(N_u\) 表示拥有物品 \(u\) 的人构成的集合. 易有 \(N=\bigcup_{u\in V} N_u\).

其具体步骤如下:

1
2
3
4
step 1. 计算 arc-weights,并且加噪音(保护隐私);
step 2. 把在每条边上权重都足够大的环清除掉,这一步确定哪些物品需要被交易(dp);
step 3. 执行交易(只能满足 marginal-dp);
step 4. 把交易涉及的物品从物品池中删去. 有必要的话,返回 step 1.

具体分析:

Step 1:给 arc-weight 加入参数为 \(1/\epsilon'\) 的 Laplace 噪声 \(Z_e\),其中: \[\epsilon^{\prime}=\frac{\epsilon \log \left(k^{3} / \beta\right)}{2 \sqrt{8}\left(\log \left(k^{3} / \beta\right) \sqrt{k \log \left(1 / \delta_{1}\right)}+k \sqrt{k \log \left(1 / \delta_{2}\right)}\right)}.\]

Step 2:若存在环 \(C\),其中的边都满足 \(\lfloor\hat{w}_e\rfloor>0\),则令 \(\hat{W}=\min_{e\in C}\{\lfloor\hat{w}_e\rfloor\}\)\(C\) 的权重. 若无环,则到 Step 4.

Step 3:若 Step 2 中得到了权重为 \(\hat{W}\) 的环 \(C\),则 \(\forall e\in C\),都从 \(P_e\) 中选取 \(\hat{W}\) 个 agent,分别沿着边 \(e\) 进行交易,称这些 agent 为 satisfied agents,记为 \(S_e\).

Step 4:若 Step 2 中没有满足条件的环,则必定存在结点 \(v\),s.t. \(\hat{n}_v=\sum\limits_{e:e=(v,z),z\in V}\hat{w}_e<k\)

Step 5 若我们分配了超量的物品,或者我们选择进行交易的人超过了想要交易的人的数量,则取消这些物品的交易,并把这些人初始拥有的物品还给他们.

原文 Appendix 中的伪代码如下:

A pseudo-code for PTTC

以下为本文的核心结果之一:

定理 4.1\(\epsilon,\delta_1,\delta_2,\beta>0\),PTTC 提供 \((\epsilon,\delta_1+\delta_2+\beta)\)-marginal dp 保护,输出的结果为 IR,同时有 \(1-\beta\) 的概率输出 \(\alpha\)-PO 的结果,其中: \[\alpha=O\left(\frac{k^{3}}{\epsilon n} \cdot\left(\sqrt{k \log \left(1 / \delta_{1}\right)} \log \left(k^{3} / \beta\right)+k \sqrt{k \log \left(1 / \delta_{2}\right)}\right)\right).\]

效率的证明(PO and IR)

引理 4.2 PTTC 输出的结果是 IR 的.

定理 4.6\(\epsilon,\delta_1,\delta_2,\beta>0\),PTTC 以 \(1-\beta\) 的概率输出 \(\alpha\)-PO 的分配,其中 \[\alpha=\tilde{O}\left( \frac{k^{9/2}}{\epsilon n} \right).\] 因此,PTTC 是渐进 PO 的.

隐私性分析

首先是一个引理,它展示了证明 marginal-dp 的一个途径:

引理 4.11\(M^1:\mathcal{X}\to O\)\((\epsilon_1,\delta_1)\)-dp 的,\(M_j^2:\mathcal{X}^{n-1}\times\mathcal{X}\times O\to R\)\(j=1,\ldots,n\) 对其第一个变量为 \((\epsilon_2,\delta_2)\)-dp 的,则 \(M:\mathcal{X}^n\to R^n\)\((\epsilon_1+\epsilon_2,\delta_1+\delta_2)\)-marginal dp 的. 其中: \[M(\mathbf{x})=\left(M_{j}^{2}\left(\mathbf{x}_{-j}, x_{j}, M^{1}(\mathbf{x})\right)\right)_{j=1}^{n}.\]

定理 4.14\(\epsilon,\delta_1,\delta_2,\beta>0\),PTTC: \(\mathcal{X}^n\to\mathcal{G}^n\) 提供 \((\epsilon,\delta_1+\delta_2+\beta)\)-marginal dp.

ALLOWING A SMALL SUPPLY OF GOODS TO BE INJECTED

抛开隐私性的限制,也不使用 TTC 算法,我们可以通过解如下问题来获得 IR 且 PO 的 exchange: \[\begin{aligned} &\max _{z}~~\sum_{i \in[n]} \sum_{ j \in \mathcal{G}} r_{i j} z_{i j}\\ &\text { s.t. } \quad \sum_{j \in \mathcal{G}} z_{i j}=n_{j} \quad \forall i \in[n]\\ &\qquad~~~ \forall j \in \mathcal{G} \text { s.t. } g_{i}>_{i} j \quad z_{i, j}=0 \quad \forall i \in[n] \\ &\qquad~~~ \sum_{i \in[n]} z_{i j}=1 \quad \forall j \in G \\ &\qquad~~~ z_{i j} \in\{0,1\} \end{aligned}\] 其中:

  • \(j\succeq_i g_i\)\(j\)\(i\) 的第 \(r\) 选择,则 \(r_{ij}=k-r+1\).
  • \(g_i\succ_i j\),则 \(w_{ij}=0\).

定理 5.1 上述约束问题的解是 IR 且 PO 的.

证明: 由第二个约束条件,每个人都不会选择比自己初始拥有的物品辣鸡的物品来交换,因此是 IR 的. 另一方面,如果上述规划问题的一个解存在 Pareto 改进,将破坏该规划问题的最优性,因此是 PO 的.

接下来作者改进了 Justin Hsu 在 2014 年的工作,获得了渐进PO,IR 且满足 Joint-dp 的分配,但需要允许我们注入一些额外的物品.

定理 5.3 在 exchange markets 中,存在满足 \((\epsilon, \delta)\) Joint-dp 的分配机制,使得导出的分配至少有 \(1-\beta\) 的概率满足 \(\alpha\)-PO 且总是 IR 的, 但可能需要 \(\Lambda\) 个额外的物品,以使得每个人都至少得到一个物品,其中:

\[ \alpha=O\left(\frac{k^{2} \log ^{3 / 2}(n k / \beta) \log ^{1 / 2}(n / \delta)}{\sqrt{n} \epsilon}\right) \quad \text { and } \quad \Lambda=O\left(\frac{k \sqrt{n} \log ^{3 / 2}(n k / \beta) \log ^{1 / 2}(n / \delta)}{\epsilon}\right) \]