Collaborative Optimization for Collective Decision-making in Continuous Spaces
Collaborative Optimization for Collective Decision-making in Continuous Spaces
复制标题
DOI：
10.1145/3038912.3052690
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
Nikhil Garg;Vijay Kamble;Ashish Goel;David Marn;Kamesh Munagala
中科院分区：
文献类型：
--
作者：
Nikhil Garg;Vijay Kamble;Ashish Goel;David Marn;Kamesh Munagala
许多社会决策问题存在于高维连续空间中，不适用于离散或单维决策的常见投票技术。这些问题通常是在举行选举前离散的，或者由代表们通过谈判决定。在这种情况下，我们提出了一种称为迭代局部投票的集体决策元算法，在该算法中，选民被顺序抽样，并被要求在其当前值的某个局部邻域内修改候选解，就像以选定范数的球所定义的那样。一般来说，这样的方案不收敛，或者，当它们收敛时，结果的解决方案没有自然的描述。我们首先证明了该算法在适当的邻域选择下收敛到某些自然环境下的合乎情理的解：当选民的效用可以表示为与其理想解的某种形式的距离时，以及当这些效用是跨维度的可加分解的时候。在许多这样的情况下，我们获得了社会福利最大化解决方案的收敛。然后，我们描述了一个实验，在这个实验中，我们测试了我们的算法，用于美国联邦预算对机械土耳其人的决策，有4,000多名工人，采用了§L1、§L2和§L∞Ball定义的社区。我们提出了几个观察结果，为此类过程的未来实现提供了依据。
Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a meta-algorithm called Iterative Local Voting for collective decision-making in this setting, in which voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm. In general, such schemes do not converge, or, when they do, the resulting solution does not have a natural description. We first prove the convergence of this algorithm under appropriate choices of neighborhoods to plausible solutions in certain natural settings: when the voters' utilities can be expressed in terms of some form of distance from their ideal solution, and when these utilities are additively decomposable across dimensions. In many of these cases, we obtain convergence to the societal welfare maximizing solution. We then describe an experiment in which we test our algorithm for the decision of the U.S. Federal Budget on Mechanical Turk with over 4,000 workers, employing neighborhoods defined by §L1, §L2 and §L∞ balls. We make several observations that inform future implementations of such a procedure.