在无中心机构下，用去中心化方法高效发现社会选择结果。
Snowveil: A Framework for Decentralised Preference Discovery
- 基于随机邻居采样与信念更新的传播机制，实现去中心化共识。
- 理论证明系统在有限期望时间内以高概率收敛到稳定结果。
- 适用于大规模分布式系统，适合研究共识算法与社会选择者。
传统社会选择中的偏好聚合依赖可信中心化机构。本文提出去中心化偏好发现（Decentralised Preference Discovery, DPD）：在部分信息、异步交互、抗审查和无中心协调条件下，可靠识别社会选择参数（如全局偏好分布下聚合规则的典型结果）。为此，我们提出Snowveil，一种基于八卦传播的框架，代理通过反复随机采样对等方的排名并更新本地信念，最终收敛至典型结果。利用势函数、次鞅理论和浓度不等式，我们证明该系统可在有限期望时间内以可调高概率达到稳定状态。单轮胜者过程可迭代用于多胜者场景。Snowveil对具体聚合规则无偏好，仅需规则满足正响应性等公理，为更广泛DPD协议提供形式基础。为展示其模块性，我们引入受限混合博达规则（Constrained Hybrid Borda, CHB），平衡广泛共识与多数支持。我们对CHB进行公理分析，并通过大规模模拟验证Snowveil的O(n)可扩展性。本工作为大规模去中心化系统中从主观、表达性强且多样化的偏好中涌现稳定共识提供了理论基础。
原文摘要 · Abstract (English)
Aggregating subjective preferences in social choice traditionally assumes a trusted central authority. In contrast, this paper formalises Decentralised Preference Discovery (DPD): the reliable identification of a social choice parameter (e.g. the canonical outcome of an aggregation rule applied to the global preference profile) under conditions of partial information, asynchronous interaction, censorship resistance, and no central coordinator. To address DPD, we propose Snowveil, a gossip-based framework where agents repeatedly sample random peer rankings and update local beliefs to converge on the canonical outcome. Using a potential function, submartingale theory, and concentration bounds, we prove the system reaches this stable state with tunable high probability, in finite expected time. This single-winner process can then be iterated to construct a set of winning candidates for multi-winner scenarios. Snowveil is agnostic to specific aggregation rules, requiring only that the rule satisfies axioms such as Positive Responsiveness, thus offering a formal basis for a wider class of DPD protocols. Demonstrating Snowveil's modularity, we introduce the Constrained Hybrid Borda (CHB), an aggregation rule designed to balance broad consensus with plurality support. We provide an axiomatic analysis of CHB and present empirical results via extensive simulation, validating Snowveil's O(n) scalability. Overall, this work provides a foundation for how a stable consensus emerges from subjective, expressive, and diverse preference profiles in large-scale decentralised systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。