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 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.