如何匿名统计平均收入

作者:, 发表于

网络的力量太大,这两次把问题放到网上不到半天,这些问题不但被解答,而且连出处都被翻出来了。这让我自己少了很多思考的乐趣。以后不能把问题太快放到网上。

1.简单情况

假设你参加一个大学同学的同学聚会,现在大家对毕业后大家的平均收入水平很感兴趣。但基于各种原因,每个人都不想让别人知道自己的收入水平。能否有一个方法,每个人都不会泄漏自己收入的情况下,大家一块儿算出一起的平均收入呢?

答案是存在的:假设大家围坐在一桌,先随便挑出一个人,这个人在心里生成一个随机数,加上自己的收入后传递给邻座,旁边这个人在接到这个数后再传给下一个人,依次下去,最后一个人在收到的数上加上自己的收入后传给第一个人。第一个人从收到的数里减去自己最开始使用的随机数,就能获得所有人的收入之和。该和除以参与人数就是大家的平均收入。

这种方法不只是上面这种生活上的应用,在真实的工作中也可以用到。比如现在很多证券公司的金融工程研究组用各种各样的方法试图统计基金的平均仓位,但得出的结果差异较大。为什么不直接发送调查问卷呢?因为没有基金经理愿意公开自己的具体仓位。而用上面的方法便可以在不泄漏每个基金的数据,并且统计出平均仓位的精确值。

上面是一本面试书里的题目。

2.解决合谋问题

上面所给的答案中,如果第一个人和第三个人串通(比如第一个人把自己告诉第二个人的数同时告诉第三个人,那么第二个人的收入就被泄露了。那么是否存在一种策略,使得,对每个人而言,除非其它所有人一起串通,否则自己的收入不会被泄露。

微博上pmonkey很快就给出了答案:

假设共有n个人,每个人可以把自己的收入随机的分成n份,并把其中n-1份分别告诉其他人。每个人把其他人告知的部分与自己留的一份相加为m(i),公开所有的m(i)再取平均值即可。

网友zornlemma甚至翻出了这个问题的出处,在《蚁迹寻踪及其他数学探索》的第四章谈到了保护隐私的协议,所使用的例子跟上面是一模一样的。

3.其它统计变量

在《蚁迹寻踪及其他数学探索》的第四章讨论了这个问题并给出了结论:

1. 假设每个人的收入是一定范围内的整数,那么任何统计变量都存在少数人-保隐私算法。这里少数人-保隐私算法 是指只要参与合谋的人低于总人数的一半,那么合谋以外的人的信息就不会被泄露。

2. 平均数以及可以表示为平均数的函数的统计量,是唯一存在多数人-保隐私算法的统计量。即对于中位数、最大值这样的统计量,只要多数人参与合谋,其它人的信息就会暴露。

除了收入是取值于有限集合的限制以外,上述两条已经完全解决了我们提到的问题。

4.安全多方计算和百万富翁问题

与之相关的是研究领域是安全多方计算(Secure multi-party computation),指参与的各方在不泄漏自己信息的情况下进行计算。其中一个著名的问题是百万富翁问题,被姚先生最早在1982年的FOCS会议上解决(这里我必须要检讨一下之前没有通读姚老板的论文,在zornlemma提醒之前我都没听说过):

百万富翁问题是指两个百万富翁想知道谁更富,但两个人都不想透露自己的资产数量。问怎么才能做到这一点。

姚先生的解决方案发表在论文A.C.Yao, Protocols for secure computation, Proceeding FOCS, 1982, 160-164。维基百科上有详细的算法:Yao's Millionaires' Problem

Q.E.D.


上一篇:取格子游戏的构造性策略2011年2月27日
在MIT BBS上看到一个有趣的题目 一个M*N的方阵,每个格子里放一个硬币。甲乙轮流取:选定一枚硬币后,必须取走它上方、右方和右上方的所有硬币(

下一篇:如何在多轮试酒中找出多杯毒酒2017年3月28日
500桶酒,其中2桶是毒酒,非常毒,一丁点就必死;48小时后要举行酒会;毒酒喝下去会在之后的0-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪2桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。