This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP-nets). Its focus is on aggregating preferences over so-called \emph{swaps}, for which optimal solutions in general are already known to be of exponential size. We first analyze a trivial 2-approximation algorithm that simply outputs the best of the given input preferences, and establish a structural condition under which the approximation ratio of this algorithm is improved to $4/3$. We then propose a polynomial-time approximation algorithm whose outputs are provably no worse than those of the trivial algorithm, but often substantially better. A family of problem instances is presented for which our improved algorithm produces optimal solutions, while, for any $\varepsilon$, the trivial algorithm can\emph{not}\/ attain a $(2-\varepsilon)$-approximation. These results may lead to the first polynomial-time approximation algorithm that solves the CP-net aggregation problem for swaps with an approximation ratio substantially better than $2$.

This paper presents two frameworks that generalize Conditional Preference networks (CP-nets). The first generalization is the LCP-theory, first order logic theory that provides a rich framework to express preferences. The the second generalization, the PCP-networks, is a probabilistic generalization of CP-nets that models conditional preferences with uncertainty.

One of the most remarkable things about the human moral mind is its flexibility. We can make moral judgments about cases we have never seen before. We can decide that pre-established rules should be broken. We can invent novel rules on the fly. Capturing this flexibility is one of the central challenges in developing AI systems that can interpret and produce human-like moral judgment. This paper details the results of a study of real-world decision makers who judge whether it is acceptable to break a well-established norm: ``no cutting in line.'' We gather data on how human participants judge the acceptability of line-cutting in a range of scenarios. Then, in order to effectively embed these reasoning capabilities into a machine, we propose a method for modeling them using a preference-based structure, which captures a novel modification to standard ``dual process'' theories of moral judgment.

We introduce PCP-nets, a formalism to model qualitative conditional preferences with probabilistic uncertainty. PCP-nets generalise CP-nets by allowing for uncertainty over the preference orderings. We define and study both optimality and dominance queries in PCP-nets, and we propose a tractable approximation of dominance which we show to be very accurate in our experimental setting. Since PCP-nets can be seen as a way to model a collection of weighted CP-nets, we also explore the use of PCP-nets in a multi-agent context, where individual agents submit CP-nets which are then aggregated into a single PCP-net. We consider various ways to perform such aggregation and we compare them via two notions of scores, based on well known voting theory concepts. Experimental results allow us to identify the aggregation method that better represents the given set of CP-nets and the most efficient dominance procedure to be used in the multi-agent context.

The Conditional Preference Network (CP-net) graphically represents user's qualitative and conditional preference statements under the ceteris paribus interpretation. The constrained CP-net is an extension of the CP-net, to a set of constraints. The existing algorithms for solving the constrained CP-net require the expensive dominance testing operation. We propose three approaches to tackle this challenge. In our first solution, we alter the constrained CP-net by eliciting additional relative importance statements between variables, in order to have a total order over the outcomes. We call this new model, the constrained Relative Importance Network (constrained CPR-net). Consequently, We show that the Constrained CPR-net has one single optimal outcome (assuming the constrained CPR-net is consistent) that we can obtain without dominance testing. In our second solution, we extend the Lexicographic Preference Tree (LP-tree) to a set of constraints. Then, we propose a recursive backtrack search algorithm, that we call Search-LP, to find the most preferable outcome. We prove that the first feasible outcome returned by Search-LP (without dominance testing) is also preferable to any other feasible outcome. Finally, in our third solution, we preserve the semantics of the CP-net and propose a divide and conquer algorithm that compares outcomes according to dominance testing.

We propose a novel framework to bootstrap the reputation of on-demand service compositions. On-demand compositions are usually context-aware and have little or no direct consumer feedback. The reputation bootstrapping of single or atomic services does not consider the topology of the composition and relationships among reputation-related factors. We apply Conditional Preference Networks (CP-nets) of reputation-related factors for component services in a composition. The reputation of a composite service is bootstrapped by the composition of CP-nets. We consider the history of invocation among component services to determine reputation-interdependence in a composition. The composition rules are constructed using the composition topology and four types of reputation-influence among component services. A heuristic-based Q-learning approach is proposed to select the optimal set of reputation-related CP-nets. Experimental results prove the efficiency of the proposed approach.

We propose a novel CP-Net based composition approach to qualitatively select an optimal set of consumers for an IaaS provider. The IaaS provider's and consumers' qualitative preferences are captured using CP-Nets. We propose a CP-Net composability model using the semantic congruence property of a qualitative composition. A greedy-based and a heuristic-based consumer selection approaches are proposed that effectively reduce the search space of candidate consumers in the composition. Experimental results prove the feasibility of the proposed composition approach.

Conditional preference statements have been used to compactly represent preferences over combinatorial domains. They are at the core of CP-nets and their generalizations, and lexicographic preference trees. Several works have addressed the complexity of some queries (optimization, dominance in particular). We extend in this paper some of these results, and study other queries which have not been addressed so far, like equivalence, thereby contributing to a knowledge compilation map for languages based on conditional preference statements. We also introduce a new parameterised family of languages, which enables to balance expressiveness against the complexity of some queries.

Modelling deontic notions through preferences [12] has the advantage of linking deontic notions to the manifold research on preferences, in multiple disciplines, such as philosophy, mathematics, economics and politics. In recent years, preferences have also been addressed within AI [15,8,18] and applications can be found in multi-agent systems [19] and recommender systems [17]. We shall model deontic notions through ceteris-paribus preferences, namely, conditional preferences for a state of affairs over another state of affairs, all the rest being equal. In particular, we shall focus on the ceteris-paribus preference for a proposition over its complement. The idea of ceteris-paribus preferences was originally introduced by the philosopher and logician Georg von Wright [22].

We propose multi-type probabilistic serial (MPS) and multi-type random priority (MRP) as extensions of the well known PS and RP mechanisms to the multi-type resource allocation problem (MTRA) with partial preferences. In our setting, there are multiple types of divisible items, and a group of agents who have partial order preferences over bundles consisting of one item of each type. We show that for the unrestricted domain of partial order preferences, no mechanism satisfies both sd-efficiency and sd-envy-freeness. Notwithstanding this impossibility result, our main message is positive: When agents' preferences are represented by acyclic CP-nets, MPS satisfies sd-efficiency, sd-envy-freeness, ordinal fairness, and upper invariance, while MRP satisfies ex-post-efficiency, sd-strategy-proofness, and upper invariance, recovering the properties of PS and RP.