Preference reasoning and aggregation over combinatorial domains in uncertain and multi-agent scenarios

Preferences, intended as user opinions over items, are conspicuously present in our lives and recently became widely studied in Artificial Intelligence. In many contexts of our life, we do not consider items only as entire entities, but we consider a set of features/attributes that characterize them and that interact to each other. Therefore, we are particularly interested in this kind of scenarios representing conditional preferences over combinatorial and multi attribute domains. The ability of representing preferences in a compact way is essential, especially in the context of multi-attribute preference modelling and reasoning since it causes combinatorial explosion of information and a high computational cost. For this purpose, a number of compact representation languages have been developed in the literature. We initially focus on a recently developed frame- work for representing conditional preferences over a graphical structure: conditional preference networks (CP-nets). We analyse the advantages and the drawbacks of CP-nets focusing on uncertain and multi-agent scenarios. Real life scenarios are often dynamic and uncertain: a user can change her mind over time and her preferences could be affected by errors or noise. We propose the new PCP-net structure (probabilistic conditional preference networks), as a generalisation of the CP-nets framework, able to respond to change through updates and to support probabilistic informations. PCP-nets can be used also to represent a multi-agent scenario where each agent is represented by a CP-net and probabilities are used to reconcile conflicts between users. We analyse another compact representation language, similar to CP-nets, namely soft con- straints. Soft constraints are less restrictive, with respect to CP-nets, but the computational complexity remains almost the same for the main tasks. For this reason, we rethink the multi-agent context by using a profile of agents expressing their preferences via soft constraints, instead of via a collection of CP-nets aggregated into a PCP-net. The CP-nets literature presents also many other generalisations, since CP-nets are restrictive and limited in expressiveness. For example, CP-nets have been extended with constraints, with local inconsistency and incompleteness (GCP-nets), with utility functions (UCP-nets), etc. Therefore, several different frameworks were developed to describe conditional preferences. Each of these formalisms have ad hoc syntax, semantics and specialised algorithms. In this thesis, we specify a new framework with an unification purpose of all these models. The strength of our formulation is the direct expression of the model in the standard first order logic, as constrained Datalog theories. This formulation is rich enough to express CP-nets and all its extensions. We conclude this work, studying an application of preferences in a real-life scenario. We analyse how to improve kidney exchanging algorithms increasing the number of transplantations and the expected life duration, providing some encouraging results. Then we provide also some preliminary ideas about how to incorporate preferences in the matching procedure currently used.

Le preferenze, intese come opinioni di utenti su un insieme di oggetti, sono ampiamente presenti nelle nostre vite e recentemente sono diventate molto studiate in Intelligenza Artificiale. In molti contesti della nostra vita, non consideriamo gli oggetti come entità atomiche, ma consideriamo un insieme di caratteristiche/attributi che le caratterizzano e che interagiscono tra di loro. Siamo dunque particolarmente interessati in questi tipi di scenario: preferenze condizionali su domini combinatori e multi-attributo. L’abilità di rappresentare le preferenze in maniera compatta è essenziale, in particolare nel contesto di modellazione e ragionamento con preferenze multi-attributo, in presente un esplosione combinatoria di informazione che causa un alto costo computazionale. A questo scopo sono state sviluppate in letteratura una serie di linguaggi di rappresentazione compatta. In questa tesi ci focalizziamo inizialmente su un modello grafico di rappresentazione delle preferenze condizionali: le conditional preference networks (CP-nets). Analizziamo quindi i vantaggi e gli svantaggi delle CP-net concentrandoci su scenari incerti e multi-agente. Gli scenari reali sono spesso dinamici e incerti: un utente può cambiare le sue idee nel tempo e le sue preferenze potrebbero essere affette da errori o rumore. In questa tesi proponiamo una nuova strutture chiamata PCP-net (probabilistic conditional preference networks), generalizzazione delle CP-net, capace di rispondere ai cambiamenti attraverso aggiornamenti e di supportare informazione probabilistica. Le PCP-net possono essere usate anche per rappresentare i contesti multi-agente dove ogni agente è rappresentato da una CP-net e le probabilità vengono usate per riconciliare i conflitti tra gli utenti. In questa tesi analizziamo anche un altro linguaggio di rappresentazione compatta, simile alle CP-net: i vincoli soft. I vincoli soft sono meno restrittivi rispetto alle CP-net, ma le complessità computazionali rimangono le stesse per i task principali. Per questo motivo, ripensiamo lo scenario multi-agente usando un profilo di agenti che esprimono le loro preferenze attraverso vincoli soft, invece che tramite una collezione di CP-net poi aggregate in una PCP-net. La letteratura riguardante le CP-net presenta anche molte altre generalizzazioni, poichè le CP-net sono per certi versi restrittive e limitate nell’espressività. Ad esempio, le CP-net sono state estese con vincoli, con inconsistenza locale e incompletezza (GCP-net), con funzioni di utilità (UCP-net), etc. Sono dunque stati sviluppati molti formalismi differenti per descrivere le preferenze condizionali e ognuno di essi ha una sintassi e una semantica ah hoc e algoritmi specifici. In questa tesi specifichiamo un nuovo framework con lo scopo di unificare tutti questi modelli. La forza della nostra formulazione è la diretta espressione del modello in logica standard al primo ordine, come una teoria Datalog vincolata. Questa formulazione è ricca abbastanza da esprimere le CP-nets e tutte le sue estensioni. Concludiamo la tesi, studiando un applicazione delle preferenze in un scenario reale. Analizziamo come migliorare gli algoritmi di scambi di reni aumentando il numero di trapianti e di durata di vita aspettata, fornendo alcuni risultati incoraggianti. Quindi forniamo anche alcune idee preliminari riguardo a come incorporare le preferenze nelle procedure di matching attualmente utilizzate.