Article ID Journal Published Year Pages File Type
973171 Mathematical Social Sciences 2016 13 Pages PDF
Abstract

•We investigate whether a preference profile is close to having a nice structure.•These structural properties include single-peakedness and single-crossingness.•Our closeness is measured by deletion of voters and by deletion of alternatives.•For most of the cases, our central problems are computationally hard.•Computational easy cases include voter deletion for single-crossing property.

We investigate the problem of deciding whether a given preference profile is close to having a certain nice structure, 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 to make the profile a nicely structured one. Our results classify the 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.

Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, , ,