Paper Outline：Frank McSherry, Kunal Talwar. Mechanism design via differential privacy. FOCS 2007.
Something about dp
- Approximate Truthfulness
引理 3. 对 \(\forall\) 满足\(\epsilon\)-dp 的机制 $，以及定义在其作用域上的非负函数 \(g\). 对 \(\forall D_1,D_2\) 的输入, s.t. \(|D_1\triangle D_2|=1\)，均有： \[E\left[g\left(\mathcal{M}\left(D_{1}\right)\right)\right] \leq \exp (\epsilon) \times E\left[g\left(\mathcal{M}\left(D_{2}\right)\right)\right]\]
- Collusion Resistance
推论 4. 对任意 \(\epsilon\)-dp 的机制 \(\mathcal{M}\) 以及定义在其作用域上的非负函数 \(g\)，对 \(\forall D_1,D_2\)，s.t. \(|D_1\triangle D_2|\leqslant t\)，总有： \[E\left[g\left(\mathcal{M}\left(D_{1}\right)\right)\right] \leq \exp (\epsilon t) \times E\left[g\left(\mathcal{M}\left(D_{2}\right)\right)\right]\]
- Composability
就是 dp 的结合方法，串行进程 \(\epsilon\) 相加.
A General dp Mechanism
- domain: \(\mathcal{D}\)，range: \(\mathcal{R}\)
- query function：\(q:\mathcal{D}^n\times \mathcal{R}\to\mathbb{R}\)，是对
(input, output)二元组的估值，\(q\) 越大，二者越匹配.
给定 \(d\in\mathcal{D}^n\)，我们希望给出一个机制，其输出为 \(r\in\mathcal{R}\)，s.t. \(q(d,r)\) 最大.
定义 对于 \(\forall q:\mathcal{D}^n\times\mathcal{R}\to\mathbb{R}\)，以及 \(\mathcal{R}\) 上的一个测度，定义： \[\mathcal{E}_{q}^{\epsilon}(d):=~\text{Choose}~r~\text{with probability proportional to}~\exp (\epsilon q(d, r)) \times \mu(r)\]
隐私性
定理 6. \(\mathcal{E}^\epsilon_q\) 提供 \((2\epsilon\triangle q)\)-dp 保护.
准确性
- 令 \(\mu(A)\) 为 \(A\subseteq\mathcal{R}\) 的测度，且 \(\mu(\mathcal{R})=1\)；
- 令 \(p(A)\) 为 \(\mathcal{E}_q^\epsilon(d)\) 所定义的测度（同样也进行正则化）；
- 令 \(OPT=\max_r q(d,r)\).
引理 7. 令 \(S_t\{r: q(d,r)>OPT-t\}\)，则 \(p(\bar{S}_{2t})\) 至多为 \(\exp(\epsilon t)/\mu(S_t)\).
进一步，有如下的结果：
定理 8. 若 \(t\) 满足 \(t \geq\) \(\ln \left(O P T / t \mu\left(S_{t}\right)\right) / \epsilon,\) 则有 \(E\left[q\left(d, \mathcal{E}_{q}^{\epsilon}(d)\right)\right] \geq O P T-3 t\)
Applications to Pricing and Auctions
本节将 gneral mechanism 应用于无限供给拍卖. 本节所有的机制都是 single price，且 envy-free 的.
考虑一个物品无限量供给的拍卖会：
- 每个参与者都有一个需求函数 \(b_i:[0,1]\to\mathbb{R}^+\)，表示在定价为 \(p\in[0,1]\) 时该参与者对物品的需求量；
- 为符合常理，每一个 \(b_i\) 都是不增的，且 \(\forall i,p\)，\(pb_i(p)\leqslant 1\)；
- 对 \(\forall\) 价格 \(p\)，我们可以卖掉 \(\sum_i b_i(p)\) 件商品，取总收益为 \(q(b,p)=p\sum_i b_i(p)\).
定理 9. 取 \(q(b, p)=p \sum_{i} b_{i}(p),\) 则 \(\mathcal{E}_{q}^{\epsilon}\) 满足 \(2 \epsilon\)-dp, 且期望收益至少为 \(O P T-3 \ln \left(e+\epsilon^{2} O P T m\right) / \epsilon,\)，其中 \(m\) 为 \(OPT\) 情形下卖掉的商品数.
General mechanism 还可以推广到 attribute auctions.
所谓 attribute auction，是指在拍卖的基础上考虑竞拍者的属性，将市场进行细分，为不同的人提供不同的价格，以获得更高预期收入的一种拍卖方式.
- 用 \(OPT_k\) 表示分割为 \(k\) 部分的市场的最大收入；
- 用 \(SEG_k\) 表示 \(n\) 个竞拍者进入 \(k\) 个市场时被允许划分的部分数；
- 有结果表明 \(SEG_k\leqslant n^{kVC}\).
定理 10. 令 \(q\) 为将市场分割为 \(k\) 个部分的收益函数, 则 \(\mathcal{E}_{q}^{\epsilon}\) 的预期收益至少为 \[O P T_{k}-3(\ln (e+\left.\left.\epsilon^{k+1} O P T_{k} S E G_{k} m^{k}\right)\right) / \epsilon.\]
以下是一个看不懂的结果…
考虑一个约束定价问题：
这是多参数问题的一个特例，即竞拍人对 \(k\) 种不同的物品中的每一种都有一个出价，并且拍卖只能以固定价格出售最多一种物品.
- 每个 \(i\) 对物品 \(j\in[k]\) 有一个需求函数 \(b_i^j:[0,1]\to\mathbb{R}^+\)；
- 须对 \(\forall i,j,p\) 确保 \(pb_i^j(p)\leqslant 1\).
- \(\mathcal{R}=[k]\times\mathbb{R}\)；
- 对物品 \(j\)，价格为 \(p\)，可以卖掉 \(\sum_i b_i^j(p)\) 件，得到 \(q(b,(j,p))=p\sum_i b_i^j(p)\) 的收入.
定理 12. 令 \(q(b,(j, p))=p \sum_{i} b_{i}^{j}(p), \mathcal{E}_{q}^{\epsilon}\) 满足 \(2\epsilon\)-dp, 且预期收益至少为 \(O P T-3 \ln \left(e+\epsilon^{2} O P T k m\right) / \epsilon,\) 其中 \(m\) 为 \(OPT\) 情形下卖掉的商品数.