2014/03/29 by Haris Aziz, Aziz, Haris
Computer Science · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Game Theory and Voting Systems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1403.7625
Top monotonicity is a relaxation of various well-known domain restrictions such as single-peaked and single-crossing for which negative impossibility results are circumvented and for which the median-voter theorem still holds. We examine the problem of testing top monotonicity and present a characterization of top monotonicity with respect to non-betweenness constraints. We then extend the definition of top monotonicity to partial orders and show that testing top monotonicity of partial orders is NP-complete.