Nic Wilson: On the Number of Queries Required to Determine an Optimal Alternative

Tuesday 20 January 2026 at 15:30 in room Espace One

Speaker: Nic Wilson (University College Cork)

Title: On the Number of Queries Required to Determine an Optimal Alternative

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