A game-theoretic approach to matching and robust inlier selection

Abstract

In questa tesi la nostra attenzione è rivolta alla classe di problemi di matching dove qualche funzione di compatibilità e definibile su un insieme di due o più coppie corrispondenti. Nello specifico proponiamo un approccio flessibile che sfrutta la teoria dei giochi per permettere l'evoluzione di un'iniziale popolazione di ipotesi verso uno stato evolutivamente stabile dove un ristretto insieme di corrispondenze altamente compatibili è riuscito a sopravvivere. La motivazione che spinge ad adottare tale approccio è duplice. Infatti da un punto di vista teorico è possibile dimostrare che in molte formulazioni di problemi gli stati evolutivamente stabili o gli equilibri di Nash corrispondono a configurazioni desiderabili della soluzione, quali ad esempio isomorfismi massimali o allineamenti ottimali di superfici. Inoltre sono disponibili in letteratura molti algoritmi efficienti per guidare il processo evolutivo e, come mostreremo con un'estensiva copertura sperimentale, persino le dinamiche più semplici permettono di condurre la popolazione iniziale verso un match ottimale. Applicando il nostro framework a diverse tipologie di scenario mostreremo la sua efficacia sia in contesti di matching pairwise, sia coinvolgendo compatibilità di ordine superiore.