Projet de recherche - 2012
Résolution distribuée des problèmes de mise en correspondance stable

Résumé

Ce travail s'intègre dans le projet de collaboration entre l'équipe SMAC du LIFL et le LISTI de l'École Nationale Supérieure des Mines de Saint-Etienne. L'objectif consiste à proposer une méthode de résolution distribuée des problèmes de mise en correspondance stable.

Localisation

Le travail sera réalisé au sein de l'équipe SMAC.

Rémunération

Environ 420 euros/mois.

Sujet

Contexte

Le travail proposé s'intéresse au problème de mise en correspondance stable. Cette problématique a été introduite dans [1], article qui a valu à Shapley le prix d'Économie de la banque de Suède en 2012, à travers le problème du mariage stable. Dans ce problème, on considère n individus d'une communauté (e.g la gent féminine) et n individus d'une autre communauté (e.g. la gent masculine). Chaque individu a des penchants pour les individus de l'autre partition avec lesquels il souhaite être apparié. Le but consiste alors à constituer un ensemble de n mariages monogames et hétérosexuels. Cet appariement doit être stable c'est-à-dire qu'il ne doit pas avoir de couple qui préférerait être ensemble plutôt qu'avec leur partenaire actuel. En d'autres termes, il ne doit pas exister de relation extra-congugale menaçant l'appariement.

Le travail proposé consiste à prôner une approche orientée individu pour la résolution de tels problèmes. Par exemple, l'agentification de l'algorithme séminal de Gale-Shapley [3] revient à distinguer deux comportements d'agents (proposant et disposant) qui négocient pour aboutir à une solution stable mais inéquitable. Nous avons proposé précédemment un comportement d'agent intitulé Casanova dans [2] qui consiste à jouer simultanément ces deux rôles dans une multitude de négociations bilatérales. Selon ce comportement, les agents mettent en oeuvre une stratégie de concession minimale maximisant leur bien-être individuel. Les solutions qui émergent sont équitables et elles ne peuvent pas être atteintes par les méthodes de résolution multi-agents existantes. De plus, notre résolution est décentralisée et elle préserve la privacité des préférences.

Objectif

L'objectif de ce stage consiste à proposer une méthode de résolution distribuée des problèmes de mise en correspondance stable dont on peut garantir la terminaison et la correction. Cet algorithme doit être adaptatif, anytime et préserver la privacité des préférences. La méthode proposée ainsi que les résultats obtenus doivent être comparées avec l'existant, comme par exemple la méthode SML [4].

Description du travail

Problème du mariage stable.

Dans le cadre du problème du mariage stable, l'objectif consite à proposer une version centralisée de Casanova afin de disposer d'une preuve de terminaison et de correction puis de distribuer cette résolution afin de la comparer avec l'existant.

Problème du mariage stable avec liste incomplète.

Dans un problème de mariage stable incomplet, au moins l'une des listes de préférence est incomplète. Le fait qu'une liste de préférences soit incomplète signifie que l'individu concerné préfère rester seul plutôt que d'être mal accompagné. Ainsi, certains appariements complets sont irrationnels car ils consistent à marier un individu à un partenaire qui n'est pas dans sa liste de préférences. L'objectif ici consiste à adapter Casanova pour ce type de problème. [1] a démontré qu'il existe toujours un appariement stable pour ce type de problème.

Problème des colocataires.

Ce problème diffère du problème des mariages stables par le fait que les individus ne sont pas séparés en deux ensembles, les hommes et les femmes, tels qu'un homme ne peut s'apparier qu'avec une femme et réciproquement. L'objectif ici consiste à adapter Casanova pour ce type de problème. Contrairement aux problèmes précédents, il n'existe pas toujours une solution.

Besoin

Le candidat doit être capable de comprendre et de modifier le prototype. À cette intention, il doit être familier avec l'environnement Linux/Unix, la programmation objet et (i.e. Java) et SVN.

Apports pour l'étudiant

Ce projet consiste en une initiation à la recherche.

Nombre d'étudiants

1

Environnement

Ce travail sera réalisé en Java sous Eclipse avec SVN.

Bibliographie

  • [1] Gale D., Shapley L. S. (1962). College admissions and the stability of marriage. American Mathematical Monthly, vol. 69, p. 9-14.
  • [2] Patricia Everaere, Maxime Morge, Gauthier Picard. Casanova : un comportement d'agent respectant la privacité pour des mariages stables et équitables. Revue d'Intelligence Artificielle, 2012 (À paraître).
  • [3] Brito, I. and Meseguer, P. Distributed Stable Matching Problems. Principles and Practice of Constraint Programming. Lecture Notes in Computer Science, Springer-Verlag, p152-166, 2005.
  • [4] Gelain, M. and Pini, M. S. and Rossi, F. and Venable, K. B. and Walsh, T. Local search algorithms on the Stable Marriage Problem: Experimental Studies. Proceedings of 19th European Conference on Artificial Intelligence, IOS Press, p 1085-1086, 2010.