Sequential Deliberation for Social Choice
Sequential Deliberation for Social Choice
复制标题
社会选择的顺序审议
DOI：
10.1007/978-3-319-71924-5_13
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Sakshuwong, S.
中科院分区：
文献类型：
--
作者：
Fain, B;Goel, A;Munagala, K;Sakshuwong, S.
社会选择是一个规范性的研究设计协议的集体决策。然而，在基础决策空间对于顺序投票来说太大或太复杂的情况下，标准投票方法可能是不切实际的。那么，我们如何设计一个协议--最好是去中心化的、简单的、可扩展的，并且不需要任何关于决策空间的特殊知识--来达成共识呢？我们建议顺序审议作为这个问题的自然解决方案。在这种迭代方法中，连续对代理讨价还价的决策空间使用以前的决定作为一个分歧的选择。我们表明，顺序审议发现一个1.208近似的最佳社会成本时，空间的偏好定义一个中位数图，非常接近这个值，只有一个小的常数数量的代理人从人口中抽样。我们还给出了更简单的机制类的下限，以证明我们的设计选择。我们进一步表明，顺序审议是事后帕累托有效的，并有真实的报告作为一个均衡的诱导广泛的形式游戏。最后，我们证明了在一般度量空间中，序列审议结果的社会成本分布的一阶矩和二阶矩也是有界的。
Social choice is a normative study of designing protocols for collective decision making. However, in instances where the underlying decision space is too large or complex for ordinal voting, standard voting methods may be impractical. How then can we design a protocol - preferably decentralized, simple, scalable, and not requiring any special knowledge of the decision space - to reach consensus? We propose sequential deliberation as a natural solution to this problem. In this iterative method, successive pairs of agents bargain over the decision space using the previous decision as a disagreement alternative. We show that sequential deliberation finds a 1.208-approximation to the optimal social cost when the space of preferences define a median graph, coming very close to this value with only a small constant number of agents sampled from the population. We also give lower bounds on simpler classes of mechanisms to justify our design choices. We further show that sequential deliberation is ex-post Pareto efficient and has truthful reporting as an equilibrium of the induced extensive form game. Finally, we prove that for general metric spaces, the first and second moment of the distribution of social cost of the outcomes produced by sequential deliberation are also bounded by constants.
登录
查看更多内容
投票直到你们两个同意：失真小且样本复杂的机制
DOI：
--
发表时间：
2017
期刊：
AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Stephen Gross;Elliot Anshelevich;Lirong Xia
通讯作者：
Lirong Xia
经济学实验室实验：讨价还价现象和讨价还价理论
DOI：
10.1017/cbo9780511528316.002
发表时间：
1987
期刊：
The Journal of Cell Biology
影响因子：
--
作者：
Alvin E. Roth
通讯作者：
Alvin E. Roth
两人讨价还价问题和可比效用
影响因子：
6.1
作者：
R. Myerson
通讯作者：
R. Myerson
双头垄断中的竞争设施选址问题：与 1 中值问题的联系
DOI：
--
发表时间：
2012
期刊：
Workshop on Internet and Network Economics
影响因子：
--
作者：
Daniela Sabán;N. Stier
通讯作者：
N. Stier
DOI：
10.1145/3038912.3052690
发表时间：
2017-02
期刊：
Proceedings of the 26th International Conference on World Wide Web
影响因子：
--
作者：
Nikhil Garg;Vijay Kamble;Ashish Goel;David Marn;Kamesh Munagala
通讯作者：
Nikhil Garg;Vijay Kamble;Ashish Goel;David Marn;Kamesh Munagala