Robust Approximation and Incremental Elicitation in Voting Protocols
Robust Approximation and Incremental Elicitation in Voting Protocols
复制标题
投票协议中的鲁棒逼近和增量启发
DOI：
10.5591/978-1-57735-516-8/ijcai11-058
复制
发表时间：
2011
影响因子：
2.6
通讯作者：
Craig Boutilier
中科院分区：
文献类型：
--
作者：
Tyler Lu;Craig Boutilier
虽然投票计划提供了一个有效的手段，聚集的偏好，有效地引出选民的偏好的方法很少受到关注。我们解决这个问题，首先考虑近似的赢家确定时，不完整的选民偏好。利用自然的评分指标，我们使用最大遗憾来衡量质量或鲁棒性的建议获奖者，并开发多项式时间算法计算的替代与最小最大遗憾几个流行的投票规则。然后，我们将展示如何极大极小遗憾可以用来有效地推动增量偏好/投票诱导，并设计了几个算法这个过程。尽管最坏情况下的理论结果表明，大多数投票协议需要几乎完整的选民偏好，以确定赢家，我们证明了实际有效性的遗憾为基础的启发，以确定近似和精确的赢家在几个现实世界的数据集。
While voting schemes provide an effective means for aggregating preferences, methods for the effective elicitation of voter preferences have received little attention. We address this problem by first considering approximate winner determination when incomplete voter preferences are provided. Exploiting natural scoring metrics, we use max regret to measure the quality or robustness of proposed winners, and develop polynomial time algorithms for computing the alternative with minimax regret for several popular voting rules. We then show how minimax regret can be used to effectively drive incremental preference/vote elicitation and devise several heuristics for this process. Despite worst-case theoretical results showing that most voting protocols require nearly complete voter preferences to determine winners, we demonstrate the practical effectiveness of regret-based elicitation for determining both approximate and exact winners on several real-world data sets.