Logic-based preference languages with intermediate complexity

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 con-text is, given a set of propositional formulas with associated weights, to find an assignment1 that maximizes the sum of those weights which are associated to satisfied formulas. The general case is intractable, and natural restrictions of the lan-guages tend either to leave the complexity unchanged or to reduce it to triviality. After proposing a revision of the deci-sion problem considered in existing research, we use a new approach to find languages with P-complete maximization problem