Nic Wilson
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Nic Wilson has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Anne-Marie George
University of Oslo
4 shared publications - Federico Toffano
University College Cork
4 shared publications - Barry O'Sullivan
University College Cork, Ireland
2 shared publications - Mojtaba Montazery
Insight Centre for Data Analytics, School of Computer Science and IT, University College Cork, Ireland
2 shared publications - Steven Prestwich
University College Cork
2 shared publications Didier Dubois
IRIT-CNRS Université Paul Sabatier
1 shared publication
Latest Publications
- Open Access
- 21 October 2025
- Published by IOS Press
- p. 525-532
On the Number of Queries Required to Determine an Optimal Alternative
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.
- 21 October 2025
- Published by IOS Press
- p. 525-532
Open AccessOn the Number of Queries Required to Determine an Optimal Alternative
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.
- Open Access
Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models
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.
Open AccessTowards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models
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.
- Open Access
Efficient Inference and Computation of Optimal Alternatives for Preference Languages Based On Lexicographic Models
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 LpqT, 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.
Open AccessEfficient Inference and Computation of Optimal Alternatives for Preference Languages Based On Lexicographic Models
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 LpqT, 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.
- Open Access
- 16 October 2024
- Published by IOS Press
- p. 3348-3355
Scale-Invariant Variations of Max Regret
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.
- 16 October 2024
- Published by IOS Press
- p. 3348-3355
Open AccessScale-Invariant Variations of Max Regret
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.
- Open Access
Computation and Complexity of Preference Inference Based on Hierarchical Models
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.
Open AccessComputation and Complexity of Preference Inference Based on Hierarchical Models
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.
- Open Access
- 29 March 2024
- Published by Elsevier in International Journal of Approximate Reasoning
- Vol. 171
A statistical approach to learning constraints
- 29 March 2024
- Published by Elsevier in International Journal of Approximate Reasoning
- Vol. 171
Open AccessA statistical approach to learning constraints
- 19 November 2023
- Published by Springer Nature
- p. 308-321
An Efficient Non-Bayesian Approach for Interactive Preference Elicitation Under Noisy Preference Models
- 19 November 2023
- Published by Springer Nature
- p. 308-321
An Efficient Non-Bayesian Approach for Interactive Preference Elicitation Under Noisy Preference Models
- Open Access
- 28 September 2023
- Published by IOS Press
- p. 2647-2654
Enforcing Natural Properties of Choice Functions, with Application for Combination
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.
- 28 September 2023
- Published by IOS Press
- p. 2647-2654
Open AccessEnforcing Natural Properties of Choice Functions, with Application for Combination
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.
- Open Access
- 28 September 2023
- Published by IOS Press
- p. 2639-2646
On the Variation of Max Regret with Respect to the Scaling of the Objectives
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.
- 28 September 2023
- Published by IOS Press
- p. 2639-2646
Open AccessOn the Variation of Max Regret with Respect to the Scaling of the Objectives
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.
- Open Access
- 13 August 2022
- Published by Springer Nature in Autonomous Agents and Multi-Agent Systems
- Vol. 36 (2) , 1-66
Minimality and comparison of sets of multi-attribute vectors
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.- 13 August 2022
- Published by Springer Nature in Autonomous Agents and Multi-Agent Systems
- Vol. 36 (2) , 1-66
Open AccessMinimality and comparison of sets of multi-attribute vectors
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.