Logic-Based Preference Languages with Intermediate Complexity

Joel Uckelman, Andreas Witzel

Logic-based preference representation languages are used to represent utility functions in combinatorial auctions, and can also be used for voting. A canonical problem in this context is, given a set of propositional formulas with associated weights, to find an assignment that maximizes the sum of those weights which are associated to satisfied formulas. The general case is intractable, and natural restrictions of the languages tend either to leave the complexity unchanged or to reduce it to triviality. After proposing a revision of the decision problem considered in existing research, we use a new approach to find languages with P-complete maximization problem.

Subjects: 1.10 Information Retrieval; 11. Knowledge Representation

Submitted: May 5, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.