Generalizing the Single-Crossing Property on Lines and Trees to Intermediate Preferences on Median Graphs
Abstract
Demange (2012) generalized the classical single-crossing property to the intermediate property on median graphs and proved that the representative voter theorem still holds for this more general framework. We complement her result with proving that the linear orders of any profile which is intermediate on a median graph form a Condorcet domain. We prove that for any median graph there exists a profile that is intermediate with respect to that graph and that one may need at least as many alternatives as vertices to construct such a profile. We provide a polynomial-time algorithm to recognize whether or not a given profile is intermediate with respect to some median graph. Finally, we show that finding winners for the Chamberlin-Courant rule is polynomial-time solvable or profiles that are single-crossing on a tree.
Cite
Text
Clearwater et al. "Generalizing the Single-Crossing Property on Lines and Trees to Intermediate Preferences on Median Graphs." International Joint Conference on Artificial Intelligence, 2015.Markdown
[Clearwater et al. "Generalizing the Single-Crossing Property on Lines and Trees to Intermediate Preferences on Median Graphs." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/clearwater2015ijcai-generalizing/)BibTeX
@inproceedings{clearwater2015ijcai-generalizing,
title = {{Generalizing the Single-Crossing Property on Lines and Trees to Intermediate Preferences on Median Graphs}},
author = {Clearwater, Adam and Puppe, Clemens and Slinko, Arkadii},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {32-38},
url = {https://mlanthology.org/ijcai/2015/clearwater2015ijcai-generalizing/}
}