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

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.