Nic Wilson

ECAI Conference 2025 Conference Paper

On the Number of Queries Required to Determine an Optimal Alternative

• Nic Wilson

Given the assumption that a user’s preference relation, on a finite set of alternatives, is in a particular family of preference relations, we consider the problem of how many queries are required to determine sufficient information about the preference relation that an alternative can be returned that is optimal for the user. We focus especially on queries based on comparisons between two alternatives and related forms of query. We consider both a fixed version of this problem, where the user is given a questionnaire (or batch of queries), and is asked to answer them all; and a dynamic, i. e. , interactive, version, where the choice of query can depend on previous answers. We derive upper and lower bounds for the numbers of queries required, and give preference families that achieve these bounds; and we determine the solution of the batch problem for linear preference families.

ECAI Conference 2024 Conference Paper

Scale-Invariant Variations of Max Regret

• Nic Wilson

Max regret is frequently used, in situations when there is uncertainty about a user preference model in a multi-objective optimisation problem, as a measure of how close an alternative is to being necessarily optimal. It is used in a termination condition for a dialogue with a user, and for recommending a compromise solution, and in different ways of generating informative queries. In this paper we consider linear user preference models based on simple weighted sums of the objectives. Unfortunately, max regret lacks a desirable scale-invariance property: changing the units (or the linear scaling) of the objectives can significantly alter the relative values of max regret between alternatives, even though the choice of units is often somewhat arbitrary. In this paper we define variations of max regret in which the regret, of an alternative given a particular user model, is divided by a function expressing a range of utility values. This leads to scale-invariance, and maintains important properties of max regret such as translation-invariance (in contrast with max relative regret). We show how linear programming and extreme points algorithms can be used for computation.

ECAI Conference 2023 Conference Paper

Enforcing Natural Properties of Choice Functions, with Application for Combination

• Nic Wilson

One important and natural representation of preferences is a choice function, which returns the preferred options amongst any given subset of the alternatives. There are some very intuitive coherence conditions that might be assumed for an agent’s choice function, in particular path independence, and a consistency condition stating that there is always at least one preferred alternative among any non-empty set. However, an elicited choice function may not satisfy path independence, because of the elicitation being incomplete, or because of there being some incoherence in the agent’s reported choice function (despite the agent assenting to the general coherence conditions). Furthermore, if we wish to combine the choice functions of more than one agent, simple natural combination operations can lose path independence. This paper develops methods for enforcing path independence and restoring consistency, thus, making the user preferences coherent; this method also leads to approaches for combining two choice functions, in order to suggest the most promising alternatives for a pair of agents.

ECAI Conference 2023 Conference Paper

On the Variation of Max Regret with Respect to the Scaling of the Objectives

• Nic Wilson

In a multi-objective optimisation problem, when there is uncertainty regarding the correct user preference model, max regret is a natural measure for how far an alternative is from being necessarily optimal (i. e. , optimal with respect to every candidate preference model). It can be used for recommending a relatively safe choice to the user, or used in the generation of an informative query, and in the decision to terminate the user interaction, because an alternative is sufficiently close to being necessarily optimal. We consider a common and simple form of user preference model: a weighted average over the objectives (with unknown weights). However, changing the scale of an objective by a linear factor leads to an essentially different set of preference models, and this changes the max regret values (and potentially their relative ordering), sometimes very considerably. Since the scaling of the objectives is often partly subjective and somewhat arbitrary, it is important to be aware of how sensitive the max regret values are to the choices of scaling of the objectives. We give mathematical results that characterise and enable computation of this variability, along with an asymptotic analysis.

JAAMAS Journal 2022 Journal Article

Minimality and comparison of sets of multi-attribute vectors

• Federico Toffano
• Nic Wilson

Abstract In a decision-making problem, there is often some uncertainty regarding the user preferences. We assume a parameterised utility model, where in each scenario we have a utility function over alternatives, and where each scenario represents a possible user preference model consistent with the input preference information. With a set \(A\) of alternatives available to the decision-maker, we can consider the associated utility function, expressing, for each scenario, the maximum utility among the alternatives. We consider two main problems: firstly, finding a minimal subset of \(A\) that is equivalent to it, i. e. , that has the same utility function. We show that for important classes of preference models, the set of possibly strictly optimal alternatives is the unique minimal equivalent subset. Secondly, we consider how to compare \(A\) to another set of alternatives \(B\), where \(A\) and \(B\) correspond to different initial decision choices. This is closely related to the problem of computing setwise max regret. We derive mathematical results that allow different computational techniques for these problems, using linear programming, and especially, with a novel approach using the extreme points of the epigraph of the utility function.

AAMAS Conference 2021 Conference Paper

Efficient Exact Computation of Setwise Minimax Regret for Interactive Preference Elicitation

• Federico Toffano
• Paolo Viappiani
• Nic Wilson

A key issue in artificial intelligence methods for interactive preference elicitation is choosing at each stage an appropriate query to the user, in order to find a near-optimal solution as quickly as possible. A theoretically attractive method is to choose a query that minimises max setwise regret (which corresponds to the worst case loss response in terms of value of information). We focus here on the situation in which the choices are represented explicitly in a database, and with a model of user utility as a weighted sum of the criteria; in this case when the user makes a choice, an agent learns a linear constraint on the unknown vector of weights. We develop an algorithmic method for computing minimax setwise regret for this form of preference model, by making use of a SAT solver with cardinality constraints to prune the search space, and computing max setwise regret using an extreme points method. Our experimental results demonstrate the feasibility of the approach and the very substantial speed up over the state of the art.

ECAI Conference 2020 Conference Paper

Minimality and Comparison of Sets of Multi-Attribute Vectors

• Federico Toffano
• Nic Wilson

In a decision-making problem, there is often some uncertainty regarding the user preferences. We assume a parameterised utility model, where in each scenario we have a utility function over alternatives, and where each scenario represents a possible user preference model consistent with the input preference information. With a set A of alternatives available to the decision maker, we can consider the associated utility function, expressing, for each scenario, the maximum utility among the alternatives. We consider two main problems: firstly, finding a minimal subset of A that is equivalent to it, i. e. , that has the same utility function. We show that for important classes of preference models, the set of so-called possibly strictly optimal alternatives is the unique minimal equivalent subset. Secondly, we consider how to compare A to another set of alternatives B, where A and B correspond to different initial decision choices. We derive mathematical results that allow different computational techniques for these two problems, using linear programming, and especially, with a novel approach using the extreme points of the epigraph of the utility function.

ECAI Conference 2020 Conference Paper

Voting Rules from Random Relations

• Nic Wilson

We consider a way of generating voting rules based on a random relation, the winners being alternatives that have the highest probability of being supported. We define different notions of support, such as whether an alternative dominates the other alternatives, or whether an alternative is undominated, and we consider structural assumptions on the form of the random relation, such as being acyclic, asymmetric, connex or transitive. We give sufficient conditions on the supporting function for the associated voting rule to satisfy various properties such as Pareto and monotonicity. The random generation scheme involves a parameter p between zero and one. Further voting rules are obtained by tending p to zero, and by tending p to one, and these limiting rules satisfy a homogeneity property, and, in certain cases, Condorcet consistency. We define a language of supporting functions based on eight natural properties, and categorise the different rules that can be generated for the limiting p cases.

AAMAS Conference 2019 Conference Paper

Generating Voting Rules from Random Relations

• Nic Wilson

We consider a way of generating voting rules based on a random relation, the winners being alternatives that have the highest probability of being supported. We consider different notions of support, such as whether an alternative dominates the other alternatives, or whether an alternative is undominated, and we consider structural assumptions on the form of the random relation, such as being acyclic, asymmetric, connex or transitive. We give sufficient conditions on the supporting function for the associated voting rule to satisfy various properties such as Pareto and monotonicity. The random generation scheme involves a parameter p between zero and one. Further voting rules are obtained by tending p to zero, and by tending p to one, and these limiting rules satisfy a homogeneity property, and, in certain cases, Condorcet consistency. We define a language of supporting functions based on eight natural properties, and categorise the different rules that can be generated for the limiting p cases.

IJCAI Conference 2017 Conference Paper

Dominance and Optimisation Based on Scale-Invariant Maximum Margin Preference Learning

• Mojtaba Montazery
• Nic Wilson

In the task of preference learning, there can be natural invariance properties that one might often expect a method to satisfy. These include (i) invariance to scaling of a pair of alternatives, e. g. , replacing a pair (a, b) by (2a, 2b); and (ii) invariance to rescaling of features across all alternatives. Maximum margin learning approaches satisfy such invariance properties for pairs of test vectors, but not for the preference input pairs, i. e. , scaling the inputs in a different way could result in a different preference relation. In this paper we define and analyse more cautious preference relations that are invariant to the scaling of features, or inputs, or both simultaneously; this leads to computational methods for testing dominance with respect to the induced relations, and for generating optimal solutions among a set of alternatives. In our experiments, we compare the relations and their associated optimality sets based on their decisiveness, computation time and cardinality of the optimal set. We also discuss connections with imprecise probability.

IJCAI Conference 2017 Conference Paper

Efficient Inference and Computation of Optimal Alternatives for Preference Languages Based On Lexicographic Models

• Nic Wilson
• Anne-Marie George

We analyse preference inference, through consistency, for general preference languages based on lexicographic models. We identify a property, which we call strong compositionality, that applies for many natural kinds of preference statement, and that allows a greedy algorithm for determining consistency of a set of preference statements. We also consider different natural definitions of optimality, and their relations to each other, for general preference languages based on lexicographic models. Based on our framework, we show that testing consistency, and thus inference, is polynomial for a specific preference language which allows strict and non-strict statements, comparisons between outcomes and between partial tuples, both ceteris paribus and strong statements, and their combination. Computing different kinds of optimal sets is also shown to be polynomial; this is backed up by our experimental results.

AAAI Conference 2017 Conference Paper

Multi-Objective Influence Diagrams with Possibly Optimal Policies

• Radu Marinescu
• Abdul Razak
• Nic Wilson

The formalism of multi-objective influence diagrams has recently been developed for modeling and solving sequential decision problems under uncertainty and multiple objectives. Since utility values representing the decision maker’s preferences are only partially ordered (e. g. , by the Pareto order) we no longer have a unique maximal value of expected utility, but a set of them. Computing the set of maximal values of expected utility and the corresponding policies can be computationally very challenging. In this paper, we consider alternative notions of optimality, one of the most important one being the notion of possibly optimal, namely optimal in at least one scenario compatible with the inter-objective tradeoffs. We develop a variable elimination algorithm for computing the set of possibly optimal expected utility values, prove formally its correctness, and compare variants of the algorithm experimentally.

FLAP Journal 2017 Journal Article

Preference Inference Based on Hierarchical and Simple Lexiographic Models.

• Nic Wilson
• Anne-Marie George
• Barry O'Sullivan

IJCAI Conference 2017 Conference Paper

Rescale-Invariant SVM for Binary Classification

• Mojtaba Montazery
• Nic Wilson

Support Vector Machines (SVM) are among the most well-known machine learning methods, with broad use in different scientific areas. However, one necessary pre-processing phase for SVM is normalization (scaling) of features, since SVM is not invariant to the scales of the features’ spaces, i. e. , different ways of scaling may lead to different results. We define a more robust decision-making approach for binary classification, in which one sample strongly belongs to a class if it belongs to that class for all possible rescalings of features. We derive a way of characterising the approach for binary SVM that allows determining when an instance strongly belongs to a class and when the classification is invariant to rescaling. The characterisation leads to a computation method to determine whether one sample is strongly positive, strongly negative or neither. Our experimental results back up the intuition that being strongly positive suggests stronger confidence that an instance really is positive.

IJCAI Conference 2016 Conference Paper

Preference Inference through Rescaling Preference Learning

• Nic Wilson
• Mojtaba Montazery

One approach to preference learning, based on linear support vector machines, involves choosing a weight vector whose associated hyperplane has maximum margin with respect to an input set of preference vectors, and using this to compare feature vectors. However, as is well known, the result can be sensitive to how each feature is scaled, so that rescaling can lead to an essentially different vector. This gives rise to a set of possible weight vectors - which we call the rescale-optimal ones - considering all possible rescalings. From this set one can define a more cautious preference relation, in which one vector is preferred to another if it is preferred for all rescale-optimal weight vectors. In this paper, we analyse which vectors are rescale-optimal, and when there is a unique rescale-optimal vector, and we consider how to compute the induced preference relation.

IJCAI Conference 2016 Conference Paper

Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models

• Anne-Marie George
• Nic Wilson
• Barry O'Sullivan

In this paper, we construct and compare algorithmic approaches to solve the Preference Consistency Problem for preference statements based on hierarchical models. Instances of this problem contain a set of preference statements that are direct comparisons (strict and non-strict) between some alternatives, and a set of evaluation functions by which all alternatives can be rated. An instance is consistent based on hierarchical preference models, if there exists an hierarchical model on the evaluation functions that induces an order relation on the alternatives by which all relations given by the preference statements are satisfied. Deciding if an instance is consistent is known to be NP-complete for hierarchical models. We develop three approaches to solve this decision problem. The first involves a Mixed Integer Linear Programming (MILP) formulation, the other two are recursive algorithms that are based on properties of the problem by which the search space can be pruned. Our experiments on synthetic data show that the recursive algorithms are faster than solving the MILP formulation and that the ratio between the running times increases extremely quickly.

IJCAI Conference 2015 Conference Paper

Computation and Complexity of Preference Inference Based on Hierarchical Models

• Nic Wilson
• Anne-Marie George
• Barry O'Sullivan

Preference Inference involves inferring additional user preferences from elicited or observed preferences, based on assumptions regarding the form of the user’s preference relation. In this paper we consider a situation in which alternatives have an associated vector of costs, each component corresponding to a different criterion, and are compared using a kind of lexicographic order, similar to the way alternatives are compared in a Hierarchical Constraint Logic Programming model. It is assumed that the user has some (unknown) importance ordering on criteria, and that to compare two alternatives, firstly, the combined cost of each alternative with respect to the most important criteria are compared; only if these combined costs are equal, are the next most important criteria considered. The preference inference problem then consists of determining whether a preference statement can be inferred from a set of input preferences. We show that this problem is coNP-complete, even if one restricts the cardinality of the equal-importance sets to have at most two elements, and one only considers non-strict preferences. However, it is polynomial if it is assumed that the user’s ordering of criteria is a total ordering; it is also polynomial if the sets of equally important criteria are all equivalence classes of a given fixed equivalence relation. We give an efficient polynomial algorithm for these cases, which also throws light on the structure of the inference.

IJCAI Conference 2015 Conference Paper

Computing Possibly Optimal Solutions for Multi-Objective Constraint Optimisation with Tradeoffs

• Nic Wilson
• Abdul Razak
• Radu Marinescu

Computing the set of optimal solutions for a multiobjective constraint optimisation problem can be computationally very challenging. Also, when solutions are only partially ordered, there can be a number of different natural notions of optimality, one of the most important being the notion of Possibly Optimal, i. e. , optimal in at least one scenario compatible with the inter-objective tradeoffs. We develop an AND/OR Branch-and-Bound algorithm for computing the set of Possibly Optimal solutions, and compare variants of the algorithm experimentally.

ECAI Conference 2014 Conference Paper

Preference Inference Based on Lexicographic Models

• Nic Wilson

With personalisation becoming more prevalent, it can often be useful to be able to infer additional preferences from input user preferences. Preference inference techniques assume a set of possible user preference models, and derive inferences that hold in all models satisfying the inputs; the more restrictive one makes the set of possible user preference models, the more inferences one gets. Sometimes it can be useful to have an adventurous form of preference inference when the input information is relatively weak, for example, in a conversational recommender system context, to give some justification for showing some options before others. This paper considers an adventurous inference based on assuming that the user preferences are lexicographic, and also an inference based on an even more restrictive preference model. We show how preference inference can be efficiently computed for these cases, based on a relatively general language of preference inputs.

KR Conference 2012 Conference Paper

An Axiomatic Framework for Influence Diagram Computation with Partially Ordered Utilities

• Nic Wilson
• Radu Marinescu

For a standard influence diagram we have both chance and decision variables, and we eliminate chance variables with a sum operator, and decision variables with a max operator. We can compute the maximum expected utility N by applying a sequence of sum and max eliminations to Θ, eliminating all the variables. Performing combinations leads to functions involving larger sets of variables, which is expensive in terms of both computational cost and time. One therefore would like to delay performing computations where possible. Thus, P when eliminating a variable X, with, for example, the operator, one transforms Θ to a collection Θ0, which includes only functions P N N 0 that don’t involve X, and is such that X (Θ) = Θ. Crucially, the functions in Θ that don’t involve X are left unchanged, so still appear in Θ0. This paper presents an axiomatic framework for influence diagram computation, which allows reasoning with partially ordered values of utility. We show how an algorithm based on sequential variable elimination can be used to compute the set of maximal values of expected utility (up to an equivalence relation). Formalisms subsumed by the framework include decision making under uncertainty based on multi-objective utility, or on interval-valued utilities, as well as a more qualitative decision theory based on order-of-magnitude probabilities and utilities.

ECAI Conference 2012 Conference Paper

Importance-based Semantics of Polynomial Comparative Peference Inference

• Nic Wilson

A basic task in preference reasoning is inferring a preference between a pair of outcomes (alternatives) from an input set of preference statements. This preference inference task for comparative preferences has been shown to be computationally very hard for the standard kind of inference. Recently, a new kind of preference inference has been developed, which is polynomial for relatively expressive preference languages, and has the additional property of being much less conservative; this can be a major advantage, since it will tend to make the number of undominated outcomes smaller. It derives from a semantics where models are weak orders that are generated by objects called cp-trees, which represent a kind of conditional lexicographic order. We show that there are simple conditions, based on the notion of importance, that determine whether a weak order can be generated by a cp-tree of the given form. This enables a simple characterisation of the less conservative preference inference. We go on to study the importance properties satisfied by a simple kind of cp-tree, leading to another characterisation of the corresponding preference inference.

UAI Conference 2012 Conference Paper

Multi-objective Influence Diagrams

• Radu Marinescu 0002
• Abdul Razak
• Nic Wilson

We describe multi-objective influence diagrams, based on a set of p objectives, where utility values are vectors in Rp , and are typically only partially ordered. These can still be solved by a variable elimination algorithm, leading to a set of maximal values of expected utility. If the Pareto ordering is used this set can often be prohibitively large. We consider approximate representations of the Pareto set based on ǫ-coverings, allowing much larger problems to be solved. In addition, we define a method for incorporating user tradeoffs, which also greatly improves the efficiency.

AIJ Journal 2011 Journal Article

Computational techniques for a simple theory of conditional preferences

• Nic Wilson

A simple logic of conditional preferences is defined, with a language that allows the compact representation of certain kinds of conditional preference statements, a semantics and a proof theory. CP-nets and TCP-nets can be mapped into this logic, and the semantics and proof theory generalise those of CP-nets and TCP-nets. The system can also express preferences of a lexicographic kind. The paper derives various sufficient conditions for a set of conditional preferences to be consistent, along with algorithmic techniques for checking such conditions and hence confirming consistency. These techniques can also be used for totally ordering outcomes in a way that is consistent with the set of preferences, and they are further developed to give an approach to the problem of constrained optimisation for conditional preferences.

UAI Conference 2011 Conference Paper

Order-of-Magnitude Influence Diagrams

• Radu Marinescu 0002
• Nic Wilson

KR Conference 2010 Conference Paper

From preference logics to preference languages, and back

• Meghyn Bienvenu
• Jérôme Lang
• Nic Wilson

show in the paper, some well-known preference languages Preference logics and AI preference representation languages are both concerned with reasoning about preferences on combinatorial domains, yet so far these two streams of research have had little interaction. This paper contributes to the bridging of these areas. We start by constructing a “prototypical” preference logic, which combines features of existing preference logics, and then we show that many well-known preference languages, such as CP-nets and its extensions, are natural fragments of it. After establishing useful characterizations of dominance and consistency in our logic, we study the complexity of satisfiability in the general case as well as for meaningful fragments, and we study the expressive power as well as the relative succinctness of some of these fragments.

ECAI Conference 2010 Conference Paper

Improving the Global Constraint SoftPrec

• David Lesaint
• Deepak Mehta 0001
• Barry O'Sullivan
• Luis Quesada 0001
• Nic Wilson

A soft global constraint SOFTPREC has been proposed recently for solving optimisation problems involving precedence relations. In this paper we present new pruning rules for this global constraint. We introduce a pruning rule that improves propagation from the objective variable to the decision variables, which is believed to be harder to achieve. We further introduce a pruning rule based on linear programming, and thereby make SOFTPREC a hybrid of constraint programming and linear programming. We present results demonstrating the efficiency of the pruning rules.

IJCAI Conference 2009 Conference Paper

• Nic Wilson

A fundamental task for reasoning with preferences is the following: given input preference information from a user, and outcomes α and β, should we infer that the user will prefer α to β? For CP-nets and related comparative preference formalisms, inferring a preference of α over β using the standard definition of derived preference appears to be extremely hard, and has been proved to be PSPACEcomplete in general for CP-nets. Such inference is also rather conservative, only making the assumption of transitivity. This paper defines a less conservative approach to inference which can be applied for very general forms of input. It is shown to be efficient for expressive comparative preference languages, allowing comparisons between arbitrary partial tuples (including complete assignments), and with the preferences being ceteris paribus or not.

IJCAI Conference 2009 Conference Paper

• David Lesaint
• Deepak Mehta
• Barry O’Sullivan
• Luis Quesada
• Nic Wilson

Hard and soft precedence constraints play a key role in many application domains. In telecommunications, one application is the configuration of callcontrol feature subscriptions where the task is to sequence a set of user-selected features subject to a set of hard (catalogue) precedence constraints and a set of soft (user-selected) precedence constraints. When no such consistent sequence exists, the task is to find an optimal relaxation by discarding some features or user precedences. For this purpose, we present the global constraint SOFTPREC. Enforcing Generalized Arc Consistency (GAC) on SOFT- PREC is NP-complete. Therefore, we approximate GAC based on domain pruning rules that follow from the semantics of SOFTPREC; this pruning is polynomial. Empirical results demonstrate that the search effort required by SOFTPREC is up to one order of magnitude less than the previously known best CP approach for the feature subscription problem. SOFTPREC is also applicable to other problem domains including minimum cutset problems for which initial experiments confirm the interest.

ECAI Conference 2008 Conference Paper

A BDD Approach to the Feature Subscription Problem

• Tarik Hadzic
• David Lesaint
• Deepak Mehta 0001
• Barry O'Sullivan
• Luis Quesada 0001
• Nic Wilson

Modern feature-rich telecommunications services offer significant opportunities to human users. To make these services more usable, facilitating personalisation is very important since it enhances the users' experience considerably. However, regardless how service providers organise their catalogues of features, they cannot achieve complete configurability due to the existence of feature interactions. Distributed Feature Composition (DFC) provides a comprehensive methodology, underpinned by a formal architecture model to address this issue. In this paper we present an approach based on using Binary Decision Diagrams (BDD) to find optimal reconfigurations of features when a user's preferences violate the technical constraints defined by a set of DFC rules. In particular, we propose hybridizing constraint programming and standard BDD compilation techniques in order to scale the construction of a BDD for larger size catalogues. Our approach outperforms the standard BDD techniques by reducing the memory requirements by as much as five orders-of-magnitude and compiles the catalogues for which the standard techniques ran out of memory.

ECAI Conference 2008 Conference Paper

An Efficient Deduction Mechanism for Expressive Comparative Preferences Languages

• Nic Wilson

ECAI Conference 2006 Conference Paper

An Efficient Upper Approximation for Conditional Preference

• Nic Wilson

The fundamental operation of dominance testing, i. e. , determining if one alternative is preferred to another, is in general very hard for methods of reasoning with qualitative conditional preferences such as CP-nets and conditional preference theories (CP-theories). It is therefore natural to consider approximations of preference, and upper approximations are of particular interest, since they can be used within a constraint optimisation algorithm to find some of the optimal solutions. Upper approximations for preference in CP-theories have previously been suggested, but they require consistency, as well as strong acyclicity conditions on the variables. We define an upper approximation of conditional preference for which dominance checking is efficient, and which can be applied very generally for CP-theories.

ECAI Conference 2004 Conference Paper

Consistency and Constrained Optimisation for Conditional Preferences

• Nic Wilson

AAAI Conference 2004 Conference Paper

Extending CP-Nets with Stronger Conditional Preference Statements

• Nic Wilson

A logic of conditional preferences is defined, with a language which allows the compact representation of certain kinds of conditional preference statements, a semantics and a proof theory. CP-nets can be expressed in this language, and the semantics and proof theory generalise those of CP-nets. Despite being substantially more expressive, the formalism maintains important properties of CP-nets; there are simple sufficient conditions for consistency, and, under these conditions, optimal outcomes can be efficiently generated. It is also then easy to find a total order on outcomes which extends the conditional preference order, and an approach to constrained optimisation can be used which generalises a natural approach for CP-nets. Some results regarding the expressive power of CP-nets are also given.

ECAI Conference 2004 Conference Paper

Job Shop Scheduling with Probabilistic Durations

• J. Christopher Beck
• Nic Wilson

ECAI Conference 2004 Conference Paper

Soft Constraints with Partially Ordered Preferences

• Nic Wilson

ECAI Conference 2004 Conference Paper

Uncertain Linear Constraints

• Nic Wilson

ECAI Conference 1996 Conference Paper

Extended Probability

• Nic Wilson

ECAI Conference 1996 Conference Paper

Fast Markov Chain Algorithms for Calculating Dempster-Shafer Belief

• Nic Wilson
• Serafín Moral

UAI Conference 1995 Conference Paper

An Order of Magnitude Calculus

• Nic Wilson

This paper develops a simple calculus for order of magnitude reasoning. A semantics is given with soundness and completeness results. Order of magnitude probability functions are easily defined and turn out to be equivalent to kappa functions, which are slight generalizations of Spohn's Natural Conditional Functions. The calculus also gives rise to an order of magnitude decision theory, which can be used to justify an amended version of Pearl's decision theory for kappa functions, although the latter is weaker and less expressive.

ECAI Conference 1994 Conference Paper

A Logical View of Probability

• Nic Wilson
• Serafín Moral

UAI Conference 1994 Conference Paper

Generating Graphoids from Generalised Conditional Probability

• Nic Wilson

We take a general approach to uncertainty on product spaces, and give sufficient conditions for the independence structures of uncertainty measures to satisfy graphoid properties. Since these conditions are arguably more intuitive than some of the graphoid properties, they can be viewed as explanations why probability and certain other formalisms generate graphoids. The conditions include a sufficient condition for the Intersection property which can still apply even if there is a strong logical relations hip between the variables. We indicate how these results can be used to produce theories of qualitative conditional probability which are semi-graphoids and graphoids.

UAI Conference 1993 Conference Paper

The Assumptions Behind Dempster's Rule

• Nic Wilson

This paper examines the concept of a combination rule for belief functions. It is shown that two fairly simple and apparently reasonable assumptions determine Dempster's rule, giving a new justification for it.

UAI Conference 1991 Conference Paper

A Monte-Carlo Algorithm for Dempster-Shafer Belief

• Nic Wilson

A very computationally-efficient Monte-Carlo algorithm for the calculation of Dempster-Shafer belief is described. If Bel is the combination using Dempster's Rule of belief functions Bel, ..., Bel,7, then, for subset b of the frame C), Bel(b) can be calculated in time linear in 1(31 and m (given that the weight of conflict is bounded). The algorithm can also be used to improve the complexity of the Shenoy-Shafer algorithms on Markov trees, and be generalised to calculate Dempster-Shafer Belief over other logics.