Generalizing the Single-Crossing Property on Lines and Trees to Intermediate Preferences on Median Graphs

Clearwater, Adam; Puppe, Clemens; Slinko, Arkadii M.

Generalizing the Single-Crossing Property on Lines and Trees to Intermediate Preferences on Median Graphs

Adam Clearwater, Clemens Puppe, Arkadii M. Slinko

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 32-37.

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.

Adam Clearwater, Clemens Puppe, and Arkadii M. Slinko. 2015. Generalizing the Single-Crossing Property on Lines and Trees to Intermediate Preferences on Median Graphs. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 32–37. https://ijcai.org/proceedings/2015/12

@inproceedings{ijcai2015p12,
  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 M.},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {32--37},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/12},
}

TY  - CPAPER
TI  - Generalizing the Single-Crossing Property on Lines and Trees to Intermediate Preferences on Median Graphs
AU  - Clearwater, Adam
AU  - Puppe, Clemens
AU  - Slinko, Arkadii M.
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 32
EP  - 37
UR  - https://ijcai.org/proceedings/2015/12
ER  -