Allocazione Stabile ed Efficiente di Compiti nel Lavoro di Squadra

The present thesis focuses on matching models, in a Stable Roommate Problem style, aimed to represent problems of task assignment to pair of agents. We focus on matchings that guarantee Pareto efficiency and stability. The original notion of stability introduced by Gale and Shapley (1962) can not be applied directly in our settings, as it was defined only on preferences over possible partners, without taking in consideration tasks. Therefore, an ad-hoc notion of stability is defined for each model that we discuss. In every model we present, we show that a stable and Pareto efficient outcome exists for every admissible preference profile. Proofs of these existence results are constructive: we present algorithms whose outcome always respects stability and efficiency, plus other desirable properties that depend on the specific model.

La presente tesi si concentra su modelli di abbinamento, nel solco dello "Stable Roommate Problem", volti a rappresentare i problemi di assegnazione dei compiti a coppie di agenti. Ci si concentra sugli abbinamenti che garantiscono l'efficienza e la stabilità paretiana. La nozione originale di stabilità introdotta da Gale e Shapley (1962) non può essere applicata direttamente nelle nostre impostazioni, in quanto è stata definita solo su preferenze rispetto a possibili partner, senza prendere in considerazione i compiti. Pertanto, per ogni modello che discutiamo, viene definita una nozione ad hoc di stabilità. In ogni modello che presentiamo, dimostriamo che esiste un'allocazione stabile e Pareto-efficiente degli agenti e dei compiti per ogni profilo di preferenza ammissibile. Le dimostrazioni di questi risultati di esistenza sono costruttive: mostriamo algoritmi il cui prodotto soddisfa sempre stabilità ed efficienza, oltre ad altre proprietà desiderabili che dipendono dal modello specifico.