De la manipulation dans les systèmes multi-agents : une étude sur les jeux hédoniques et les systèmes de réputation
Institution:
CaenDisciplines:
Directors:
Abstract EN:
In this thesis, we study the robustness of multi-agent systems to strategic behaviors, namely manipulations. We consider in this manuscript two families of systems, hedonic games and reputation systems, which have complementary properties that allow to adress a broad range of questions. In the domain of hedonic games, we propose an analysis metholody which consists in studying the necessary minimal conditions to implement manipulations in an efficient way. To this end, we identify three minimal manipulations based on false preference profiles and false identities, and we study their efficiency on three canonical solution concepts that satisfy individual rationality (Nash stability, individual stability and core stability). By both theoretical and empirical results, we proved that Nash stability is robust to manipulations, unlike individual and core stability. In the domain of reputation systems, we propose to model reputation systems and the associated decision problem with a multiarmed bandit. Firstly, we show by an empirical study that using multiarmed bandit policies with an exploration faction tuned with respect to the reputation system reduces interactions with malicious agents and increases the cost of manipulations. Secondly, we propose a new credibility assessment based on the Kullback-Leibler divergence and the estimation error of the agents that allow to detect and filter false feedbacks.
Abstract FR:
Cette thèse porte sur la robustesse des systèmes multi-agents aux comportements stratégiques, génériquement appelés manipulations. Nous considérons dans ce manuscrit deux familles de systèmes, les jeux de coalitions hédoniques et les systèmes de réputation, dont les propriétés complémentaires permettent d'aborder une large gamme de questions. Dans le domaine des jeux de coalitions hédoniques, nous proposons une méthode d'analyse consistant à étudier les conditions minimales nécessaires à la mise en œuvre de manipulations efficaces. Pour cela, nous identifions trois manipulations minimales mêlant faux profils de préférences et fausses identités et étudions leur efficacité sur trois concepts de solution individuellement rationnels (stabilité au sens de Nash, au sens du cœur et stabilité individuelle). Par une étude tant théorique qu'empirique, nous montrons que la stabilité au sens de Nash est robuste aux manipulations contrairement à la stabilité individuelle et la stabilité au sens du cœur. Dans le domaine des systèmes de réputation, nous proposons de modéliser un système de réputation et le problème de décision associé par un problème de bandits manchots. Par une étude empirique, nous montrons dans un premier temps qu'utiliser des politiques de sélection ayant une facteur d'exploration adapté au système de réputation réduit les interactions avec des agents manipulateurs et augmentent le coût des manipulations. Dans un second temps, nous proposons une nouvelle mesure de crédibilité fondée sur la divergence de Kullback-Leibler et sur l'erreur d'estimation des agents pour détecter puis filtrer les faux témoignages.