如何匿名统计平均收入

作者: , 共 1435 字
系列:生活中的数学

查看该系列所有文章

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

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.

系列: 生活中的数学 »
在 slashdot 上看到一篇科技新闻,两个数学家(其中一个来自于 MIT )和一个计算机学家,在 arXiv 上发表了一篇论文《HOW TO GAMBLE IF YOU』RE IN A HURRY》(PDF 版链接),是最近几天很热门的一条新闻。
最佳约会策略里,我们提到,如果有 100 个女孩可以顺序挑选,那么最好的方法是先看前 37 个,然后在剩下的女孩里选择当时最好的那个女孩,这样有接近 40%的概率挑选到最好的那个女孩。同时,不可能有更好的策略
类似文章:
机器统治世界提到,随着科技的发展,我们可以直接用机器来替代政府。所谓机器统治世界,并不意味着机器是世界的主人。机器还是听命于人类,只不过以一种无法被干预的民主投票的方式。所以,机器统计世界的第一要解决的问题就是投票协议。
机器统治世界,其中一个重要的部分便是安全计算。而这一领域的开创性工作便是姚期智先生的「姚氏百万富翁问题」。相关的工作发表于 1982 年 FOCS 上的的《Protocols for secure computations》
想起比多中心的匿名投票协议,有一种很简单的使用盲签名的投票协议,可以做到匿名投票。
数学 » 数学游戏, 概率
蚁迹寻踪及其他数学探索》提到一个游戏:
给定\( n\times n\) 的实数矩阵,每行和每列都是递增的,求这\( n^2\) 个数的中位数。
相似度: 0.056
这个题目听说是 MSRA 的面试题。
相似度: 0.053
数学 » 悖论, 头脑风暴
最有名的关于换还是不换的问题是三门问题,已经被研究得比较透彻。这里想说的是另外一个悖论。
IT » 比特币
上篇大致描述了 bitcoin 的技术原理,只想说明一件事情: bitcoin 的协议是可靠的,它保证了 bitcoin 虚拟货币的信用问题,别人不会偷走我的 bitcoin ,我拿到的 bitcoin 也是真实可靠的。使用 bitcoin 交易有很多好处,可以轻易列出一大堆:
上个月写的二逼年终奖扣税方法果壳引用,甚受鼓舞。年终奖的扣税规则比较二逼,但我们在政府修改税法之前只能容忍它。相反地,我们可以充分利用其规则,进行一定程度的避税。
2012 年 3 月 20 日到期的 145 亿欧元的债务,使得这一天成为希腊债务危机的一个关键时点。Troika为第二轮救助所要求的减值私人投资者债务也成为焦点。