龙岩天宫山攻略_海南网站seo_希爱力双效片骗局_南昌百度搜索排名优化

由于GitHub项目仅翻译到前5章，我们从第6章开始通过大语言模型翻译，并导出markdown格式。
大模型难免存在错漏，请读者指正。

教材原文地址：https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf

在这里插入图片描述

10 差分隐私与机制设计

博弈论中最引人入胜的领域之一是机制设计（mechanism design），它是一门设计激励措施以促使人们按你期望的方式行事的科学。差分隐私已被证明在几个意想不到的方面与机制设计有着有趣的联系。它提供了一种量化和控制隐私损失的工具，如果机制设计者试图操纵的人关心隐私，这一点很重要。然而，它还提供了一种限制机制结果对任何单个个体选择的敏感性的方法，事实证明，即使在没有隐私问题的情况下，这也是一种强大的工具。在本节中，我们简要概述其中一些观点。

机制设计是指当算法的输入由个体的、自利的参与者控制，而不是由算法设计者自己控制时的算法设计问题。该算法将其接收到的输入映射到某个结果，参与者对这些结果有偏好。困难在于，如果参与者误报数据能使算法输出一个不同的、更偏好的结果，他们可能会这样做，因此机制设计者必须设计算法，使参与者始终有动机报告他们的真实数据。

机制设计的关注点与隐私算法设计的关注点非常相似。在这两种情况下，算法的输入都被认为属于某个对结果有偏好的第三方 ${}^{1}$ 。在机制设计中，我们通常认为个体从机制的结果中获得一些明确的价值。在隐私算法设计中，我们通常认为个体因机制结果（的后果）而遭受一些明确的损害。实际上，我们可以给出一个与标准定义等价的差分隐私的效用理论定义，但它明确了与个体效用的联系：

定义10.1。如果对于每个函数 $\rightarrow {\mathbb{R}}_{ + }$ ，以及每对相邻数据库 $\in {\mathbb{N}}^{\left| \mathcal{X}\right| }$ ，算法 ${\mathbb{N}}^{\left| \mathcal{X}\right| } \rightarrow R$ 满足 $\epsilon$ -差分隐私：

$\exp \left( {-\epsilon }\right) {\mathbb{E}}_{z \sim A\left( y\right) }\left\lbrack {f\left( z\right) }\right\rbrack \leq {\mathbb{E}}_{z \sim A\left( x\right) }\left\lbrack {f\left( z\right) }\right\rbrack \leq \exp \left( \epsilon \right) {\mathbb{E}}_{z \sim A\left( y\right) }\left\lbrack {f\left( z\right) }\right\rbrack .$

我们可以将 $f$ 视为一个将结果映射到任意主体对这些结果的效用的函数。根据这种解释，如果一个机制对于每个主体都承诺，无论其效用函数是什么，他们参与该机制对其预期未来效用的影响不会超过 $\exp \left( \epsilon \right)$ 倍，那么该机制就是 $\epsilon$ -差分隐私的。

现在让我们简要定义一下机制设计中的一个问题。一个机制设计问题由几个要素定义。有 $n$ 个主体 $\in \left\lbrack n\right\rbrack$ ，以及一组结果 $\mathcal{O}$ 。每个主体都有一个类型 ${t}_{i} \in \mathcal{T}$ ，该类型只有她自己知道，并且存在一个关于结果的效用函数 $\mathcal{T} \times \mathcal{O} \rightarrow \left\lbrack {0,1}\right\rbrack$ 。主体 $i$ 从结果 $\in \mathcal{O}$ 中获得的效用是 $u\left( {{t}_{i},o}\right)$ ，我们通常将其缩写为 ${u}_{i}\left( o\right)$ 。我们将用 $\in {\mathcal{T}}^{n}$ 表示所有 $n$ 个主体类型的向量，其中 ${t}_{i}$ 表示主体 $i$ 的类型， ${t}_{-i} \equiv \left( {{t}_{1},\ldots ,{t}_{i - 1},{t}_{i + 1},\ldots ,{t}_{n}}\right)$ 表示除主体 $i$ 之外所有主体的类型向量。主体 $i$ 的类型完全决定了她对结果的效用——也就是说，两个主体 $\neq j$ ，如果 ${t}_{i} = {t}_{j}$ ，那么他们对每个结果的评估将相同：对于所有的 $\in \mathcal{O}$ ，都有 ${u}_{i}\left( o\right) = {u}_{j}\left( o\right)$ 。

${}^{1}$ 在隐私设置中，数据库管理员（如医院）可能已经可以访问数据本身，但在努力保护隐私时，仍然会采取行动来保护数据所有者的利益。

机制 $M$ 以一组报告的类型作为输入，每个参与者提供一个类型，并选择一个结果。也就是说，机制是一个映射 ${\mathcal{T}}^{n} \rightarrow \mathcal{O}$ 。参与者会策略性地选择报告他们的类型，以优化自己的效用，可能会考虑（他们认为）其他参与者会怎么做。特别是，他们不必向机制报告自己的真实类型。如果无论对手报告什么类型，一个参与者总是有动机报告某个类型，那么报告该类型就被称为占优策略。如果对于每个参与者来说，报告自己的真实类型是占优策略，那么该机制就被称为诚实的，或者等价地，占优策略诚实的。

定义10.2。给定一个机制 ${\mathcal{T}}^{n} \rightarrow \mathcal{O}$ ，如果对于每对类型 ${t}_{i},{t}_{i}^{\prime } \in T$ ，以及每个类型向量 ${t}_{-i}$ ，如实报告是参与者 $i$ 的 $\epsilon$ -近似占优策略：

$u\left( {{t}_{i},M\left( {{t}_{i},{t}_{-i}}\right) }\right) \geq u\left( {{t}_{i},M\left( {{t}_{i}^{\prime },{t}_{-i}}\right) }\right) - \epsilon .$

如果如实报告是每个参与者的 $\epsilon$ -近似占优策略，我们就说 $M$ 是 $\epsilon$ -近似占优策略诚实的。如果 $\epsilon = 0$ ，那么 $M$ 就是完全诚实的。

也就是说，如果无论其他参与者报告什么，没有主体可以通过歪曲自己的类型来提高自己的效用，那么该机制就是诚实的。

在这里，我们可以立即观察到与差分隐私定义的句法联系。我们可以将类型空间 $T$ 与数据全域 $X$ 等同起来。因此，该机制的输入由一个大小为 $n$ 的数据库组成，该数据库包含每个参与者的报告。事实上，当一个参与者考虑她是应该如实报告自己的类型 ${t}_{i}$ 还是说谎并误报为类型 ${t}_{i}^{\prime }$ 时，她是在决定该机制应该接收两个数据库中的哪一个： $\left( {{t}_{1},\ldots ,{t}_{n}}\right)$ 或 $\left( {{t}_{1},\ldots ,{t}_{i - 1},{t}_{i}^{\prime },{t}_{i + 1},\ldots ,{t}_{n}}\right)$ 。请注意，这两个数据库仅在参与者 $i$ 的报告上有所不同！也就是说，它们是相邻数据库。因此，差分隐私提供了近似真实性的保证！

10.1 差分隐私作为一种解决方案概念

研究差分隐私与博弈论之间联系的起点之一是观察到差分隐私是比近似真实性更强的条件。注意到对于 $\epsilon \leq 1,\exp \left( \epsilon \right) \leq 1 + {2\epsilon }$ ，因此以下命题是显而易见的。

命题10.1。如果一个机制 $M$ 是 $\epsilon$ - 差分隐私的，那么 $M$ 也是 ${2\epsilon }$ - 近似占优策略真实的。

作为一种解决方案概念，它具有一些策略防操纵机制所不具备的鲁棒性属性。根据差分隐私的组合性质， ${2\epsilon }$ - 差分隐私机制的组合仍然是 ${4\epsilon }$ - 近似占优策略真实的。相比之下，一般策略防操纵机制的激励属性在组合下可能无法保留。

差分隐私作为一种解决方案概念的另一个有用属性是它可以推广到群体隐私：假设 $t$ 和 ${t}^{\prime } \in$ ${\mathcal{T}}^{n}$ 不是相邻的，而是在 $k$ 个索引上有所不同。回想一下，根据群体隐私，对于任何参与者 ${\mathbb{E}}_{o \sim M\left( t\right) }\left\lbrack {{u}_{i}\left( o\right) }\right\rbrack \leq$ $\exp \left( {k\epsilon }\right) {\mathbb{E}}_{o \sim M\left( {t}^{\prime }\right) }\left\lbrack {{u}_{i}\left( o\right) }\right\rbrack$ 。也就是说，当 $\ll 1/\epsilon$ 时，最多 $k$ 种类型的变化最多使期望输出改变 $\approx \left( {1 + {k\epsilon }}\right)$ 。因此，差分隐私机制使如实报告成为即使对于 $k$ 个参与者的联盟也是 ${2k\epsilon }$ - 近似占优策略——即，差分隐私自动提供了对合谋的鲁棒性。同样，这与一般的占优策略真实机制形成对比，一般的占优策略真实机制通常不提供防止合谋的保证。

值得注意的是，差分隐私在非常一般的设置中无需使用货币就能实现这些属性！相比之下，在不允许货币转移的情况下，精确占优策略真实机制的集合非常有限。

最后，我们指出将差分隐私作为一种解决方案概念存在的一个缺点：如实报告自己的类型不仅是一种近似占优策略，任何报告都是近似占优策略！也就是说，差分隐私使得结果近似独立于任何单个参与者的报告。在某些情况下，这个缺点可以得到缓解。例如，假设 $M$ 是一个差分隐私机制，但参与者的效用函数被定义为机制结果和参与者报告类型 ${t}_{i}^{\prime }$ 的函数：形式上，我们将结果空间视为 ${\mathcal{O}}^{\prime } = \mathcal{O} \times T$ 。当参与者向机制报告类型 ${t}_{i}^{\prime }$ ，并且机制选择结果 $\in \mathcal{O}$ 时，参与者所体验到的效用由结果 ${o}^{\prime } = \left( {o,{t}_{i}^{\prime }}\right)$ 控制。现在考虑底层效用函数 $\times {\mathcal{O}}^{\prime } \rightarrow \left\lbrack {0,1}\right\rbrack$ 。假设我们固定机制的一个选择 $o$ ，如实报告是一种占优策略——也就是说，对于所有类型 ${t}_{i},{t}_{i}^{\prime }$ ，以及所有结果 $\in \mathcal{O}$ ：

$u\left( {{t}_{i},\left( {o,{t}_{i}}\right) }\right) \geq u\left( {{t}_{i},\left( {o,{t}_{i}^{\prime }}\right) }\right) .$

那么，向一个 $\epsilon$ - 差分隐私机制 ${T}^{n} \rightarrow \mathcal{O}$ 如实报告仍然是一种 ${2\epsilon }$ 近似占优策略，因为对于参与者 $i$ 可能考虑的任何虚假报告 ${t}_{i}^{\prime }$ ，我们有：

$u\left( {{t}_{i},\left( {M\left( t\right) ,{t}_{i}}\right) }\right) = {\mathbb{E}}_{o \sim M\left( t\right) }\left\lbrack {u\left( {{t}_{i},\left( {o,{t}_{i}}\right) }\right) }\right\rbrack$

$\geq \left( {1 + {2\epsilon }}\right) {\mathbb{E}}_{o \sim M\left( {{t}_{i}^{\prime },{t}_{-i}}\right) }\left\lbrack {u\left( {{t}_{i},\left( {o,{t}_{i}}\right) }\right) }\right\rbrack$

$\geq {\mathbb{E}}_{o \sim M\left( {{t}_{i}^{\prime },{t}_{-i}}\right) }\left\lbrack {u\left( {{t}_{i},\left( {o,{t}_{i}^{\prime }}\right) }\right) }\right\rbrack$

$u\left( {{t}_{i},\left( {M\left( {{t}_{i}^{\prime },{t}_{-i}}\right) ,{t}_{i}^{\prime }}\right) }\right) \text{.}$

然而，我们不再有“每个报告都是近似占优策略”这一情况，因为参与者 $i$ 的效用可以任意依赖于 ${o}^{\prime } = \left( {o,{t}_{i}^{\prime }}\right)$ ，并且只有 $o$ （而不是参与者 $i$ 的报告 ${t}_{i}^{\prime }$ 本身）是差分隐私的。我们在这里考虑的所有例子都会是这种情况。

10.2 差分隐私作为机制设计的工具

在本节中，我们将展示如何将差分隐私的方法作为一种工具来设计新颖的机制。

10.2.1 热身：数字商品拍卖

作为热身，让我们考虑差分隐私在机制设计中首次应用的一个简单特殊情况。考虑一场数字商品拍卖，即卖家拥有一种商品的无限供应，且生产的边际成本为零，例如一款软件或其他数字媒体。有 $n$ 个对该商品有单位需求的买家，每个买家的估值 ${v}_{i} \in \left\lbrack {0,1}\right\rbrack$ 未知。通俗地说，投标人 $i$ 的估值 ${v}_{i}$ 代表买家 $i$ 愿意为该商品支付的最高金额。投标人的估值没有先验分布，因此一个自然的收入基准是最优固定价格的收入。在价格 $\in \left\lbrack {0,1}\right\rbrack$ 下，每个 ${v}_{i} \geq p$ 的投标人 $i$ 都会购买。因此，拍卖人的总收入为

$\operatorname{Rev}\left( {p,v}\right) = p \cdot \left| \left\{ {i : {v}_{i} \geq p}\right\} \right| .$

最优收入是最优固定价格的收入： $\mathrm{{OPT}} =$ $\mathop{\max }\limits_{p}\operatorname{Rev}\left( {p,v}\right)$ 。这种情况已经得到了深入研究：对于精确占优策略如实机制，已知的最佳结果是一个能实现至少 $\mathrm{{OPT}} - O\left( \sqrt{n}\right)$ 收入的机制。

我们展示了指数机制的一个简单应用如何实现至少 $\mathrm{{OPT}} - O\left( \frac{\log n}{\epsilon }\right)$ 的收入。也就是说，该机制用精确性换取近似如实性，但实现了指数级更好的收入保证。当然，它也继承了前面讨论过的差分隐私的优点，如抗合谋性和可组合性。

思路是从指数机制中选择一个价格，将该价格所能获得的收入作为我们的“质量得分”。假设我们将指数机制的取值范围设定为 $\mathcal{R} = \{ \alpha ,{2\alpha },\ldots ,1\}$ 。该范围的大小为 $\left| \mathcal{R}\right| = 1/\alpha$ 。如果我们将价格选择范围限制在 $\mathcal{R}$ 内，我们在潜在收入方面损失了多少呢？不难看出

${\mathrm{{OPT}}}_{\mathcal{R}} \equiv \mathop{\max }\limits_{{p \in \mathcal{R}}}\operatorname{Rev}\left( {p,v}\right) \geq \mathrm{{OPT}} - {\alpha n}.$

这是因为，如果 ${p}^{ * }$ 是实现最优收入的价格，而我们使用的价格为 $p$ ，且满足 ${p}^{ * } - \alpha \leq p \leq {p}^{ * }$ ，那么在最优价格下购买的每个买家都会继续购买，并且每个买家给我们带来的收入最多减少 $\alpha$ 。由于最多有 $n$ 个买家，因此总损失收入最多为 ${\alpha n}$ 。

那么我们如何对指数机制进行参数化呢？我们有一族离散范围 $\mathcal{R}$ ，由 $\alpha$ 参数化。对于一个值向量 $v$ 和一个价格 $\in \mathcal{R}$ ，我们将质量函数定义为 $q\left( {v,p}\right) =$ $\operatorname{Rev}\left( {v,p}\right)$ 。注意，由于每个值 ${v}_{i} \in \left\lbrack {0,1}\right\rbrack$ ，我们可以将注意力限制在价格 $\leq 1$ 上，因此， $q$ 的敏感度为 $\Delta = 1$ ：改变一个投标者的估值最多只能使固定价格下的收益改变 ${v}_{i} \leq 1$ 。因此，如果我们要求 $\epsilon$ - 差分隐私，根据定理3.11，我们可以得到，在高概率下，指数机制会返回某个价格 $p$ ，使得

$\operatorname{Rev}\left( {p,v}\right) \geq \left( {\mathrm{{OPT}} - {\alpha n}}\right) - O\left( {\frac{1}{\epsilon }\ln \left( \frac{1}{\alpha }\right) }\right) .$

选择我们的离散化参数 $\alpha$ 来最小化两种误差来源，我们发现这个机制在高概率下能为我们找到一个实现收益的价格

$\operatorname{Rev}\left( {p,v}\right) \geq \mathrm{{OPT}} - O\left( \frac{\log n}{\epsilon }\right) .$

隐私参数 $\epsilon$ 应该选择什么合适的水平呢？请注意，在这里，我们并不一定将隐私本身视为计算的目标。相反， $\epsilon$ 是一种在收益保证和代理人偏离激励上限之间进行权衡的方式。在经济学中关于大市场的文献里，当无法实现精确的真实性时，一个常见的目标是“渐近真实性”——也就是说，随着市场规模 $n$ 的增大，任何代理人偏离其真实报告的最大激励趋于0。为了在这里实现类似的结果，我们所需要做的就是将 $\epsilon$ 设为代理人数量 $n$ 的某个递减函数。例如，如果我们取 $\epsilon = 1/\log \left( n\right)$ ，那么我们就得到了一个渐近精确真实的机制（即，随着市场规模增大，对真实性的近似变得精确）。我们还可以问，随着 $n$ 的增大，我们对最优收益的近似程度如何。请注意，我们对最优收益的近似只是加法性的，因此，即使在这样设置 $\epsilon$ 的情况下，只要 $\mathrm{{OPT}}$ 随着人口规模 $n$ 的增长比 $\log {\left( n\right) }^{2}$ 增长得更快，我们仍然可以保证至少有 $\left( {1 - o\left( 1\right) }\right) \mathrm{{OPT}}$ 的收益。

最后，注意我们可以使每个代理人 $i$ 的报告值 ${v}_{i}$ 具有约束力。换句话说，只要 ${v}_{i} \geq p$ ，我们就可以将一个物品分配给代理人 $i$ ，并按照所选的张贴价格 $p$ 收取费用。如果我们这样做，该机制是近似真实的，因为价格是使用差分隐私机制选取的。此外，并非每个报告都是近似占优策略：如果一个代理人高报，她可能会被迫以高于其真实价值的价格购买商品。

10.2.2 近似真实的均衡选择机制

我们现在考虑近似真实的均衡选择问题。我们回顾一下纳什均衡的定义：假设每个玩家都有一组行动 $\mathcal{A}$ ，并且可以选择执行任何行动 ${a}_{i} \in \mathcal{A}$ 。此外，假设结果仅仅是代理人可能选择执行的行动选择，因此代理人的效用函数定义为 $\mathcal{T} \times {\mathcal{A}}^{n} \rightarrow \left\lbrack {0,1}\right\rbrack$ 。那么：

定义10.3。一组行动 $\in {\mathcal{A}}^{n}$ 是一个 $\epsilon$ - 近似纳什均衡，如果对于所有玩家 $i$ 和所有行动 ${a}_{i}^{\prime }$ ：

${u}_{i}\left( a\right) \geq {u}_{i}\left( {{a}_{i}^{\prime },{a}_{-i}}\right) - \epsilon$

换句话说，假设其他代理人按照 $a$ 行动，那么每个代理人同时都在对其他代理人的行为做出（近似）最优反应。

大致来说，问题如下：假设我们有一个博弈，其中每个玩家都知道自己的收益，但不知道其他玩家的收益（即玩家不知道其他参与者的类型）。因此，玩家们不知道这个博弈的均衡结构。即使他们知道，也可能存在多个均衡，不同的参与者偏好不同的均衡。中介提供的机制能否激励参与者如实报告他们的效用并遵循其选择的均衡呢？

例如，想象一个城市，其中（比如说）谷歌导航是占主导地位的服务。每天早上，每个人输入他们的起点和目的地，收到一组路线指引，并根据这些指引选择自己的路线。是否有可能设计一种导航服务，使得：每个参与者都受到激励，既（1）如实报告，又（2）遵循所提供的驾驶路线？虚报起点和终点，以及如实报告起点和终点但随后选择不同（更短）的路线都应受到抑制。

直观地说，我们的两个期望目标存在冲突。在上述通勤示例中，如果我们要保证每个玩家都受到激励如实遵循建议的路线，那么我们必须根据玩家的报告计算所讨论博弈的一个均衡。另一方面，要做到这一点，我们给某个玩家 $i$ 的建议路线必须依赖于其他玩家报告的位置/目的地对。这种矛盾在激励方面会带来问题：如果我们根据玩家的报告计算博弈的一个均衡，那么一个参与者可能会通过虚报而获益，导致我们计算出错误博弈的均衡。

然而，如果参与者 $i$ 的报告对参与者 $\neq i$ 的行动只有微小的影响，那么这个问题将在很大程度上得到缓解。在这种情况下，参与者 $i$ 很难通过对其他玩家的影响获得优势。然后，假设每个人都如实报告了他们的类型，该机制将计算出正确博弈的一个均衡，根据定义，每个参与者 $i$ 遵循建议的均衡行动就是最优选择。换句话说，如果我们能在差分隐私的约束下计算出博弈的一个近似均衡，那么如实报告，然后采取协调设备建议的行动将是一个纳什均衡。稍加思考就会发现，在小型博弈中，私下计算均衡的目标是不可能实现的，因为在小型博弈中，一个参与者的效用是其他参与者行动（以及效用函数）的高度敏感函数。但在大型博弈中情况如何呢？

形式上，假设我们有一个 $n$ 个玩家的博弈，其行动集为 $\mathcal{A}$ ，每个类型为 ${t}_{i}$ 的参与者都有一个效用函数 ${u}_{i} : {\mathcal{A}}^{n} \rightarrow \left\lbrack {0,1}\right\rbrack$ 。我们称这个博弈是 $\Delta$ - 大型的，如果对于所有玩家 $\neq j$ 、行动向量 $\in {\mathcal{A}}^{n}$ 和行动对 ${a}_{j},{a}_{j}^{\prime } \in \mathcal{A}$ ：

$\left| {{u}_{i}\left( {{a}_{j},{a}_{-j}}\right) - {u}_{i}\left( {{a}_{j}^{\prime },{a}_{-j}}\right) }\right| \leq \Delta .$

换句话说，如果某个参与者 $j$ 单方面改变他的行动，那么他对任何其他参与者 $\neq j$ 的收益的影响至多为 $\Delta$ 。请注意，如果参与者 $j$ 改变他自己的行动，那么他的收益可能会任意改变。从这个意义上说，许多博弈都是“大型”的。在上述通勤示例中，如果爱丽丝改变她的上班路线，她可能会大幅增加或减少自己的通勤时间，但对任何其他参与者鲍勃的通勤时间只会有极小的影响。本节的结果在 $\Delta = O\left( {1/n}\right)$ 的情况下最强，但更普遍地也成立。

首先，我们可能会问，我们是否根本就需要隐私——在一个大规模博弈中，任何根据所报告的类型计算博弈均衡的算法，是否都具有我们所期望的稳定性呢？答案是否定的。举一个简单的例子，假设有 $n$ 个人，每个人都必须选择去海滩（B）还是去山区（M）。人们私下了解自己的类型——每个人的效用取决于他自己的类型、他的行动，以及去海滩的其他人的比例 $p$ 。海滩型的人如果去海滩，会得到 ${10p}$ 的收益；如果去山区，则会得到 $5\left( {1 - p}\right)$ 的收益。山区型的人去海滩会得到 ${5p}$ 的收益，去山区会得到 ${10}\left( {1 - p}\right)$ 的收益。请注意，这是一个大规模（即低敏感度）的博弈——每个玩家的收益对其他玩家的行动不敏感。此外，无论类型的实际情况如何，“每个人都去海滩”和“每个人都去山区”都是该博弈的均衡。考虑这样一种机制，它试图实现以下社会选择规则——“如果海滩型的人数少于总人数的一半，就把所有人送到海滩，反之亦然”。显然，如果山区型的人占多数，那么每个山区型的人都有动机谎报为海滩型；反之亦然。因此，即使这个博弈是“大规模”的，并且参与者的行动不会显著影响其他参与者的收益，但仅仅根据所报告的类型配置计算均衡，一般来说并不能产生近似真实的机制。

然而，事实证明，可以给出一种具有以下性质的机制：它获取每个参与者的类型 ${t}_{i}$ ，然后计算由所报告的类型定义的博弈的 $\alpha$ - 近似相关均衡（在某些情况下，可以将这一结果加强为计算基础博弈的近似纳什均衡）。它从相关均衡中抽取一个行动配置 $\in {\mathcal{A}}^{n}$ ，并向每个参与者 $i$ 报告行动 ${a}_{i}$ 。该算法保证，对于所有参与者 $i$ ，除 $i$ 之外的所有参与者的报告的联合分布 ${a}_{-i}$ 在参与者 $i$ 所报告的类型上是差分隐私的。当算法计算基础博弈的相关均衡时，这一保证足以实现一种受限形式的近似真实性：有选择加入或退出该机制（但如果选择加入则不能谎报其类型）的参与者没有退出的动机，因为没有参与者 $i$ 可以通过退出显著改变其他参与者的行动分布。此外，鉴于他选择加入，没有参与者有动机不遵循他所得到的建议行动，因为他的建议是相关均衡的一部分。当该机制计算基础博弈的纳什均衡时，那么即使参与者在选择加入时能够向机制谎报其类型，该机制也是真实的。

${}^{2}$ 相关均衡是由行动配置的联合分布 ${\mathcal{A}}^{n}$ 定义的。对于从该分布中抽取的一个行动配置 $a$ ，如果只告诉参与者 $i$ 行动 ${a}_{i}$ ，那么在给定 ${a}_{-i}$ 的条件分布下，采取行动 ${a}_{i}$ 是最优反应。 $\alpha$ - 近似相关均衡是指偏离该均衡最多能使参与者的效用提高 $\alpha$ 。

更具体地说，当这些机制在满足 $\epsilon$ - 差分隐私的同时计算出一个 $\alpha$ - 近似纳什均衡时，每个遵循诚实行为（即，首先选择参与并报告其真实类型，然后遵循建议的行动）的参与者都会形成一个 $\left( {{2\epsilon } + \alpha }\right)$ - 近似纳什均衡。这是因为，从隐私角度来看，报告你的真实类型是一种 ${2\epsilon }$ - 近似占优策略，并且假设每个人都报告了他们的真实类型，该机制会计算出真实博弈的一个 $\alpha$ - 近似均衡，因此根据定义，遵循建议的行动是一种 $\alpha$ - 近似最优反应。存在一些机制可用于计算具有 $\alpha = O\left( \frac{1}{\sqrt{n}\epsilon }\right)$ 的大型博弈中的 $\alpha$ - 近似均衡。因此，通过设置 $\epsilon = O\left( \frac{1}{{n}^{1/4}}\right)$ ，这为……提供了一种 $\eta$ - 近似真实的均衡选择机制

$\eta = {2\epsilon } + \alpha = O\left( \frac{1}{{n}^{1/4}}\right) .$

换句话说，它为大型博弈中的均衡行为协调提供了一种机制，该机制在博弈规模上渐近真实，而且无需货币转移。

10.2.3 实现精确真实性

到目前为止，我们已经讨论了在大规模群体博弈中渐近真实的机制。然而，如果我们坚持要使用精确占优策略真实的机制，同时保留我们目前所讨论机制的一些优良特性，例如，这些机制不需要能够提取货币支付，该怎么办呢？差分隐私能在此发挥作用吗？答案是肯定的——在本节中，我们将讨论一个框架，该框架将差分隐私机制作为构建模块，用于设计无需货币的精确真实机制。

基本思路简单而优雅。正如我们所见，指数机制在保留差分隐私的同时，通常能提供出色的效用保证。这虽然不能产生一个精确真实的机制，但它让每个参与者几乎没有动机偏离真实行为。如果我们能将其与第二种机制结合起来会怎样呢？第二种机制不一定需要有良好的效用保证，但能给每个参与者一个严格的正向激励来如实报告，即一种本质上只惩罚非真实行为的机制。然后，我们可以在运行这两种机制之间进行随机选择。如果我们对惩罚机制赋予足够的权重，那么我们就能继承其严格真实性的特性。分配给指数机制的剩余权重则有助于最终机制的效用特性。我们希望，由于指数机制一开始就近似策略无懈可击，随机化机制可以对严格真实的惩罚机制赋予较小的权重，从而具有良好的效用特性。

为了设计惩罚机制，我们必须在一个稍微非标准的环境中进行工作。我们可以将机制建模为不仅选择一个结果，然后让参与者选择对该结果的反应，这两者共同决定了他的效用，而不是简单地选择一个结果。然后，机制将有权根据参与者报告的类型限制其允许的反应。形式上，我们将在以下框架中进行工作：

定义10.4（环境）。一个环境是一个包含 $n$ 个参与者的集合 $N$ 、一个类型集合 ${t}_{i} \in \mathcal{T}$ 、一个有限的结果集合 $\mathcal{O}$ 、一个反应集合 $R$ 和一个效用函数 $\times \mathcal{O} \times R \rightarrow \left\lbrack {0,1}\right\rbrack$ 。

我们用 ${r}_{i}\left( {t,s,{\widehat{R}}_{i}}\right) \in \arg \mathop{\max }\limits_{{r \in {\widehat{R}}_{i}}}{u}_{i}\left( {t,s,r}\right)$ 来表示，如果 $i$ 属于类型 $t$ ，他在对备选方案 $s$ 的选择 ${\widehat{R}}_{i} \subseteq R$ 中的最优反应。

一个直接揭示机制 $\mathcal{M}$ 定义了一个按如下方式进行的博弈：

每个参与者 $i$ 报告一个类型 ${t}_{i}^{\prime } \in \mathcal{T}$ 。
该机制为每个参与者 $i$ 选择一个备选方案 $\in \mathcal{O}$ 和一个反应子集 ${\widehat{R}}_{i} \subseteq R$ 。
每个参与者 $i$ 选择一个反应 ${r}_{i} \in {\widehat{R}}_{i}$ 并获得效用 $u\left( {{t}_{i},s,{r}_{i}}\right)$ 。

参与者会采取行动以最大化自身效用。注意，由于在第三步之后没有进一步的交互，理性的参与者会选择 ${r}_{i} = {r}_{i}\left( {{t}_{i},s,{\widehat{R}}_{i}}\right)$ ，因此我们可以将此步骤视为非策略性步骤而忽略。设 $\mathcal{R} = {2}^{R}$ 。那么一个机制就是一个随机映射 $\mathcal{M} : \mathcal{T} \rightarrow \mathcal{O} \times {\mathcal{R}}^{n}$ 。

让我们考虑功利主义福利准则： $F\left( {t,s,r}\right) =$ $\frac{1}{n}\mathop{\sum }\limits_{{i = 1}}^{n}u\left( {{t}_{i},s,{r}_{i}}\right)$ 。注意，该准则的敏感度为 $\Delta = 1/n$ ，因为每个参与者的效用都在区间 $\left\lbrack {0,1}\right\rbrack$ 内。因此，如果我们简单地选择一个结果 $s$ 并允许每个参与者做出他们的最优反应，指数机制就是一个 $\epsilon$ - 差分隐私机制。根据定理 3.11，该机制以高概率实现至少为 OPT $O\left( \frac{\log \left| \mathcal{O}\right| }{\epsilon n}\right)$ 的社会福利。我们将这个具有质量得分 $F$ 、范围 $\mathcal{O}$ 和隐私参数 $\epsilon$ 的指数机制实例记为 ${\mathcal{M}}_{\epsilon }$ 。

其思路是在指数机制（具有良好的社会福利性质）和一个严格诚实机制（惩罚虚假报告，但社会福利性质较差）之间进行随机选择。如果我们进行适当的混合，就可以得到一个具有合理社会福利保证的严格诚实机制。

以下是一个这样的惩罚机制，它很简单，但对于给定的问题不一定是最优的：

定义 10.5。承诺机制 ${M}^{P}\left( {t}^{\prime }\right)$ 从 $\in \mathcal{O}$ 中均匀随机选择一个结果，并设定 ${\widehat{R}}_{i} = \left\{ {{r}_{i}\left( {{t}_{i}^{\prime },s,{R}_{i}}\right) }\right\}$ ，即它随机选择一个结果，并强制每个人按照他们报告的类型就是真实类型的方式做出反应。

将一个环境的差距定义为

$\gamma = \mathop{\min }\limits_{{i,{t}_{i} \neq {t}_{i}^{\prime },{t}_{-i}}}\mathop{\max }\limits_{{s \in \mathcal{O}}}\left( {u\left( {{t}_{i},s,{r}_{i}\left( {{t}_{i},s,{R}_{i}}\right) }\right) - u\left( {{t}_{i},s,{r}_{i}\left( {{t}_{i}^{\prime },s,{R}_{i}}\right) }\right) }\right) ,$

即 $\gamma$ 是参与者和类型在误报的最坏情况成本（关于 $s$ ）上的一个下界。注意，对于每个参与者，这种最坏情况至少以概率 $1/\left| \mathcal{O}\right|$ 出现。因此，我们有以下简单的观察结果：

引理 10.2。对于所有的 $i,{t}_{i},{t}_{i}^{\prime },{t}_{-i}$ ：

$u\left( {{t}_{i},{\mathcal{M}}^{P}\left( {{t}_{i},{t}_{-i}}\right) }\right) \geq u\left( {{t}_{i},{\mathcal{M}}^{P}\left( {{t}_{i}^{\prime },{t}_{-i}}\right) }\right) + \frac{\gamma }{\left| \mathcal{O}\right| }.$

注意，承诺机制是严格诚实的：每个个体至少有 $\frac{\gamma }{\left| \mathcal{O}\right| }$ 的激励不去说谎。

这表明存在一个具有良好社会福利保证的严格诚实机制：

定义 10.6。惩罚指数机制 ${\mathcal{M}}_{\epsilon }^{P}\left( t\right)$ 由参数 $\leq q \leq 1$ 定义，它以概率 $1 - q$ 选择指数机制 ${\mathcal{M}}_{\epsilon }\left( t\right)$ ，以互补概率 $q$ 选择惩罚机制 ${\mathcal{M}}^{P}\left( t\right)$ 。

观察到，根据期望的线性性质，对于所有的 ${t}_{i},{t}_{i}^{\prime },{t}_{-i}$ ，我们有：

$u\left( {{t}_{i},{\mathcal{M}}_{\epsilon }^{P}\left( {{t}_{i},{t}_{-i}}\right) }\right) = \left( {1 - q}\right) \cdot u\left( {{t}_{i},{\mathcal{M}}_{\epsilon }\left( {{t}_{i},{t}_{-i}}\right) }\right) + q \cdot u\left( {{t}_{i},{\mathcal{M}}^{P}\left( {{t}_{i},{t}_{-i}}\right) }\right)$

$\geq \left( {1 - q}\right) \left( {u\left( {{t}_{i},{\mathcal{M}}_{\epsilon }\left( {{t}_{i}^{\prime },{t}_{-i}}\right) }\right) - {2\epsilon }}\right) + q\left( {u\left( {{t}_{i},{\mathcal{M}}^{P}\left( {{t}_{i}^{\prime },{t}_{-i}}\right) }\right) + \frac{\gamma }{\left| \mathcal{O}\right| }}\right)$

$u\left( {{t}_{i},{\mathcal{M}}_{\epsilon }^{P}\left( {{t}_{i}^{\prime },{t}_{-i}}\right) }\right) - \left( {1 - q}\right) {2\epsilon } + q\frac{\gamma }{\left| \mathcal{O}\right| }$

$u\left( {{t}_{i},{\mathcal{M}}_{\epsilon }^{P}\left( {{t}_{i}^{\prime },{t}_{-i}}\right) }\right) - {2\epsilon } + q\left( {{2\epsilon } + \frac{\gamma }{\left| \mathcal{O}\right| }}\right) .$

以下两个定理展示了该机制的激励和社会福利性质。

定理10.3。若 ${2\epsilon } \leq \frac{q\gamma }{\left| \mathcal{O}\right| }$ ，则 ${\mathcal{M}}_{\epsilon }^{P}$ 是严格真实的。

注意，我们也为此机制提供了效用保证。设置参数 $q$ ，使我们得到一个真实机制：

${\mathbb{E}}_{s,\widehat{R} \sim {\mathcal{M}}_{\epsilon }^{P}}\left\lbrack {F\left( {t,s,r\left( {t,s,\widehat{R}}\right) }\right) }\right\rbrack$

$\geq \left( {1 - q}\right) \cdot {\mathbb{E}}_{s,\widehat{R} \sim {\mathcal{M}}_{\epsilon }}\left\lbrack {F\left( {t,s,r\left( {t,s,\widehat{R}}\right) }\right) }\right\rbrack$

$\left( {1 - \frac{{2\epsilon }\left| \mathcal{O}\right| }{\gamma }}\right) \cdot {\mathbb{E}}_{s,\widehat{R} \sim {\mathcal{M}}_{\epsilon }}\left\lbrack {F\left( {t,s,r\left( {t,s,\widehat{R}}\right) }\right) }\right\rbrack$

$\geq \left( {1 - \frac{{2\epsilon }\left| \mathcal{O}\right| }{\gamma }}\right) \cdot \left( {\mathop{\max }\limits_{{t,s,r}}F\left( {t,s,r}\right) - O\left( {\frac{1}{\epsilon n}\log \left| \mathcal{O}\right| }\right) }\right)$

$\geq \mathop{\max }\limits_{{t,s,r}}F\left( {t,s,r}\right) - \frac{{2\epsilon }\left| \mathcal{O}\right| }{\gamma } - O\left( {\frac{1}{\epsilon n}\log \left| \mathcal{O}\right| }\right) .$

设置

$\epsilon \in O\left( \sqrt{\frac{\log \left| \mathcal{O}\right| \gamma }{\left| \mathcal{O}\right| n}}\right)$

我们发现：

${\mathbb{E}}_{s,\widehat{R} \sim {\mathcal{M}}_{\epsilon }^{P}}\left\lbrack {F\left( {t,s,r\left( {t,s,\widehat{R}}\right) }\right) }\right\rbrack \geq \mathop{\max }\limits_{{t,s,r}}F\left( {t,s,r}\right) - O\left( \sqrt{\frac{\left| \mathcal{O}\right| \log \left| \mathcal{O}\right| }{\gamma n}}\right) .$

注意，在这个计算中，我们假设 $\epsilon \leq \gamma /\left( {2\left| \mathcal{O}\right| }\right)$ ，使得 $\frac{{2\epsilon }\left| \mathcal{O}\right| }{\gamma } \leq 1$ 且该机制定义明确。对于足够大的 $n$ ，这是成立的。也就是说，我们已经证明：

定理10.4。对于足够大的 $n,{M}_{\epsilon }^{P}$ ，可实现社会福利达到

至少

$\mathrm{{OPT}} - O\left( \sqrt{\frac{\left| \mathcal{O}\right| \log \left| \mathcal{O}\right| }{\gamma n}}\right) .$

注意，这个机制无需支付就能保证真实性！

现在让我们考虑这个框架的一个应用：设施选址博弈。假设一个城市想建造 $k$ 家医院，以最小化每个市民与其最近医院之间的平均距离。为简化问题，我们做一个温和的假设，即城市建在单位线段的离散化上。形式上，令 $L\left( m\right) = \left\{ {0,\frac{1}{m},\frac{2}{m},\ldots ,1}\right\}$ 表示步长为 $1/m.\left| {L\left( m\right) }\right| = m + 1$ 的离散单位线段。令对于所有 $i$ 有 $\mathcal{T} = {R}_{i} = L\left( m\right)$ ，且令 $\left| \mathcal{O}\right| = L{\left( m\right) }^{k}$ 。定义参与者 $i$ 的效用为：

$u\left( {{t}_{i},s,{r}_{i}}\right) = \left\{ \begin{array}{ll} - \left| {{t}_{i} - {r}_{i}}\right| , & \text{ If }{r}_{i} \in s \\ - 1, & \text{ otherwise. } \end{array}\right.$

${}^{3}$ 如果不是这种情况，我们可以轻松拆除然后重建城市。

换句话说，参与者与线段上的点相关联，而一个结果是为 $k$ 个设施中的每一个分配线段上的一个位置。参与者可以通过决定去哪个设施来对一组设施做出反应，他们做出这种决定的成本是他们自己的位置（即他们的类型）与他们选择的设施之间的距离。注意，这里 ${r}_{i}\left( {{t}_{i},s}\right)$ 是最近的设施 ${r}_{i} \in s$ 。

我们可以实例化定理10.4。在这种情况下，我们有： $\left| \mathcal{O}\right| =$ ${\left( m + 1\right) }^{k}$ 和 $\gamma = 1/m$ ，因为任意两个位置 ${t}_{i} \neq {t}_{i}^{\prime }$ 之间的差异至少为 $1/ m$ 。因此，我们有：

定理10.5。针对设施选址博弈实例化的 ${M}_{\epsilon }^{P}$ 是严格真实的，并且至少能实现社会福利：

$\mathrm{{OPT}} - O\left( \sqrt{\frac{{km}{\left( m + 1\right) }^{k}\log m}{n}}\right) .$

对于少量的设施 $k$ ，这已经非常好了，因为我们预期 $\mathrm{{OPT}} = \Omega \left( 1\right)$ 。

10.3 针对注重隐私的参与者的机制设计

在上一节中，我们看到差分隐私作为一种为只关心机制所选结果的参与者设计机制的工具是有用的。在这里，我们主要将隐私视为在传统机制设计中实现目标的一种工具。作为一种附带影响，这些机制也保护了所报告的参与者类型的隐私。这本身是一个有价值的目标吗？为什么我们希望我们的机制保护参与者类型的隐私呢？

稍加思考便会发现，参与者（agent）可能会在意隐私。实际上，通过基本的内省可以推测，在现实世界中，参与者重视对某些“敏感”信息保密的能力，例如健康信息或性取向。在本节中，我们将探讨如何对这种隐私价值进行建模的问题，以及文献中采用的各种方法。

鉴于参与者可能对隐私有偏好，即便对于像福利最大化这类我们已经可以在不考虑隐私的情况下解决的任务，也值得考虑设计将保护隐私作为额外目标的机制。正如我们将看到的，确实有可能将维克里 - 克拉克 - 格罗夫斯（VCG）机制进行推广，以在任何社会选择问题中私下近似优化社会福利，同时在隐私参数和近似参数之间实现平滑权衡，并且保证精确的占优策略真实性。

然而，我们可能希望更进一步。当存在对隐私有偏好的参与者时，如果我们希望设计出具有真实性的机制，就必须以某种方式在他们的效用函数中对其隐私偏好进行建模，然后设计出相对于这些新的“考虑隐私”的效用函数具有真实性的机制。正如我们在差分隐私中所看到的，将隐私建模为机制本身的一种属性是最为自然的。因此，我们的效用函数不仅仅是结果的函数，而是结果和机制本身的函数。在几乎所有的模型中，参与者对结果的效用都被视为线性可分的，也就是说，对于每个参与者 $i$ ，

${u}_{i}\left( {o,\mathcal{M},t}\right) \equiv {\mu }_{i}\left( o\right) - {c}_{i}\left( {o,\mathcal{M},t}\right) .$

这里 ${\mu }_{i}\left( o\right)$ 表示参与者 $i$ 对结果 $o$ 的效用，而 ${c}_{i}\left( {o,\mathcal{M},t}\right)$ 表示当使用机制 $\mathcal{M}$ 选择结果 $o$ 时参与者 $i$ 所经历的（隐私）成本。

我们首先考虑也许是最简单（也是最天真）的隐私成本函数 ${c}_{i}$ 模型。回想一下，对于 $\epsilon \ll 1$ ，差分隐私承诺对于每个参与者 $i$ ，以及对于每个可能的效用函数 ${f}_{i}$ 、类型向量 $\in {\mathcal{T}}^{n}$ 和偏差 ${t}_{i}^{\prime } \in \mathcal{T}$ ：

$\left| {{\mathbb{E}}_{o \sim M\left( {{t}_{i},{t}_{-i}}\right) }\left\lbrack {{f}_{i}\left( o\right) }\right\rbrack - {\mathbb{E}}_{o \sim M\left( {{t}_{i}^{\prime },{t}_{-i}}\right) }\left\lbrack {{f}_{i}\left( o\right) }\right\rbrack }\right| \leq {2\epsilon }{\mathbb{E}}_{o \sim M\left( t\right) }\left\lbrack {{f}_{i}\left( o\right) }\right\rbrack .$

如果我们将 ${f}_{i}$ 视为代表参与者 $i$ 的“预期未来效用”，那么将参与者 $i$ 的数据在 $\epsilon$ - 差分隐私计算中被使用的成本建模为与 $\epsilon$ 呈线性关系是很自然的。也就是说，我们认为参与者 $i$ 由某个值 ${v}_{i} \in \mathbb{R}$ 参数化，并采用：

${c}_{i}\left( {o,\mathcal{M},t}\right) = \epsilon {v}_{i},$

其中 $\epsilon$ 是使得 $\mathcal{M}$ 具有 $\epsilon$ - 差分隐私的最小值。这里我们假设 ${v}_{i}$ 代表类似 ${\mathbb{E}}_{o \sim M\left( t\right) }\left\lbrack {{f}_{i}\left( o\right) }\right\rbrack$ 的一个量。在这种情况下， ${c}_{i}$ 不依赖于结果 $o$ 或类型分布 $t$ 。

使用这种简单的隐私度量方法，我们讨论隐私数据分析中的一个基本问题：当数据所有者重视他们的隐私并坚持为此获得补偿时，如何收集数据。在这种情况下，除了支付款项之外，参与者没有其他他们看重的“结果”，只有因隐私损失而产生的负效用。然后，我们将讨论这种（以及其他）隐私损失负效用度量方法的缺点，以及在更一般的机制设计场景中，当参与者 ${do}$ 从机制的结果中获得效用时的隐私问题。

10.3.1 维克里 - 克拉克 - 格罗夫斯（VCG）机制的隐私推广

假设我们有一个一般的社会选择问题，由结果空间 $\mathcal{O}$ 和一组参与者 $N$ 定义，这些参与者对由 ${u}_{i} : \mathcal{O} \rightarrow \left\lbrack {0,1}\right\rbrack$ 给出的结果有任意偏好。我们可能希望选择一个结果 $\in \mathcal{O}$ 来最大化社会福利 $F\left( o\right) = \frac{1}{n}\mathop{\sum }\limits_{{i = 1}}^{n}{u}_{i}\left( o\right)$ 。众所周知，在任何这样的设定中，维克里 - 克拉克 - 格罗夫斯（VCG）机制可以实现恰好使社会福利最大化的结果 ${o}^{ * }$ ，同时收取费用，使得如实报告成为占优策略。如果我们想在保护隐私的同时实现相同的结果，该怎么办呢？隐私参数 $\epsilon$ 必须如何与我们对最优社会福利的近似程度进行权衡呢？

回想一下，我们可以使用指数机制来选择一个结果 $\in \mathcal{O}$ ，其质量得分是 $F$ 。对于隐私参数 $\epsilon$ ，这将给出一个分布 ${\mathcal{M}}_{\epsilon }$ ，定义为 $\Pr \left\lbrack {{\mathcal{M}}_{\epsilon } = o}\right\rbrack \propto$ $\exp \left( \frac{{\epsilon F}\left( o\right) }{2n}\right)$ 。此外，该机制具有良好的社会福利性质：以概率 $\beta$ ，它会选择某个 $o$ ，使得： $F\left( o\right) \geq$ $F\left( {o}^{ * }\right) - \frac{2}{\epsilon n}\left( {\ln \frac{\left| \mathcal{O}\right| }{\beta }}\right)$ 。但正如我们所见，差分隐私仅能保证 $\epsilon$ - 近似的真实性。

然而，可以证明 ${\mathcal{M}}_{\epsilon }$ 是以下精确优化问题的解：

${\mathcal{M}}_{\epsilon } = \arg \mathop{\max }\limits_{{\mathcal{D} \in \Delta \mathcal{O}}}\left( {{\mathbb{E}}_{o \sim \mathcal{D}}\left\lbrack {F\left( o\right) }\right\rbrack + \frac{2}{\epsilon n}H\left( \mathcal{D}\right) }\right) ,$

其中 $H$ 表示分布 $\mathcal{D}$ 的香农熵（Shannon Entropy）。换句话说，指数机制是恰好使期望社会福利加上由 $2/\left( {\epsilon n}\right)$ 加权的分布熵最大化的分布。这一点很重要，原因如下：已知任何在任何有限范围内恰好使期望参与者效用最大化的机制（称为分布范围最大机制）都可以与支付相结合，从而使如实报告成为精确的占优策略。指数机制是恰好使期望社会福利加上熵最大化的分布。换句话说，如果我们假设添加了一个额外的参与者，其效用恰好是分布的熵，那么指数机制在分布范围内是最大的。因此，它可以与支付相结合，使得如实报告对所有参与者（特别是 $n$ 个真实参与者）成为占优策略。此外，可以证明如何以保护隐私的方式收取费用。结论是，对于任何社会选择问题，社会福利可以以一种既保护差分隐私又完全真实的方式进行近似。

10.3.2 敏感调查者问题

在本节中，我们考虑一位数据分析师的问题，他希望使用一群个体的私有数据进行研究。然而，他必须说服这些个体交出他们的数据！个体因隐私损失而产生成本。数据分析师可以通过保证差分隐私并对他们的损失进行补偿来减轻这些成本，同时试图获取具有代表性的数据样本。

考虑敏感调查员爱丽丝面临的以下典型问题。她的任务是对一组 $n$ 个个体 $N$ 进行调查，以确定个体 $\in N$ 中满足某些属性 $P\left( i\right)$ 的比例。她的最终目标是发现该统计量的真实值 $\frac{1}{n}\left| {\{ i \in N : P\left( i\right) \} }\right|$ ，但如果无法做到这一点，她会满足于某个估计值 $\widehat{s}$ ，使得误差 $\left| {\widehat{s} - s}\right|$ 最小化。我们将采用基于大偏差界限的准确性概念，如果 $\Pr \left\lbrack {\left| {\widehat{s} - s}\right| \geq \alpha }\right\rbrack \leq \frac{1}{3}$ ，则称调查机制是 $\alpha$ -准确的。不可避免的问题是，个体重视他们的隐私，不会免费参与调查。当个体与爱丽丝互动时，他们会因隐私损失而产生一定成本，必须为此损失获得补偿。更糟糕的是，这些个体是理性（即自私）的主体，如果误报成本能带来经济收益，他们很可能会向爱丽丝误报自己的成本。这使得爱丽丝的问题完全属于机制设计领域，要求爱丽丝制定一个在统计准确性和成本之间进行权衡的方案，同时还要管理个体的激励机制。

顺便说一下，这个典型问题与任何使用潜在敏感数据集合的组织都广泛相关。例如，这包括使用搜索日志来提供搜索查询补全、使用浏览历史来改善搜索引擎排名、使用社交网络数据来选择展示广告和推荐新链接，以及现在网络上提供的无数其他数据驱动的服务。在所有这些情况下，都是从敏感数据集合的统计属性中获取价值，以换取某种报酬 4

以固定价格交换收集数据可能会导致对总体统计量的有偏估计，因为这样的方案只会从那些对隐私的重视程度低于所提供价格的个体那里收集数据。然而，如果不与主体进行互动，我们就无法知道应该提供什么价格，才能让足够多的人参与，从而保证我们收集到的答案只有很小的偏差。因此，为了获得该统计量的准确估计，自然会考虑使用拍卖的方式购买隐私数据，以此来确定这个价格。在为隐私数据进行拍卖时，必须面对两个明显的障碍，还有一个不太明显但更具隐患的额外障碍。第一个障碍是，必须对“隐私”进行定量形式化，以便用于衡量主体在对其数据进行各种操作时的成本。在这里，差分隐私提供了一个明显的工具。对于较小的 $\epsilon$ 值，因为 $\exp \left( \epsilon \right) \approx \left( {1 + \epsilon }\right)$ ，所以正如前面所讨论的，一个简单（但可能比较天真）的初步模型是将每个主体视为在参与隐私研究时具有一定的线性成本。我们在这里假设每个主体 $i$ 都有一个未知的隐私价值 ${v}_{i}$ ，并且当他的隐私数据以 $\epsilon$ -差分隐私的方式被使用时，会经历 $\operatorname{cost}{c}_{i}\left( \epsilon \right) = \epsilon {v}_{i}$ 5 第二个障碍是，我们的目标是与统计准确性进行权衡，而在机制设计中，统计准确性这一目标尚未得到充分研究。

${}^{4}$ 报酬不一定是明确的和/或以美元计价的——例如，它可能是使用“免费”服务。

最后一个更隐蔽的障碍是，个人因隐私泄露而付出的代价可能与其私人数据本身高度相关！假设我们只知道鲍勃非常重视其艾滋病状况的隐私，但并不明确知晓他是否患有艾滋病。这本身就具有泄露性，因为鲍勃的艾滋病状况可能与其对隐私的重视程度相关，而知道他为保护隐私愿意付出高昂代价，会让我们更新对其私人数据的推测。更关键的是，假设在一项艾滋病患病率调查的第一步，我们要求每个人报告他们对隐私的重视程度，然后打算通过拍卖来决定购买哪些人的数据。如果参与者如实报告，我们可能会发现报告的数值自然形成两个聚类：低重视程度者和高重视程度者。在这种情况下，我们甚至在收集任何数据或支付任何费用之前，就可能已经了解到了一些关于总体统计数据的信息——因此，参与者已经付出了代价。结果，参与者可能会虚报他们对隐私的重视程度，这可能会给调查结果带来偏差。这种现象使得直接披露机制存在问题，并将这个问题与经典机制设计区分开来。

有了一种量化参与者 $i$ 允许其数据被 $\epsilon$ -差分隐私算法 $\left( {{c}_{i}\left( \epsilon \right) = \epsilon {v}_{i}}\right)$ 使用所造成损失的方法后，我们几乎可以描述敏感调查者问题的结果了。回想一下，差分隐私算法是一种映射 ${\mathcal{T}}^{n} \rightarrow \mathcal{O}$ ，适用于一般类型空间 $\mathcal{T}$ 。接下来需要明确定义类型空间 $\mathcal{T}$ 究竟是什么。我们将考虑两种模型。在这两种模型中，我们都会为每个人关联一个比特 ${b}_{i} \in \{ 0,1\}$ ，它表示这个人是否满足敏感谓词 $P\left( i\right)$ ，以及一个隐私价值 ${v}_{i} \in {\mathbb{R}}^{ + }$ 。

${}^{5}$ 正如我们稍后将讨论的，这个假设可能存在问题。

在不敏感价值模型中，我们通过将类型空间设为 $\mathcal{T} = \{ 0,1\}$ 来计算隐私机制的 $\epsilon$ 参数：即，我们仅根据机制对敏感比特 ${b}_{i}$ 的处理方式来衡量隐私成本，而忽略它对所报告的隐私价值 ${v}_{i}6$ 的处理方式。
在敏感价值模型中，我们通过将类型空间设为 $\mathcal{T} = \left( {\{ 0,1\} \times {\mathbb{R}}^{ + }}\right)$ 来计算隐私机制的 $\epsilon$ 参数：即，我们根据机制对每个人的 $\left( {{b}_{i},{v}_{i}}\right)$ 这一对信息的处理方式来衡量隐私。

直观地说，不敏感价值模型假设个人忽略了其隐私价值与私人比特之间的相关性可能导致的潜在隐私损失，而敏感价值模型则假设个人认为这些相关性处于最坏情况，即他们的隐私价值 ${v}_{i}$ 与他们的私人比特 ${b}_{i}$ 一样具有泄露性。众所周知，在不敏感价值模型中，可以推导出近似最优的直接披露机制，以实现高精度和低成本。相比之下，在敏感价值模型中，没有任何个体理性的直接披露机制能够实现任何非平凡的精度。

这导致了一种有些不尽如人意的情况。敏感价值模型捕捉到了我们真正想要处理的微妙问题，但在这个模型中却得到了一个不可能的结果！以令人满意的方式绕过这个结果（例如，通过改变模型或机制的能力）仍然是一个引人入胜的开放性问题。

10.3.3 更好的隐私成本衡量方法

在上一节中，我们采用了一个简单的建模假设，即参与一个 $\epsilon$ - 差分隐私机制 $M$ 所产生的成本为 ${c}_{i}\left( {o,\mathcal{M},t}\right) = \epsilon {v}_{i}$ ，其中 ${v}_{i}$ 为某个数值。这种衡量方法存在几个问题。首先，尽管差分隐私保证了任何参与者的效用损失上限是一个与 $\epsilon$ （近似）呈线性关系的量，但没有理由认为参与者的成本下限也是这样一个量。也就是说，虽然采用 ${c}_{i}\left( {o,\mathcal{M},t}\right) \leq \epsilon {v}_{i}$ 是有充分理由的，但几乎没有依据将这个不等式变成等式。其次，（事实证明）任何仅作为 $\epsilon$ 的确定性函数（不仅仅是线性函数）的隐私衡量方法都会导致有问题的行为预测。

${}^{6}$ 也就是说，处理报告值的映射部分不必是差分隐私的。

那么，我们还可以如何对 ${c}_{i}$ 进行建模呢？一种自然的衡量方法是参与者报告的类型 $i$ 与机制结果之间的互信息。为了使这个定义明确，我们必须处于一个每个参与者的类型 ${t}_{i}$ 都从一个已知的先验分布 ${t}_{i} \sim \mathcal{T}$ 中抽取的环境中。每个参与者的策略是一个映射 ${\sigma }_{i} : \mathcal{T} \rightarrow \mathcal{T}$ ，它根据参与者的真实类型确定他所报告的类型。然后我们可以定义

${c}_{i}\left( {o,\mathcal{M},\sigma }\right) = I\left( {\mathcal{T};\mathcal{M}\left( {{t}_{-i},\sigma \left( \mathcal{T}\right) }\right) ,}\right.$

其中 $I$ 是表示参与者 $i$ 类型先验的随机变量 $\mathcal{T}$ 与表示机制结果的随机变量 $\mathcal{M}\left( {{t}_{-i},\sigma \left( \mathcal{T}\right) }\right)$ 之间的互信息，这里的机制结果是在给定参与者 $i$ 的策略下得到的。

这种衡量方法具有很大的吸引力，因为它表示了机制的输出与参与者 $i$ 的真实类型之间的“关联程度”。然而，除了需要一个关于参与者类型的先验分布之外，我们还可以观察到这种隐私损失衡量方法所导致的一个有趣的悖论。考虑这样一个世界，其中有两种三明治面包：黑麦面包（R）和小麦面包（W）。此外，在这个世界中，三明治偏好是非常私密且令人尴尬的。类型 $\mathcal{T}$ 的先验分布在 $\mathrm{R}$ 和 $\mathrm{W}$ 上是均匀的，并且机制 $\mathcal{M}$ 只是给参与者 $i$ 提供他声称喜欢的那种类型的三明治。现在考虑两种可能的策略， ${\sigma }_{\text{truthful }}$ 和 ${\sigma }_{\text{random }}$ 。 ${\sigma }_{\text{truthful }}$ 对应于如实报告三明治偏好（随后会吃到喜欢的三明治类型），而 ${\sigma }_{\text{random }}$ 则独立于真实类型随机报告（结果只有一半的时间能吃到喜欢的三明治）。使用随机策略的成本是 $I\left( {\mathcal{T};\mathcal{M}\left( {{t}_{-i},{\sigma }_{\text{random }}\left( \mathcal{T}\right) }\right) = 0}\right.$ ，因为输出与参与者 $i$ 的类型无关。另一方面，如实报告的成本是 $I\left( {\mathcal{T};\mathcal{M}\left( {{t}_{-i},{\sigma }_{\text{truthful }}\left( \mathcal{T}\right) }\right) = 1}\right.$ ，因为现在三明治的结果是参与者 $i$ 类型的恒等函数。然而，从任何外部观察者的角度来看，这两种策略是无法区分的！在这两种情况下，参与者 $i$ 都会得到一个均匀随机的三明治。那么为什么有人会选择随机策略呢？只要对手认为他们是随机选择的，他们就应该选择诚实策略。

另一种不需要关于参与者类型先验分布的方法如下。我们可以将参与者建模为具有一个满足以下条件的成本函数 ${c}_{i}$ ：

$\left| {{c}_{i}\left( {o,\mathcal{M},t}\right) }\right| = \ln \left( {\mathop{\max }\limits_{{{t}_{i},{t}_{i}^{\prime } \in \mathcal{T}}}\frac{\Pr \left\lbrack {\mathcal{M}\left( {{t}_{i},{t}_{-i}}\right) = o}\right\rbrack }{\Pr \left\lbrack {\mathcal{M}\left( {{t}_{i}^{\prime },{t}_{-i}}\right) = o}\right\rbrack }}\right) .$

注意，如果 $\mathcal{M}$ 是 $\epsilon$ - 差分隐私的，那么

$\mathop{\max }\limits_{{t \in {\mathcal{T}}^{n}}}\mathop{\max }\limits_{{o \in \mathcal{O}}}\mathop{\max }\limits_{{{t}_{i},{t}_{i}^{\prime } \in \mathcal{T}}}\ln \left( \frac{\Pr \left\lbrack {\mathcal{M}\left( {{t}_{i},{t}_{-i}}\right) = o}\right\rbrack }{\Pr \left\lbrack {\mathcal{M}\left( {{t}_{i}^{\prime },{t}_{-i}}\right) = o}\right\rbrack }\right) \leq \epsilon .$

也就是说，我们可以将差分隐私视为对所有可能结果的最坏情况隐私损失进行界定，而这里提出的度量仅考虑实际实现的结果 $o$ （以及类型向量 $t$ ）的隐私损失。因此，对于任何差分隐私机制 $\mathcal{M},\left| {{c}_{i}\left( {o,\mathcal{M},t}\right) }\right| \leq \epsilon$ ，对于所有 $o, t$ 都成立，但重要的是，成本可能因结果而异。

然后，我们可以考虑以下用于最大化社会福利 $F\left( o\right) = \mathop{\sum }\limits_{{i = 1}}^{n}{u}_{i}\left( o\right) .{}^{7}$ 的分配规则。我们讨论 $\left| \mathcal{O}\right| = 2$ 的情况（这不需要支付），但也可以分析一般情况（有支付），该情况可以针对任何社会选择问题私下实现维克里 - 克拉克 - 格罗夫斯（VCG）机制。

对于每个结果 $\in \mathcal{O}$ ，从分布 $\Pr \left\lbrack {{r}_{o} = x}\right\rbrack \propto \exp \left( {-\epsilon \left| x\right| }\right)$ 中选择一个随机数 ${r}_{o}$ 。
输出 ${o}^{ * } = \arg \mathop{\max }\limits_{{o \in \mathcal{O}}}\left( {F\left( o\right) + {r}_{o}}\right)$ 。

上述机制是 $\epsilon$ -差分隐私的，并且对于注重隐私的参与者而言是真实的，只要对于每个参与者 $i$ ，以及对于两个结果 $o,{o}^{\prime } \in \mathcal{O},\left| {{\mu }_{i}\left( o\right) - {\mu }_{i}\left( {o}^{\prime }\right) }\right| > {2\epsilon }$ 都成立。请注意，只要参与者对结果的效用是不同的，那么对于足够小的 $\epsilon$ ，这将是成立的。分析过程是通过考虑随机变量 ${r}_{o}$ 的任意固定实现，以及第 $i$ 个参与者偏离真实报告的任意偏差 ${t}_{i}^{\prime }$ 。有两种情况：在第一种情况下，这种偏差不会改变机制的结果 $o$ 。在这种情况下，参与者对结果的效用 ${\mu }_{i}$ 以及他因隐私损失而产生的成本 ${c}_{i}$ 都完全不会改变，因此参与者不会从偏离中获益。在第二种情况下，如果当参与者 $i$ 偏离时结果从 $o$ 变为 ${o}^{\prime }$ ，那么必然有 ${\mu }_{i}\left( {o}^{\prime }\right) < {\mu }_{i}\left( o\right) - {2\epsilon }$ 。然而，根据差分隐私， $\left| {{c}_{i}\left( {o,\mathcal{M},t}\right) - {c}_{i}\left( {{o}^{\prime },\mathcal{M},t}\right) }\right| \leq {2\epsilon }$ ，因此隐私成本的变化不足以使其变得有利。

${}^{7}$ 这种分配规则与指数机制极为相似，实际上可以修改为与之完全相同。

最后，通常考虑的对隐私成本进行建模的最保守方法如下。给定一个 $\epsilon$ -差分隐私机制 $\mathcal{M}$ ，仅假设

${c}_{i}\left( {o,\mathcal{M},t}\right) \leq \epsilon {v}_{i}$

对于某个数 ${v}_{i}$ 。这与我们之前考虑的线性成本函数类似，但关键在于，这里我们仅假设一个上界。我们到目前为止所考虑的所有其他隐私成本模型都满足这一假设。可以证明，许多将差分隐私算法与能够限制用户选择的惩罚机制相结合的机制，就像我们在第10.2.3节中考虑的那些机制一样，只要值 ${v}_{i}$ 是有界的，在存在有隐私偏好的参与者的情况下，它们仍能保持其真实性属性。

10.4 参考文献注释

本节基于派伊（Pai）和罗斯（Roth）的综述[70]以及罗斯的综述[73]。差分隐私与机制设计之间的联系最初由杰森·哈特林（Jason Hartline）提出，并由麦克谢里（McSherry）和塔尔瓦尔（Talwar）在他们的开创性著作《通过差分隐私进行机制设计》[61]中进行了研究，他们在该著作中考虑了将差分隐私应用于设计近似真实的数字商品拍卖。在数字商品场景下，关于精确真实机制的最佳结果归功于巴尔坎（Balcan）等人[2]。

使用差分隐私作为工具来设计精确真实机制的问题最初由尼斯姆（Nissim）、斯莫罗丁斯基（Smorodinsky）和滕内霍尔茨（Tennenholtz）在[69]中进行了探索，他们也是首次对将差分隐私（单独使用）作为一种解决方案概念提出批评的人。本节中使用差分隐私来获得精确真实机制的示例直接取自[69]。敏感调查员问题最初由戈什（Ghosh）和罗斯[36]考虑，并由[56, 34, 75, 16]进行了扩展。弗莱舍尔（Fleischer）和吕（Lyu）[34]考虑了本节中讨论的贝叶斯场景，而利格特（Ligett）和罗斯[56]考虑了带有要么接受要么放弃提议的最坏情况场景，两者都是为了绕过[36]中的不可能结果。戈什和利格特考虑了一个相关模型，其中参与决策（和隐私保证）仅在均衡状态下确定[35]。

在将隐私明确视为其效用函数一部分的参与者存在的情况下进行机制设计的问题，最早由肖（Xiao）的具有影响力的研究[85]提出，他考虑了（在其他隐私成本度量中）互信息成本函数。在此之后，陈（Chen）等人[15]和尼斯姆（Nissim）等人[67]展示了在两种不同的模型中，即使对于重视隐私的参与者，有时也可以设计出诚实机制。陈冲（Chen Chong）、卡什（Kash）、莫兰（Moran）和瓦德汉（Vadhan）考虑了我们在本节中讨论的基于结果的成本函数，而尼斯姆、奥兰迪（Orlandi）和斯莫罗丁斯基（Smorodinsky）在 $\epsilon >$ 中考虑了仅用线性函数对每个参与者的成本进行上界约束的保守模型。根据互信息来衡量隐私的“三明治悖论”归因于尼斯姆、奥兰迪和斯莫罗丁斯基。

黄（Huang）和坎南（Kannan）证明，通过添加支付可以使指数机制变得完全诚实[49]。凯恩斯（Kearns）、派伊（Pai）、罗斯（Roth）和厄尔曼（Ullman）展示了如何通过在大型博弈中私下计算相关均衡，利用差分隐私来推导渐近诚实的均衡选择机制[54]。罗杰斯（Rogers）和罗斯[71]强化了这些结果，他们展示了如何在大型拥塞博弈中私下计算近似纳什均衡，这使得该机制具有更强的激励特性。这两篇论文都使用了“联合差分隐私”的解决方案概念，该概念要求对于每个参与者 $i$ ，发送给其他参与者的消息的联合分布 $\neq i$ 在 $i$ 的报告中是差分隐私的。这个解决方案概念在其他隐私机制设计场景中也被证明是有用的，包括许（Hsu）等人[47]提出的用于计算隐私匹配的算法。

目录导航

第1章：https://blog.csdn.net/AdamCY888/article/details/146454841
第2章:https://blog.csdn.net/AdamCY888/article/details/146455093
第3章(1/3):https://blog.csdn.net/AdamCY888/article/details/146455756
第3章(2/3):https://blog.csdn.net/AdamCY888/article/details/146455796
第3章(3/3):https://blog.csdn.net/AdamCY888/article/details/146455328
第4章:https://blog.csdn.net/AdamCY888/article/details/146455882
第5章:https://blog.csdn.net/AdamCY888/article/details/146456100
第6章(1/2):https://blog.csdn.net/AdamCY888/article/details/146456712
第6章(2/2):https://blog.csdn.net/AdamCY888/article/details/146456972
第7章:https://blog.csdn.net/AdamCY888/article/details/146457037
第8章:https://blog.csdn.net/AdamCY888/article/details/146457172
第9章:https://blog.csdn.net/AdamCY888/article/details/146457257
第10章:https://blog.csdn.net/AdamCY888/article/details/146457331
第11章:https://blog.csdn.net/AdamCY888/article/details/146457418
第12章:https://blog.csdn.net/AdamCY888/article/details/146457489
第13章(含附录):https://blog.csdn.net/AdamCY888/article/details/146457601