Are There Any Nicely Structured Preference Profiles Nearby?
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.
Cite
Text
Bredereck et al. "Are There Any Nicely Structured Preference Profiles Nearby?." International Joint Conference on Artificial Intelligence, 2013.Markdown
[Bredereck et al. "Are There Any Nicely Structured Preference Profiles Nearby?." International Joint Conference on Artificial Intelligence, 2013.](https://mlanthology.org/ijcai/2013/bredereck2013ijcai-there/)BibTeX
@inproceedings{bredereck2013ijcai-there,
title = {{Are There Any Nicely Structured Preference Profiles Nearby?}},
author = {Bredereck, Robert and Chen, Jiehua and Woeginger, Gerhard J.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2013},
pages = {62-68},
url = {https://mlanthology.org/ijcai/2013/bredereck2013ijcai-there/}
}