Unconditional privacy in social choice
Unconditional privacy in social choice
复制标题
社会选择中的无条件隐私
DOI：
10.1145/1089933.1089957
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
T. Sandholm
中科院分区：
文献类型：
--
作者：
F. Brandt;T. Sandholm
冲突偏好的聚合是人类社会和多智能体系统中的一个重要问题。由于其普遍性，在一组备选方案中进行投票在偏好聚合机制中具有核心作用。我们考虑最一般的情况下，投票的选民的选择的排名映射到一个集体排名的替代品的所谓的社会福利功能（社福）。维护个人偏好的隐私至关重要，以保证选择自由（例如，缺乏投票胁迫和声誉效应），以及不促进战略性投票。我们调查是否可以实现无条件的完全隐私的偏好聚合，也就是说，隐私既不依赖于可信的第三方（或在一定比例的选民被信任），也不计算棘手的假设。更确切地说，我们研究了分布式协议的存在，允许选民共同确定集体偏好排名，而不透露进一步的信息。我们证明了不存在非独裁，帕累托，单调，私人可计算（这些属性中的任何三个可以实现）。此外，我们表明，用匿名取代隐私，使联合计算的任意对称SWFs。
The aggregation of conflicting preferences is an important issue in human society and multiagent systems. Due to its universality, voting among a set of alternatives has a central role among preference aggregation mechanisms. We consider the most general case of voting in which the voters' rankings of alternatives are mapped to a collective ranking of alternatives by a so-called social welfare functional (SWF). Maintaining privacy of individuals' preferences is crucial in order to guarantee freedom of choice (e.g., lack of vote coercing and reputation effects), and to not facilitate strategic voting. We investigate whether unconditional full privacy can be achieved in preference aggregation, that is, privacy that relies neither on trusted third parties (or on a certain fraction of the voters being trusted), nor on computational intractability assumptions. More precisely, we study the existence of distributed protocols that allow voters to jointly determine the collective preference ranking without revealing further information. We prove that there exists no SWF that is non-dictatorial, Paretian, monotonic, and privately computable (any three of these properties can be achieved). Moreover, we show that replacing privacy with anonymity enables the joint computation of arbitrary symmetric SWFs.