Optimal Bounds for the No-Show Paradox via SAT Solving

被引:0
作者
Brandt, Felix [1 ]
Geist, Christian [1 ]
Peters, Dominik [2 ]
机构
[1] Tech Univ Munich, Munich, Germany
[2] Univ Oxford, Oxford, England
来源
AAMAS'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS | 2016年
基金
英国工程与自然科学研究理事会;
关键词
Computer-aided theorem proving; social choice theory; SAT; no-show paradox; participation; Condorcet; SOCIAL CHOICE THEORY; IMPLIES;
D O I
暂无
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Voting rules allow multiple agents to aggregate their preferences in order to reach joint decisions. Perhaps one of the most important desirable properties in this context is Condorcet-consistency, which requires that a voting rule should return an alternative that is preferred to any other alternative by some majority of voters. Another desirable property is participation, which requires that no voter should be worse off by joining an electorate. A seminal result in social choice theory by Moulin [28] has shown that Condorcet-consistency and participation are incompatible whenever there are at least 4 alternatives and 25 voters. We leverage SAT solving to obtain an elegant human-readable proof of Moulin's result that requires only 12 voters. Moreover, the SAT solver is able to construct a Condorcet-consistent voting rule that satisfies participation as well as a number of other desirable properties for up to 11 voters, proving the optimality of the above bound. We also obtain tight results for set-valued and probabilistic voting rules, which complement and significantly improve existing theorems.
引用
收藏
页码:314 / 322
页数:9
相关论文
共 36 条
[1]  
[Anonymous], THESIS
[2]  
[Anonymous], PARTICIPATION FAILUR
[3]  
[Anonymous], EC THEORY
[4]  
Baumeister D., 2012, AAMAS, P577
[5]  
Belov A., 2012, J SATISF BOOLEAN MOD, V8, P123, DOI DOI 10.3233/SAT190094
[6]  
Biere A., 2013, Proceedings of SAT Competition 2013, V2013, P1
[7]  
Brandl F., 2015, WORKING PAPER
[8]  
Brandl F, 2015, PROCEEDINGS OF THE 2015 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS (AAMAS'15), P1411
[9]  
Brandl F, 2015, PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI), P18
[10]  
Brandt F., 2016, Handbook of computational social choice, DOI DOI 10.1017/CBO9781107446984