NWNic Wilson

Nic Wilson

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Nic Wilson has a total of 13 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    On the Number of Queries Required to Determine an Optimal Alternative

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

  • Open Access

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

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

  • Open Access

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

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

    Scale-Invariant Variations of Max Regret

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

  • Open Access

    Computation and Complexity of Preference Inference Based on Hierarchical Models

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

  • Open Access

    Enforcing Natural Properties of Choice Functions, with Application for Combination

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

  • Open Access

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

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

  • Open Access

    Minimality and comparison of sets of multi-attribute vectors

    by 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$$ 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$$ 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$$ A to another set of alternatives $$B$$ B , where $$A$$ A and $$B$$ 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.