Are There Any Nicely Structured Preference Profiles Nearby?
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 62-67.
Abstract
We investigate the problem of deciding whether a given preference profile is close to a nicely structured preference profile of a certain type, as for instance single-peaked, single-caved, single-crossing, value-restricted, best-restricted, worst-restricted, medium-restricted, or group-separable profiles. We measure this distance by the number of voters or alternatives that have to be deleted so as to reach a nicely structured profile. Our results classify all considered problem variants with respect to their computational complexity, and draw a clear line between computationally tractable (polynomial time solvable) and computationally intractable (NP-hard) questions.
@inproceedings{ijcai2013p21,
title = {Are There Any Nicely Structured Preference Profiles Nearby?},
author = {Bredereck, Robert and Chen, Jiehua and Woeginger, Gerhard J.},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {62--67},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/21},
}
TY - CPAPER TI - Are There Any Nicely Structured Preference Profiles Nearby? AU - Bredereck, Robert AU - Chen, Jiehua AU - Woeginger, Gerhard J. T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 62 EP - 67 UR - https://ijcai.org/proceedings/2013/21 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
