Representing interval orders by weighted bases: Some complexity results
Ozturk, Meltem; Marquis, Pierre (2009), Representing interval orders by weighted bases: Some complexity results, Mathematical Social Sciences, 57, 3, p. 367-388. http://dx.doi.org/10.1016/j.mathsocsci.2008.12.011
TypeArticle accepté pour publication ou publié
Journal nameMathematical Social Sciences
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)This paper is centered on the notion of interval order as a model for preferences. We introduce a family of representation languages for such orders, parameterized by a scale and an aggregation function. We show how interval orders can be represented by elements of those languages, called weighted bases. We identify the complexity of the main decision problems to be considered for exploiting such representations of interval orders (including the comparison problems and the non-dominance problem). We also show that our representation of interval orders based on weighted bases encompasses the penalty-based representation of complete preorders as a specific case.
Subjects / KeywordsComputational complexity; Compact representation of preferences; Preferences over combinatorial domains
Showing items related by title and author.