EWG on Preference Handling

Advances in Preference Handling

Multidisciplinary Working Group affiliated to EURO

Quai de la Dorade Toulouse

The M-PREF 2022 talks have been all of high quality, showing that the field is very active and flourishing. And there is more in preparation!

Dec 16, 2022

M-PREF 2022: A MULTITUDE OF IMPRESSIONS

LinkedIn Group on Preference Handling
Mail to the Working Group on Advances in Preference Handling

What is the opposite of preferences? The opposite of a particular preference between two alternatives may be the inverse preference. For example, if we prefer speaking to writing, we may say that the opposite of this preference is preferring writing to speaking. But what is the opposite of the concept of preference? We may say that this is the absence of preference, that means indifference.

Indifference is often associated with this kind of bureaucratic behavior that is only concerned with achieving a goal by whatever means. A good example for this is the allocation of tasks to staff members while ignoring the preferences of the individual staff members. Not only this may lead to bad outcomes as the staff members may be frustrated by their job, it may also lead to strikes as it happened for airlines in the 1990s since the flight personnel had been unhappy about their time schedule and flight destinations. So the indifference about the preferences of captains has led to a situation about which the airline could no longer be indifferent.

Indeed you cannot succeed large societal projects by walking on the shoulders of the members of the society without taking their preferences into account and without giving them a voice. One remediation is to maximize social welfare, i.e. an aggregation of all preferences of the individual members. In the case of crew scheduling, this has led to the development and deployment of preferential bidding software.

However, this does not fix the indifference problem completely. When maximizing global welfare, some individuals may get their preferences satisfied whereas others don’t. So it still allows for an indifference with respect to the preferences of some individuals. Indeed, it is even worse. The preferences of some individuals get sacrificed and turned to their opposite in order to satisfy the preferences of others since otherwise not all resources will be allocated.

This situation is particularly problematic when individuals are comparing their assignments. For example, suppose some captain prefers overnight stops in Singapore to overnight stops in New York, but got assigned the latter. So this captain will envy colleagues who got the former.

Approaches to fair allocation seek to fix those kinds of issues. Fair allocation was difficult more than 20 years ago, but became a topic of intense research in areas such as computational social choice since then. It may now be a good time to put these results into practice for problems such as crew scheduling and others.

This topic of fairness in resource allocation played an important role at the 13th Multidisciplinary Workshop on Advances in Preference Handling. This workshop has been held as a hybrid event on July 23, 2022 in Vienna as part of the IJCAI 2022 workshop program. It has been organized by Meltem Öztürk, Paolo Viappiani, Christophe Labreuche, and Sébastien Destercke and the organizers have done a fantastic job. In spite of many parallel events, participation has been excellent with 27 participants onsite and 10 participants online. The program has been very dense and included three invited talks as well as nineteen regular presentations about topics such as combinatorial aspects of preferences, voting theory and computational social choice, logic and argumentation, and preference learning. The talks have been all of high quality, showing that the field is very active and flourishing.

The workshop started with the invited talk of Haris Aziz, UNSW Sydney about "Pareto Optimality: Computation and Characterizations". Haris investigated the computational complexity of testing Pareto-optimality for problems such as the discrete allocation of bundles of goods to agents. The preferences of the agents over goods can be expressed in different ways. Haris started with additive utility and lexicographical preferences, but also discussed preferences over lotteries and uncertain preferences.

The first regular session included five papers on combinatorial aspects of preferences. Reshef Meir examined methods for mitigating skewed bidding for conference paper matching. The main idea consists in promoting papers with few or no bids during the bidding process. In the next talk, Toby Walsh considered the design of mechanisms that assign facilities to agents based on the locations reported by the agents. Toby proposed new strategy-proof mechanisms and characterized them by new approximation measures. The third talk of this session was given by Linus Boes about collective combinatorial optimization. Linus expressed those problems as weighted judgement aggregation, which consist in choosing a subset of items that best suits the agent’s preferences according to some aggregation rule. Meijing Wang gave the next talk and showed how to learn users’ preferences by a sequence of questions that are generated by solving sub-modular set covering problems while ensuring that the questions fairly treat all aspects of the subject domain. After this, Agnes Rico discussed the role of set functions for preference modeling and observed that those set functions may be non-monotonic. Agnes then showed how to carry approximation methods for monotonic set functions over to non-monotonic ones.

The topic of the second section had been voting theory and computational social choice. Ariane Ravier considered subset selection under preferences formulated over subsets of up to size 2. Ariane elaborated an axiomatic characterization of ordinal dominance and studied the complexity of finding a non-dominated subset. After this, Sofia Simola examined whether preference profiles of voters can be represented by placing both voters and alternatives on a multi-dimensional grid. If a voter prefers an item to another one, the Manhattan distance between the voter and the first item should be smaller than that of the second item. In the next task, Jan Maly studied the computational complexity of participatory budget under new kinds of fairness notions. Each agent should receive a fair share of the budget in terms of the cost of a project divided by its number of supporters. The fourth talk of the session was given by Grzegorz Pierczyński, who discussed the election of core-stable committees. Each group of voters can decide about a number of committee members that is proportional to the group’s size. Grzegorz developed algorithms for computing those committees under different forms of preferences. In the final talk of the session, Farhad Mohsin studied the computational complexity of determining whether a voting problem suffers from the group no-show paradox, i.e. the abstention of voters with the purpose to make the winner more favorable to them. Farhad reported experimental results based on depth-first search as well as integer linear programming.

The second invited talk had been given by Rudolf Vetschera, University of Vienna about "Modeling negotiator behavior: Preferences, confidence and reciprocity". Rudolf presented a negotiation framework where AI agents negotiate with a human opponent while using an adequate model of human negotiation behavior. Rudolf identified three factors of such a model, namely the human’s preferences over the negotiated issues, the human’s confidence in achieving good results, and the human’s expectations about reciprocity of action

The third regular session consisted of two talks about logic and argumentation. Francis Ward introduced argumentative reward learning, which consists in defining an attack relation over trajectories sampled from a Markov decision process and in eliciting human preferences over those trajectories. Experiments with maze solving showed that this approach results into less overfitting and improved accuracy. Michael Bernreiter presented a Hintikka-style game-theoretic semantics for qualitative choice logic. Ordered disjunctions are modeled by a preference relation over the outcomes of game trees.

Andrea Passerini, University of Trento gave the third invited talk about "Constructive Preference Elicitation: from Product Bundling to Algorithmic Recourse". Andrea presented a variety of preference elicitation methods for configuration problems. The basic idea consists in constructing a solution and then asking the user to improve it. Andrea applied the elicitation methods to problems such as product bundling, housing, and algorithmic recourse. The latter consists in finding actions that will overturn an unfavorable outcome made by a machine learning decision support system.

The workshop continued with a regular session about preference learning, i.e. the learning of a preference model from examples. Yanxia Zhang proposed neural networks architectures for predicting preferences between pairs of choices. The methods are able to learn nonlinear interactions between features. The next talk, given by Nicholas Mattei, was about the learning of constraints over actions, occupancy, and features in Markov decision processes. This problem has been solved by a new form of inverse reinforcement learning. Nicholas Mattei had a second talk, namely about multi-alternative decision field theory, which models the human deliberation process preceding a choice. The talk proposed a recurrent neural network for learning the preferences of this deliberation process from the final choices only.

The last session was again about preference learning. Mohamed Ouaguenouni presented a cautious (i.e. robust) method for learning preferences within the generalized additive model while minimizing the maximal size of the factors as well as the number of factors. The cautious learning allows for the possibility that no preference between two alternatives can be predicted due to a lack of information. After this, Farhad Mohsin gave a second talk, namely about models of human priorities in moral dilemmas. Farhad reported that lexicographical preference models have a similar accuracy as complex machine learning models for the considered life jacket datasets while achieving a better interpretability. In the next talk, Margot Herin presented a method for learning a bipolar Choquet integral, which separates the evaluation of positive and negative consequences of a decision. The method first learns spline representations of marginal utilities and then determines a compact representation of capacities. The last talk of the workshop was given by Pierre François Giminez, who studied the sample and time complexity of learning lexicographical preference trees from a history of observed choices. This method can be considered an unsupervised kind of preference learning as it does not start with a set of comparisons, but a set of highly preferred alternatives.

This summary gives a short impression of the richness of the program. The papers can be found on the M-PREF 2022 web site. Some talks are available as video as well. As a follow-up of the workshop, the organizers are planning a special issue of the Annals of Mathematics and Artificial Intelligence on Recent Advances in Preference Handling.

FEB 2023

MAY 2023

JULY 2023

AUG 2023

OCT 2023

CALENDAR