4.1 Origine

L’origine des réseaux à préférences est la théorie des mariages stables proposée par Gale et Shapley. La plus ludique version de ce problème apparaît dès l’article original de [38] : il s’agit de marier des hommes et des femmes en faisant en sorte d’éviter tout risque d’adultère. Formellement, une instance du problème des mariages stables est constituée de deux ensembles et (les hommes et les femmes), chacun classant strictement un sous-ensemble des membres du sexe opposé. Une configuration de cette instance est tout simplement un couplage entre et . Elle est instable s’il existe un couple n’appartenant pas à la configuration, tel que préfère à sa partenaire dans la configuration (ou si est célibataire, que accepte d’être avec ), et réciproquement. Si cela se produit, l’adultère n’est pas loin, car et ont tout deux intérêt à se mettre ensemble, même si cela signifie la fin de leur couple actuel. À partir de cette définition, l’objectif de la théorie est d’identifier les configurations stables d’une instance donnée. Il a été prouvé dès que si les préférences sont strictes (pas d’hésitations dans les classements), il existe toujours une configuration stable, que l’on peut facilement obtenir par l’algorithme du bal [38].

Une première extension du problème est celui du recrutement des Maîtres de Conférences (college admission ou hospitals/residents en anglais [43, 66]). Dans cette variante, les membres de l’un des ensembles peuvent choisir plusieurs représentants de l’ensemble opposé. Par exemple, une université peut ouvrir plusieurs postes de Maître de Conférence chaque année, mais un futur maître de conférence n’ira qu’à une seule université. Comme pour le problème du mariage stable, il est toujours possible d’obtenir une configuration stable, et certains algorithmes proposés par Gale et Shapley sont toujours en vigueur dans nombre de processus de recrutement.

Mais pour le P2P, l’extension intéressante est celle où il n’y a qu’une seule catégorie de participants. Cette variante unisexe est connue sous le nom du problème des camarades de chambre (roommates) dans le cas du couplage simple, et -couplage (-matching) dans le cas général, étant la notation standard pour le vecteur décrivant les quotas du multi-couplage [31, 42, 44]. Le mariage unisexe trouve des applications dans de nombreux domaines, l’une des variantes les plus actives étant les échanges de donneurs de rein (pairwise kidneys exchange program) [67, 80]. La principale difficulté par rapport aux mariages sexués est qu’il n’est plus possible de garantir l’existence d’une configuration stable, ce qui peut s’avérer problématique, en particulier quand il s’agit de dons d’organe.

4.1.1 Réinventer la roue ?

Intuitivement, l’intérêt des théories de mariage pour le P2P est assez évident : si l’on a un ensemble de pairs, chacun possédant une liste de voisins avec lesquels il est susceptible d’interagir, la théorie devrait pouvoir nous éclairer sur ce qui se passe en supposant que chaque pair agit en fonction de son propre intérêt (i.e. de ses propres préférences).

Comme les théories des mariages existent depuis près de ans, on pourrait penser qu’il suffit de prendre la littérature existante pour avoir l’outil idéal de modélisation P2P. En pratique, les choses ne sont pas aussi simples : les théories des mariages offrent effectivement un bagage théorique extrêmement puissant, mais les spécificités liées au P2P nécessitent de voir le problème sous un nouvel angle, celui des réseaux à préférences, qui sont l’objet de ce chapitre.

Plus précisément, les principaux changements apportés par les réseaux à préférences sont les suivants :

• les préférences des problèmes classiques de -couplage sont souvent arbitraires, alors qu’en P2P, la plupart des préférences sont dérivées à partir de mesures objectives ;
• l’existence de configurations stables et les moyens de les obtenir sont une composante essentielle des problèmes de -couplage ; à l’inverse, la plupart des préférences P2P bénéficient d’un puissant théorème d’existence/unicité/convergence qui rend ces questions hors de propos ;
• les questions de dynamique et de performance des configurations sont un aspect fondamental pour le P2P, et doivent donc être mises en avant.