论文笔记[13]——Mechanism design via differential privacy

Frank McSherry, Kunal Talwar. Mechanism design via differential privacy. FOCS 2007.

Paper Outline:

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\) 情形下卖掉的商品数.