【前言】最近几年，随着计算机学科的强势崛起，计算机这一学科逐渐的渗入到经济学中，以网络新经济学为代表的交叉学科开始走向舞台的中心。很多计算机网络方面的专家学者开始依靠博弈论解决在一定的规则下该网络中“用户最大化收益”的问题。当然，不仅仅是计算机网络，有很多其他方面的也有应用。就笔者本人来看，我们团队研究的就是依靠博弈论解决网络中用户的选择什么样的策略能够保证自己获得最大的收益，与此同时，该网络中的每个个体的收益都能同时达到最大化。组合拍卖就是博弈论中很经典的一种拍卖理论，那么组合博弈是什么呢？具体的应用场景是什么呢？有哪些核心的算法？如何保证博弈论中最经典的“纳什均衡”呢？下面我们就来一一了解。

1.组合拍卖的基本介绍

计算机科学的很大一部分以及经济学的很大一部分可能被视为解决“分配问题”，我们应该如何根据已有资源的不同可能用途进行分配。假设我们有一个不可分割的资源，两个玩家希望使用它，那么谁应该得到它？当然，这个问题用简单的拍卖理论就可以解决。那么继续拓展，如果有多个资源，并且多个资源之间可能存在依赖关系，那么对于青睐这些资源的用户而言，购买多个相互关联的资源的性价比可能要优于单独的购买一个资源，对于平台而言的话，也可能会利益最大化。那么，如何分配这一系列相互关联的资源就是一个问题了，组合拍卖就诞生了！

2.增价组合拍卖

增加组合拍卖，Ascending Auctions，是组合拍卖的其中的一种拍卖方案，其基本流程为：平台公布各产品价格，这些产品的价格最初设定为零或者很小的值，并且投标人通过在当前价格下对他们最愿意获得的商品集合进行竞标。然后，拍卖师通过以某种增价机制来反复更新用户间重叠产品的价格，直到达到所有投标人获得自己愿意获得的商品的集合为止，平台就公布最终的成交的价格和获胜投标者。这种拍卖方式很受欢迎，因为他可以使得用户和平台“双赢”。

3.增价组合拍卖的两种算法设计

（1）Ascending Item-Price Auctions 

该种拍卖机制的主要流程是：每一个Item逐步增加其价格，保持暂定分配，直到另一个投标人暂停持有的Item为止。 直观地说，在这一点上，需求等于供给。

 针对上述算法，存在了下面的例子，读者可根据该例子对算法进行具体的解析：

 

（2）Ascending Bundle-Price Auctions

 该种拍卖机制的主要流程是：在该种拍卖方式中，用户最大化自己的利益是前提，多个想依赖的Item结合形成Bundle，用户青睐的是其中的一个Bundle，但是在具体增价的过程中还是以单个Item为基础进行增价，最终的流程参考一下算法： 

针对上述算法，存在了下面的例子，读者可根据该例子对算法进行具体的解析：

 上述问题增加的前提是用户都想利益最大化，想以最低的价格获取自己青睐的商品集，但是我们的机制设计是要满足尽可能多的用户的需求，故得到最终的结论。

4.写在最后

本文是题主主要研究博弈论，看到该部分内容的时候，觉得收获颇多。故再次将其展示与博客，为了让大家更多的了解博弈论的真面目，另外一方面也会在后来做该方面工作的时候可以继续去补充，希望能和大家共勉，一起去贡献出更精彩的博客！

注：文章内容引用列表： 

1.Lavi R. Algorithmic game theory[J]. Computationally-efficient approximate mechanisms, 2007: 301-330.

---

题主只是一个入门的小学生，希望大家多多指教！如果该帖子确实能解决您的问题，望多多留言，谢谢！

---

 

 

目录

•写在前面

•问题引入

•暴力枚举

循环枚举

递归枚举

回溯枚举

•深度优先搜索

前序遍历

中序遍历

后序遍历

•字典序

•二进制位运算

•带重复数字

•总结

---

•写在前面

排列组合的问题，如果没有合适的算法去解决，时间复杂度会相当的大，毕竟阶乘的时间复杂度不仅让人头大，也让他计算机欲罢不能，而且我们遇到排列组合的相关问题的概率相当的大，所以非常有必要掌握排列组合相关的算法，碰到很多问题，我们心里就有些底气了。我这里例举几种算法，其中想要特别强调二进制的相关解法，非常有趣。

•问题引入

我们把实际问题抽象一下，就是从一个集合中取出任意元素，形成唯一的组合。如 [a,b,c] 可组合为 [a]、[b]、[c]、[ab]、[bc]、[ac]、[abc]。我们既然说的是排列组合，当然就有区分这个集合里面，是否存在重复的元素的问题，如 [a,a,b,c] 可组合为 [a]、[b]、[c]、[ab]、[aa]、[bc]、[ac]、[abc]、[aab]等等。针对是否存在重复的元素问题，我们自然需要不同的解决方案，不过有些方法思路存在共性，接下来我们以不同算法为基础，结合不同的问题进行讲解，完成思路的理解（我们的重点是思路，有了思路，实现代码的时候就简单多了）。这里我们抛出一个问题，即如下

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

我们先按照不含重复元素来进行思考，然后附上含重复元素的思路。

•暴力枚举

对于这种排列组合的问题，首先想到的当然是穷举。由于排列的要求较少，实现更简单一些，如果我先找出所有排列，再剔除由于位置不同而重复的元素，即可实现需求。假设需要从 [A B C D E] 五个元素中取出所有组合，那么我们先找出所有元素的全排列，然后再将类似 [A B] 和 [B A] 两种集合去重即可。当然，我们可以在枚举的时候进行一些剪枝，即在枚举个过程中进行一些判断，也可以当做一种优化。总结就是，逐个枚举，空集的幂集只有空集，每增加一个元素，让之前幂集中的每个集合，追加这个元素，就是新增的子集。还是不知道啥意思？没关系，我么来看思路和代码实现，这里我们分为两种枚举方式。

循环枚举

循环枚举的思路其实特别简单（暴力的思路就是人类的直觉，思路当然简单啦，哈哈哈），我们先创建结果集（res），然后往结果集里面添加一个空集，现在完成结果集的初始化之后（初始化的结果集中只有一个空集），我们开始在集合（nums）中开始循环遍历所有的元素，每次遍历一个元素，我们就把这个元素添加在当前结果集的每一个子集后，并形成新的子集，添加到结果集中，思路非常的简单暴力，代码吐下：

public static List<List<Integer>> enumerate(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    res.add(new ArrayList<Integer>());
    for (Integer n : nums) {
        int size = res.size();
        for (int i = 0; i < size; i++) {
            List<Integer> newSub = new ArrayList<Integer>(res.get(i));
            newSub.add(n);
            res.add(newSub);
        }
    }
    return res;
}

递归枚举

递归枚举的总体思路和循环枚举一致，只不过我们的实现方式是使用递归，代码的变化其实就是把循环枚举里面的最外面那层遍历集合（nums）的循环，使用递归来代替，很简单的，看代码你就明白了。

public static void recursion(int[] nums, int i,
                                List<List<Integer>> res) {
    if (i >= nums.length) return;
    int size = res.size();
    for (int j = 0; j < size; j++) {
        List<Integer> newSub = new ArrayList<Integer>(res.get(j));
        newSub.add(nums[i]);
        res.add(newSub);
    }
    recursion(nums, i + 1, res);
}

回溯枚举

回溯枚举就和上面的两种枚举思路有点不一样了，这种枚举思路就好像是我们人的思路，进行一个一个拼凑，只要符合我们子集的条件，就将这个子集添加进结果集，代码如下：

public static void backtrack(int[] nums, int i, List<Integer> sub, 
                                 List<List<Integer>> res) {
    for (int j = i; j < nums.length; j++) {
        if (j > i && nums[j] == nums[j - 1]) continue;
        sub.add(nums[j]);
        res.add(new ArrayList<Integer>(sub));
        backtrack(nums, j + 1, sub, res);
        sub.remove(sub.size() - 1);
    }
}

•深度优先搜索

集合中每个元素其实就两种状态，就是选和不选，我们通过这两种状态，可以构成了一个满二叉状态树，比如，左子树是不选，右子树是选，从根节点、到叶子节点的所有路径，构成了所有子集。可以有前序、中序、后序的不同写法，结果的顺序不一样。本质上，其实是比较完整的中序遍历。我这样光说，可能比较抽象，我这里通过画的一张中序遍历的图进行讲解，如下。

前序遍历

public static void preOrder(int[] nums, int i, 
              ArrayList<Integer> subset, List<List<Integer>> res) {
    if (i >= nums.length) return;
    subset = new ArrayList<Integer>(subset);

    res.add(subset);
    preOrder(nums, i + 1, subset, res);
    subset.add(nums[i]);
    preOrder(nums, i + 1, subset, res);
}

中序遍历

public static void inOrder(int[] nums, int i, 
              ArrayList<Integer> subset, List<List<Integer>> res) {
    if (i >= nums.length) return;
    subset = new ArrayList<Integer>(subset);

    inOrder(nums, i + 1, subset, res);
    subset.add(nums[i]);
    res.add(subset);
    inOrder(nums, i + 1, subset, res);
}

后序遍历

public static void postOrder(int[] nums, int i, 
         ArrayList<Integer> subset, List<List<Integer>> res) {
    if (i >= nums.length) return;
    subset = new ArrayList<Integer>(subset);

    postOrder(nums, i + 1, subset, res);
    subset.add(nums[i]);
    postOrder(nums, i + 1, subset, res);
    res.add(subset);
}

•字典序

如果你足够理解了前面的思路，其实你应该会发现前面本质思路可以分为两类，暴力、递归、回溯一类，以及深度优先搜索一类，分类的依据是什么呢？其实就是思考的角度不一样，前面的那一类，我们思考的对象是每个子集，我们对每个子集进行相关算法的实现，而深度优先搜索开始，我们将关注的点放在集合（nums）中的每个元素的状态，我们集合中的每个元素在子集中只有两个状态，也就是存在和不存在。现在我们将关注的点转到了元素的状态上，即01状态，上面的深度优先搜索的实现只是一个过渡，本质上和递归等效率差不了多少，因为01状态是二进制的天下，我们自然使用二进制来代替，效率很高。利用二进制的思想去解决这个问题，就很简单了，值得一提的是，我们在使用二进制思想解决问题的时候，并不一定说使用位运算，而这里要讲的字典序，就不适用位运算来实现二进制思路。为了更好的理解思路，我们暂时先将问题简化为：

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

算法其实非常的直观，不过有一个值得注意的是，我们在子集的最后需要放一个标志位（也就是所说的哨兵），在每次循环的时候，我们只要找到nums中的第一个满足 nums[j] + 1 != nums[j + 1]的元素，并将其加一nums[j]++ 以转到下一个组合。这种思想代替了位运算，完成了二进制的实现

public List<List<Integer>> combine(int n, int k) {
  LinkedList<Integer> nums = new LinkedList<Integer>();
  for(int i = 1; i < k + 1; ++i)
    nums.add(i);
  nums.add(n + 1);

  List<List<Integer>> output = new ArrayList<List<Integer>>();
  int j = 0;
  while (j < k) {
    output.add(new LinkedList(nums.subList(0, k)));
    j = 0;
    while ((j < k) && (nums.get(j + 1) == nums.get(j) + 1))
      nums.set(j, j++ + 1);
    nums.set(j, nums.get(j) + 1);
  }
  return output;
}

•二进制位运算

很多算法都能通过位运算巧秒地解决，其优势主要有两点：一者位运算在计算机中执行效率超高，再者由于位运算语义简单，算法大多直指本质。组合算法也能通过位运算实现，而且代码实现之后，简直令人回味无穷。我们将问题回归到最开始的问题，现在我们假设，从 M 个元素中取任意个元素形成组合，组合内元素不能重复、元素位置无关。我们使用状态的思想，对于每个元素来说，要么被放进组合，要么不放进组合。每个元素都有这么两种状态。我们这里举个例子，如果从 5 个元素中任意取 N 个元素形成组合的话，用二进制位来表示每个元素是否被放到组合里，就是：

每种组合都可以拆解为 N 个二进制位的表达形式，而每个二进制组合同时代表着一个十进制数字，所以每个十进制数字都就能代表着一种组合。十进制数字的数目我们很简单就能算出来，从00000... 到 11111... 一共有种，排除掉全都不被放进组合这种可能，结果有几种。

public List<List<String>> combination(String[] m) {
    List<List<String>> result = new ArrayList<>();
    for (int i = 1; i < Math.pow(2, m.length) - 1; i++) {
        List<String> eligibleCollections = new ArrayList<>();
        for (int j = 0; j < m.length; j++) {
            if ((i & (int) Math.pow(2, j)) == Math.pow(2, j)) {
                eligibleCollections.add(m[j]);
            }
        }
        result.add(eligibleCollections);
    }
    return result;
}

当然，还想更秀操作一点，我们在第一和二层循环那里，使用位移运算，来完成与运算，本质是一样的，代码如下

public static List<List<Integer>> binaryBit(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    for (int i = 0; i < (1 << nums.length); i++) {
        List<Integer> sub = new ArrayList<Integer>();
        for (int j = 0; j < nums.length; j++)
            if (((i >> j) & 1) == 1) sub.add(nums[j]);
        res.add(sub);
    }
    return res;
}

当然，如果我们还有一种稍微绕一点点的二进制实现方式，就是数1的个数，这种思路有点绕，不过不管怎么样都还是二进制的一种实现方式，带着二进制的特色，我这里就大概的提一下数二进制中1的个数的实现方式，具体的问题解决代码，感兴趣的可以自己去实现以下，数二进制中1的个数的代码如下，想要关于数二进制的个数的其他算法，可以看我另一篇文章

int BitCount1(unsigned int n)
{
    unsigned int c =0 ; // 计数器
    for (c =0; n; n >>=1) // 循环移位
        c += n &1 ; // 如果当前位是1，则计数器加1
    return c ;
}

•带重复数字

我们在集合中带有重复数字，这样的集合和不带重复数字有什么区别呢？我们按照这个思路，其实可以使用不重复数字的求解方式，在求解带重复数字集合的过程中，进行去重即可。有了这种思路，我们去设计算法其实就不难了，在暴力、递归、回溯、深搜的方法中，我们很容易的将算法进行改进，我在这里就不多提了，这里要说的是二进制的算法改进。你仔细想一下我们怎么样才能在二进制的算法中进行相应的去重，这其实不容易想到的。

我们来假设nums中有[1,2,3]，那么它的结果集以及对应的二进制形如下面这这样

1 2 3
0 0 0 -> [     ]
0 0 1 -> [    3]
0 1 0 -> [  2  ]   
0 1 1 -> [  2 3]  
1 0 0 -> [1    ]
1 0 1 -> [1   3] 
1 1 0 -> [1 2  ]
1 1 1 -> [1 2 3]

但是如果有了重复数字，很明显就行不通了。例如对于 nums = [ 1 2 2 2 3 ]。

1 2 2 2 3
0 1 1 0 0  -> [  2 2  ]
0 1 0 1 0  -> [  2 2  ]
0 0 1 1 0  -> [  2 2  ]

上边三个数产生的数组重复的了。三个中我们只取其中 1 个，取哪个呢？我们仔细想一下应该好想到，就是我们只要去重复数字的开头的序列就可以了，比如重复了三个2，那么我们只要分别取一个2开头即“2”，两个2开头即“22”以及三个2开头即“222”就可以了，这样就可以避免重复，更形象的解释，我们举个五个2的例子，然后例举出他们不重复的序列，像下面这样

2 2 2 2 2 
1 0 0 0 0 -> [  2         ]
1 1 0 0 0 -> [  2 2       ]
1 1 1 0 0 -> [  2 2 2     ]
1 1 1 1 0 -> [  2 2 2 2   ]
1 1 1 1 1 -> [  2 2 2 2 2 ] 

那么这个时候，我们就可以将问题转成，我们怎么去取不同个数的2在一起，其实仔细思考也不难理解，我们只要对二进制稍微研究一下就知道了，我们先拿两个2来举例子，在五位二进制中，有两个2开头的二进制序列有哪些？

2 2 2 2 2 
1 1 0 0 0 -> [  2 2       ]
1 0 1 0 0 -> [  2 2       ]
0 1 1 0 0 -> [  2 2       ]
0 1 0 1 0 -> [  2 2       ]
0 0 0 1 1 -> [  2 2       ]

上面所有两个2的情况，我们只需要去其中一种，那么我们应该取哪种？怎么取呢？这个时候我们观察一下他们是否存在不同点，而且其中存在一个和其他情况都不同的形式，我们来看一下出现了重复数字，并且当前是 1 的前一个的二进位。

对于 1 1 0 0 0 ，是 1。

对于 1 0 1 0 0 , 是 0。

对于 0 1 1 0 0 ，是 0。

对于 0 1 0 1 0 ，是 0。

对于 0 0 0 1 1 ，是 0。

可以看到只有第一种情况对应的是 1 ，其他情况都是 0。其实除去从开头是连续的 1 的话，就是两种情况。第一种就是，占据了开头，类似于这种 10...1....。第二种就是，没有占据开头，类似于这种 0...1...。这两种情况，除了第一位，其他位的 1 的前边一定是 0。所以的话，我们的条件是看出现了重复数字，并且当前位是 1 的前一个的二进位。有了这种思路，我们只需要在不重复的代码中，进行一个判断就可以了，代码如下

public static List<List<Integer>> binaryBit(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    for (int i = 0; i < (1 << nums.length); i++) {
        List<Integer> sub = new ArrayList<Integer>();
        boolean illegal=false;
        for (int j = 0; j < nums.length; j++)
            if (((i >> j) & 1) == 1) {
                if(j>0&&nums[j]==nums[j-1]&&(i>>(j-1)&1)==0){
                    illegal=true;
                    break;
                }else{
                    sub.add(nums[j]);
                }
            }
        if(!illegal){
            res.add(sub);
        }
    }
    return res;
}

•总结

二进制是真的很美妙，我们的很多问题都可以通过二进制来解决，所以我们需要慢慢适应并融入二进制的世界，思考问题的角度和 思路也将变得更加开阔。

写在前面的话

书上学来终觉浅，绝知此事要躬行。

回顾

1、与$k$-Anonymity不同，差分隐私是算法的属性，而不是数据的属性。也就是说，我们可以证明算法满足差分隐私。

2、随机函数$F$中的随机性应该是"足够的"，以便从$F$观察到的输出不会揭示$x$或$x^{\prime }$中哪一个是输入。

3、当$ϵ$越小时，数据效用越低，隐私保护程度越高；当$ϵ$越大时，数据效用越高，隐私保护程度越低。

4、普遍的共识是$ϵ$应该在1左右或更小，并且$ϵ$的值高于10可能对保护隐私没有多大作用 ，但这个经验法则可能会变得非常保守。

5、拉普拉斯机制不会拒绝被确定为恶意的查询，相反，它增加了足够的噪音，恶意查询的结果对对手毫无用处。

讲完了拉普拉斯，我们来看看差分隐私的组合定理~

差分隐私的属性（Properties of Differential Privacy）

由差分隐私的定义，所产生的差分私有机制的三个重要属性。

这些属性将帮助我们设计满足差分隐私的有用算法，并确保这些算法提供准确的答案。

这三个属性是：

1、顺序组成（Sequential composition）

2、平行组合（Parallel composition）

3、后处理（Post processing）

顺序组成（Sequential composition）

差分隐私的第一个主要性质是顺序组合，它限制了在同一输入数据上发布多个差私有机制结果的总隐私成本。

形式上，差分隐私的顺序组合定理说：

如果$F_1(x)$满足${ϵ}_1$-差异隐私

并且$F_2(x)$满足${ϵ}_2$-差分隐私

则释放两个结果的机制$G(x)=(F_1(x),F_2(x))$满足${ϵ}_1+{ϵ}_2$-差分隐私。

顺序组合是差分隐私的重要属性，因为它可以设计出多次查阅数据的算法。

当对单个数据集执行多个单独的分析时，顺序组合也很重要。

因为它允许个人通过参与所有这些分析来约束他们产生的总隐私成本。

顺序组合给出的隐私成本的界限是一个上限，两个特定的差异隐私机制的实际隐私成本可能小于此，但永远不会比这个更大。

如果我们检查来自一个将两个差分隐私结果平均在一起的机制的输出分布，那么$ϵ$的"相加"原则是有意义的。

上例子！

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
plt.style.use('seaborn-whitegrid')
epsilon1 = 1
epsilon2 = 1
epsilon_total = 2

# satisfies 1-differential privacy
def F1():
    return np.random.laplace(loc=0, scale=1/epsilon1)

# satisfies 1-differential privacy
def F2():
    return np.random.laplace(loc=0, scale=1/epsilon2)

# satisfies 2-differential privacy
def F3():
    return np.random.laplace(loc=0, scale=1/epsilon_total)

# satisfies 2-differential privacy, by sequential composition
def F_combined():
    return (F1() + F2()) / 2

如果我们绘制F1 和 F2 ，我们会看到它们的输出的分布看起来非常相似。

# plot F1
plt.hist([F1() for i in range(1000)], bins=50, label='F1');

# plot F2 (should look the same)
plt.hist([F2() for i in range(1000)], bins=50, alpha=.7, label='F2');
plt.legend();

如果我们绘制F1 和F3 ，我们看到输出的分布看起来F3比F1的分布**“更尖锐更瘦窄”**。

# plot F1
plt.hist([F1() for i in range(1000)], bins=50, label='F1');

# plot F3 (should look "pointier")
plt.hist([F3() for i in range(1000)], bins=50, alpha=.7, label='F3');
plt.legend();

因为它的$ϵ$越高，意味着隐私性越低，因此获得的结果与真实答案越相近。

如果我们绘制F1 和F_combined ，我们会看到输出F_combined的分布较于F1"更尖锐更瘦窄"。

# plot F1
plt.hist([F1() for i in range(1000)], bins=50, label='F1');

# plot F_combined (should look "pointier")
plt.hist([F_combined() for i in range(1000)], bins=50, alpha=.7, label='F_combined');
plt.legend();

这意味着它的答案比F1的答案更准确。

虽然只是做了一个平均的操作，但是结果告诉我们它的$ϵ$必须更高（即它产生的隐私比 ） 要高。

那么F3 和F_combined呢？回想一下，这两种机制的$ϵ$值是相同的 - 两者的$ϵ$均为 2。它们的输出分布应该看起来相同。

# plot F3
plt.hist([F3() for i in range(1000)], bins=50, label='F3');

# plot F_combined (should look "pointier")
plt.hist([F_combined() for i in range(1000)], bins=50, alpha=.7, label='F_combined');
plt.legend();

事实上，F3看起来"更尖锐更瘦窄"！为什么会发生这种情况？

请记住，顺序组合在几个版本的总$ϵ$上的上限，但是实际上对隐私的实际累积影响可能较低，并不与总$ϵ$上的上限效果一致。

在这种情况下，实际的隐私损失似乎略低于由顺序组合确定的上限$ϵ$。

总的来说顺序组合是控制总隐私成本的一种非常有用的方法，我们将看到它以许多不同的方式使用，但请记住，它不一定是一个确切的边界。

平行组合（Parallel Composition）

差分隐私的第二个重要性质称为并行组合。

并行组合可以看作是顺序组合的替代方案，第二种计算多个数据发布的总隐私成本边界的方法。

并行组合基于将数据集拆分为不相交的块，并在每个块上单独运行差异私有机制的想法。

由于块是不相交的，因此每个个体的数据只出现在一个块中 。因此，即使总共有$k$块，该机制也会对每个个体的数据运行一次。

正式一点说：

如果$F(x)$满足$ϵ$-差分隐私，我们将数据集$X$拆分为$k$不相交的块，使得$x_1\cup ...\cup x_k=X$

然后，释放所有结果的机制$F(x_1),...,F(x_k)$满足$ϵ$-差分隐私

这是一个比顺序组合更好的绑定。由于我们运行$F$ $k$次，顺序组合会说此过程满足$kϵ$-差分隐私。

并行组合允许我们说总隐私成本只是$ϵ$。

正式定义与我们的直觉相匹配，如果数据集中的每个参与者都向$X$贡献了一行，则此行将恰好出现在块之一$x_1,...,x_k$中。这意味着$F$只会"看到"这个参与者的数据一次，这意味着$ϵ$的隐私成本适合该个人。由于此属性适用于所有个人，因此每个人的隐私成本为$ϵ$。

直方图（Histograms）

在我们的上下文中，直方图是对数据集的分析，该数据集根据其中一个数据属性的值将数据集拆分为"条柱"，并计算每个条柱中的行数。

例如，直方图可能会计算数据集中达到特定教育水平的人数。

adult = pd.read_csv("adult_with_pii.csv")
adult['Education'].value_counts().to_frame().head(5)

直方图对于差分隐私特别有趣，因为它们会自动满足并行组合。

直方图中的每个"条柱"都由数据属性的可能值定义（例如，'Education' == 'HS-grad'）。

单个行不可能同时具有属性的两个值，因此以这种方式定义条柱可以保证它们不相交。

因此，我们已经满足了并行组合的要求，并且我们可以使用差分私有机制来释放所有"条柱"计数，总隐私成本仅为$ϵ$。

epsilon = 1

# This analysis has a total privacy cost of epsilon = 1, even though we release many results!
f = lambda x: x + np.random.laplace(loc=0, scale=1/epsilon)
s = adult['Education'].value_counts().apply(f)
s.to_frame().head(5)

列联表（Contingency Tables）

列联表或交叉制表（通常缩写为交叉表）就像一个多维直方图。

它计算数据集中具有特定值的行的频率，这些行一次具有多个属性。

在分析数据时，列联表经常用于显示两个变量之间的关系。

例如，我们可能希望查看基于教育水平和性别的计数：
关于pandas中crosstab的用法

pd.crosstab(adult['Education'], adult['Sex']).head(5)

就像我们之前看到的直方图一样，数据集中的每个人都只参与此表中出现的一个计数。

对于在构建列联表时考虑的任何一组数据属性，任何单个行都不可能同时具有多个值。

因此，在这里使用并行组合也是安全的。
python中的apply(),applymap(),map() 的用法和区别

ct = pd.crosstab(adult['Education'], adult['Sex'])
f = lambda x: x + np.random.laplace(loc=0, scale=1/epsilon)
ct.applymap(f).head(5)

还可以生成包含 2 个以上变量的列联表。但是，请考虑每次添加变量时会发生什么：每个计数都倾向于变小。

直观地说，当我们将数据集拆分为更多块时，每个块中的行数都会减少，因此所有计数都会变小。

这些缩小的计数会对我们从中计算出的差分隐私结果的准确性产生重大影响。

如果我们从信号和噪声的角度来考虑事物，那么大量的计数代表一个强信号，它不太可能被相对较弱的噪声（就像我们上面添加的噪声）干扰太多，因此即使在添加噪声之后，结果也可能是有用的。

然而，一小段计数代表一个微弱的信号，可能与噪声本身一样弱，并且在我们添加噪声后，我们将无法从结果中推断出任何有用的东西。

因此，虽然并行组合似乎为我们提供了"免费"的东西（以相同的隐私成本获得更多结果），但事实并非如此。

并行组合只是沿着不同的轴移动准确性和隐私之间的权衡，当我们将数据集拆分为更多块并发布更多结果时，每个结果都包含较弱的信号，因此准确性较低。

后处理（Post-processing）

这个想法很简单：通过以某种方式对数据进行后处理，不可能逆转差异隐私提供的隐私保护。

正式一点说：

如果$F(X)$满足$ϵ$-差分隐私，则对于任何（确定性或随机化）函数$g$, $g(F(X))$满足$ϵ$-差分隐私。

后处理属性意味着对差分私有机制的输出执行任意计算始终是安全的，不存在逆转该机制提供的隐私保护的危险。

特别是，可以执行后处理，这可能会减少噪声或改善机制输出中的信号。

例如，对于不应返回负结果的查询，将负结果替换为零。之前在差分隐私群里看到一个小伙伴弄电影评分的差分隐私，说是出现负数怎么办。就是利用后处理设为0就好，结果还是满足差分隐私的。

事实上，许多复杂的差分私有算法利用后处理来减少噪声并提高结果的准确性。

后处理属性的另一个含义是，差分隐私提供了对基于辅助信息的隐私攻击的抵抗力。

例如，函数$g$可能包含有关数据集元素的辅助信息，并尝试使用此信息执行链接攻击。

后处理属性表示，无论$g$中包含的辅助信息如何，此类攻击的有效性都受到隐私参数$ϵ$的限制。

总结

1、顺序组合给出的隐私成本的界限是一个上限，两个特定的差异隐私机制的实际隐私成本可能小于此，但永远不会比这个更大。

2、实际的隐私损失似乎略低于由顺序组合确定的上限$ϵ$。

3、如果数据集中的每个参与者都向$X$贡献了一行，则此行将恰好出现在块之一$x_1,...,x_k$中。这意味着$F$只会"看到"这个参与者的数据一次，这意味着$ϵ$的隐私成本适合该个人。由于此属性适用于所有个人，因此每个人的隐私成本为$ϵ$。

4、单个行不可能同时具有属性的两个值，因此以这种方式定义直方图中条柱可以保证它们不相交。

5、对于在构建列联表时考虑的任何一组数据属性，任何单个行都不可能同时具有多个值。因此，在这里使用并行组合也是安全的。

6、执行后处理，这可能会减少噪声或改善机制输出中的信号。