> For the complete documentation index, see [llms.txt](https://differentialprivacy.gitbook.io/dp/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://differentialprivacy.gitbook.io/dp/overview-4/overview/a-game-theoretic-view-of-query-release.md).

# 查询发布的博弈论观点

在本节中，我们将短暂停留在博弈论中，以解释我们拥有（并将看到）的一些查询发布算法。让我们考虑两个敌对玩家Alice和Bob之间的交互。Alice有一组她可能采取的行动，$$\mathcal{A}$$，而Bob有一组行动$$\mathcal{B}$$。博弈按以下方式进行：Alice选择了一些行动$$a\in\mathcal{A}$$（可能随机选择），同时Bob也选择一些行动$$b\in\mathcal{B}$$（可能随机选择）。Alice经历了成本$$c(a,b)\in\[-1,1]$$。Alice希望在进行博弈中最小化此成本，并且由于Bob是对抗性的，他希望在博弈中*最大化* 此成本。 这就是所谓的*零和* 博弈。

那么Alice应该怎么玩呢？ 首先，我们考虑一个更简单的问题。假设我们给Alice设置阻碍并要求她在玩之前向Bob宣布她的随机策略，并让Bob使用这些信息做出最佳反应？如果Alice宣布她将根据概率分布$$\mathcal{D}\_A$$ 进行一些行动$$a\in\mathcal{A}$$，那么Bob将做出最优响应以最大化Alice的期望成本。 也就是说，鲍勃会做出行动使：

$$
b^\*=arg\space\max\_{b\in\mathcal{B}}\mathbb{E}\_{a\sim\mathcal{D}\_A}\[c(a,b)].
$$

因此，一旦Alice宣布了她的策略，她就知道她的成本是多少，因为Bob将能够做出最佳响应。所以，*一旦Bob响应*，Alice将希望对动作进行分配以*最小化* 她的成本。也就是说，Alice希望使用定义为：

$$
\mathcal{D}*A=arg\space\min*{\mathcal{D}\in\Delta\mathcal{A}}\max\_{b\in\mathcal{B}}\mathbb{E}\_{a\sim\mathcal{D}}\[c(a,b)].
$$

的一个分布$$\mathcal{D}\_A$$。

如果她执行$$\mathcal{D}\_A$$（Bob是最优响应），Alice将经历她能保证的最低成本，但她必须提前宣布她的策略。 对Alice来说，这样的策略被称为最小-最大（$$min-max$$）策略。 让我们把Alice在使用最小-最大策略时获得的成本称为博弈的Alice的值， 记为$$v^A$$：

$$
v^A=\min\_{\mathcal{D}\in\Delta\mathcal{A}}\max\_{b\in\mathcal{B}}\mathbb{E}\_{a\sim\mathcal{D}}\[c(a,b)].
$$

我们同样可以问Bob应该怎么做，如果我们让他处于劣势，并迫使他首先向Alice宣布他的策略。 如果他这样做了，当Alice做出最优反应时，他将在行动$$b\in\mathcal{B}$$上执行分配$$\mathcal{D}*B$$以使Alice的期望成本*最大化\_。对于Bob，我们称这样的策略$$\mathcal{D}\_B$$为最大-最小（$$max-min$$）策略。我们可以定义Bob在这个博弈中的值，$$v^B$$，作为他可能宣布的任何策略所能确保的最大成本：

$$
v^B=\max\_{\mathcal{D}\in\Delta\mathcal{B}}\min\_{a\in\mathcal{A}}\mathbb{E}\_{b\sim\mathcal{D}}\[c(a,b)].
$$

明显地，$$v^B\leq v^A$$，因为宣布自己的策略只是一个障碍。

博弈论的基础结果之一是冯-诺伊曼的最小-最大（$$min-max$$）定理，它指出在任何零和对策中，$$v^B= v^A$$。$$^2$$（注：引用冯·诺伊曼的话说：“据我所知，没有这个定理，就不可能有博弈论。 ... 我以为在极大极小定理（Minimax Theorem）被证明之前，没有什么值得发表的。“ ）换句话说，在零和博弈中“先走”没有坏处，如果玩家玩得最优，我们可以准确地预测Alice的成本： 它将是$$v^A=v^b\equiv v$$，我们称之为博弈的值。

**定义 5.7** 在一个由行动集合$$\mathcal{A},\mathcal{B}$$和成本函数$$c:\mathcal{A}\times\mathcal{B}\to\[-1,1]$$定义的零和博弈中，令$$v$$为博弈的值。一个$$\alpha-$$近似的最小-最大策略是这样的分布$$\mathcal{D}\_A$$：

$$
\max\_{b\in\mathcal{B}}\mathbb{E}\_{a\sim\mathcal{D}\_A}\[c(a,b)]\leq v+\alpha
$$

相似的，一个$$\alpha-$$近似的最大-最小策略是这样的分布$$\mathcal{D}\_B$$：

$$
\min\_{a\in\mathcal{A}}\mathbb{E}\_{b\sim\mathcal{D}\_B}\[c(a,b)]\geq v-\alpha
$$

如果$$\mathcal{D}\_A$$和$$\mathcal{D}\_B$$都分别是$$\alpha-$$近似的最小-最大策略和最大-最小策略，我们说这对$$(\mathcal{D}\_A,\mathcal{D}\_B)$$是零和博弈的$$\alpha-$$近似纳什均衡。

那么这与查询发布有什么关系呢？

考虑一个特殊的零和博弈，该博弈是针对在数据域$$\mathcal{X}$$上发布一组线性查询$$\mathcal{Q}$$的问题设计的。首先，在不丧失一般性的情况下假定对于每一个$$f\in \mathcal{Q}$$， 存在一个查询$$\hat{f}\in\mathcal{Q}$$使得$$\hat{f}=1-f$$（例如：对于每一个$$\chi\in\mathcal{X},\hat{f}(\chi)=1-f(\chi)$$）。将Alice的行动集合定义为$$\mathcal{A}=\mathcal{X}$$，将Bob的行动集合定义为$$\mathcal{B}=\mathcal{Q}$$。我们将Alice称为*数据库玩家*，Bob称为*查询玩家*。 最后，将一个真正的私有数据库$$x$$归一化为一个概率分布 （例如：$$||x||\_1=1$$），定义成本函数$$c:\mathcal{A}\times\mathcal{B}\to\[-1,1]$$为：$$c(\chi,f)=f(\chi)-f(x)$$。让我们称这个博弈为“查询发布博弈”。

我们从一个简单的观察开始：

**命题 5.16.** 查询发布博弈的值是$$v=0$$。

【证明】我们首先证明$$v^A=v\leq0$$。考虑一下，如果我们让数据库玩家的策略对应于真正的数据库：$$\mathcal{D}\_A=x$$会发生什么。 那么我们有：

$$
\begin{aligned} v^A&\leq\max\_{f\in\mathcal{B}}\mathbb{E}*{\chi\sim\mathcal{D}*A}\[c(\chi,f)]\ &=\max*{f\in\mathcal{B}}\sum*{i=1}^{|\mathcal{X}|}f(\chi\_i)\cdot x\_i-f(x)\ &=f(x)-f(x)\ &=0. \end{aligned}
$$

（译者注：第一个等号是将$$c\_i(\chi\_i,f)=f(\chi\_i)-f(x)$$带入右式，得到$$\max\_{f\in\mathcal{B}}\sum\_{i=1}^{|\mathcal{X}|}f(\chi\_i)\cdot x\_i-f(x)\sum\_{i=1}^{|\mathcal{X}|}x\_i$$，又因为$$\mathcal{D}*A=x$$，所以$$\sum*{i=1}^{|\mathcal{X}|}x\_i=1$$，这样就得到了第一个等式。第二个等号就需要使用到$$\hat{f}=1-f$$这个条件，由该条件和线性查询$$f:\mathcal{X}\to\[0,1]$$这两个条件可知：$$\forall f(\chi\_i)\leq1$$，所以最大$$f(\chi\_i)=1$$，带入第二个等式就得到了第三个等式。）

接下来我们观察到$$v=v^B\geq0$$。对于矛盾点，假设$$v<0$$。换句话说，存在一个分布$$\mathcal{D}\_A$$使得对于所有$$f\in\mathcal{Q}$$

$$
\mathbb{E}\_{\chi\sim\mathcal{D}\_A}c(\chi,f)<0
$$

在这里，我们简单地注意到，根据定义， 如果$$\mathbb{E}\_{\chi\sim\mathcal{D}*A}c(\chi,f)=c<0$$，那么$$\mathbb{E}*{\chi\sim\mathcal{D}\_A}c(\chi,\hat{f})=-c>0$$，矛盾，因为$$\hat{f}\in\mathcal{Q}$$。（译者注：所以$$v=0$$）

我们所建立的结果表明，对于任何分布$$\mathcal{D}*A$$是数据库玩家的$$\alpha-$$近似最小-最大策略， 我们有：对于所有查询$$f\in\mathcal{Q}:|\mathbb{E}*{\chi\sim\mathcal{D}\_A}f(\chi)-f(x)|\leq\alpha$$。换句话说，分布$$\mathcal{D}\_A$$可以被看作是一个以$$\alpha-$$精度回答$$\mathcal{Q}$$中的每个查询的合成数据库。

对于非线性查询呢？ 如果稍微更改查询发布博弈，我们可以重复上面的相同参数。 我们不是让数据库玩家拥有对应于域元素$$\chi\in\mathcal{X}$$的策略，而是让数据库玩家拥有对应于数据库本身的策略！那么，$$c(f,y)=|f(x)-f(y)|$$。不难看出，该博弈的值仍然为0，并且$$\alpha-$$近似最小-最大策略对应于对$$\mathcal{Q}$$中的查询给出$$\alpha-$$精度答案的合成数据。

那么，我们如何计算零和博弈中的近似最小-最大策略呢？有很多方法！众所周知，如果Alice反复进行博弈游戏，则使用具有保证无反悔（no-regret guarantee）的在线学习算法来更新她的行动分布（定义在[11.2](https://github.com/doubleheiker/algorithmic-foundation-of-dp-zh-cn/blob/master/11-Differential-Privacy-and-Machine-Learning/Differentially-private-online-learning.html)节），Bob在每一轮都会做出近似-成本-最大化的响应，然后Alice的分布会迅速收敛到近似的最小-最大策略。可乘权重就是这样一种算法，理解可乘权重机制的一种方法是将其作为Alice在本节中定义的查询发布博弈中的策略。（私有区分器在这里扮演Bob的角色，在每一轮中挑选对应于近似最大化Alice的成本的查询）。对于Alice的策略对应于数据库而不是域元素的博弈，中位数机制是另一种这样的算法，并且因此也计算查询释放博弈的近似最小-最大解。

然而，也有其他方法来计算近似平衡！例如，查询玩家Bob可以使用无悔学习算法（如乘法权重）玩游戏，Alice可以在每一轮中使用一个近似-成本-最小化的数据库重复响应！在这种情况下，Alice在本实验过程中使用的数据库平均值也将收敛到近似的最小-最大解。这正是第[6](https://github.com/doubleheiker/algorithmic-foundation-of-dp-zh-cn/blob/master/6-Boosting-for-Queries/Overview.html)节所做的，在该节中，私有base-sanitizer扮演Alice的角色，根据Bob在查询中的分布情况，在每一轮中扮演一个近似成本-最小化的数据库。

事实上，计算零和博弈的近似均衡的第三种方法是让Alice和Bob根据无悔学习算法进行博弈。我们不会在这里介绍这种方法，但这种方法不仅可以保证数据库的隐私，还可以保证被询问的查询集的隐私，以及私有地解决某些类型的线性规划。