---
tags: TD, Go
---

# [IA04] TD3 : Algorithmes d'appariement

| Information | Valeur |
| :------------ | :------------- |
| **Auteurs** | Khaled Belahcene ([e-mail]) |
| | Sylvain Lagrue ([[e-mail]](mailto:[e-mail]))|
| **Licence** | Creative Common [CC BY-SA 3.0](https://creativecommons.org/licenses/by-sa/3.0) |
| **Version document** | 0.5.1 |

En cours ont été présentées des notions de modélisation, ainsi que la situation suivante:
> ## Situation d'appariement
> * Deux groupes de même taille sont composés d'agents.
> * On cherche à apparier deux à deux ces agents de manière univoque.
> * chaque agent dispose de préférences quant aux agents de l'autre groupe

Les objectifs de cette séance sont :
* de formaliser cette situation sous forme de **problème(s)** dont on caractérise les entrées et les sorties: qu'est ce qu'une *instance* du problème ? Quelle *réponse* est attendue ?
* de formuler des **algorithmes** permettant de résoudre ces problèmes
* de **programmer** ces algorithmes dans le langage Go

## Le problème de l'appariement
Pour formaliser la situation d'appariement, il est nécessaire de préciser:
1. la représentation des préférences des agents
2. la notion d'appariement

Si, par la suite, on désire trouver un appariement possédant de "bonnes" propriétés, il faudra aussi les formaliser

## Les algorithmes d'appariement

#### AI - Acceptation Immédiate (a.k.a. "Boston")

L'un des deux groupes joue le rôle des *proposants*, l'autre des *disposants*
* chaque proposant propose à son 1e choix
* chaque disposant accepte son proposant préféré
* les proposants et disposants appariés sont retirés et on itère (on passe donc aux choix d'ordre 2, 3, ...)

#### AD - Acceptation Différée (Gale & Shapley, 1962)
Idem AI, mais les refus sont permanents alors que les acceptations sont *temporaires*

* tant qu'il reste un proposant non apparié:

- il propose aux disposants (même déjà appariés) qui ne lui ont pas déjà répondu "non"
- les disposants abordés répondent "non" si la proposition ne leur convient pas, ou bien "peut-être" si la proposition leur convient, en rejetant éventuellement leur partenaire actuel
* les propositions sont finalisées (les "peut-être" deviennent des "oui")

#### TTC - *Top Trading Cycles* (Gale - Shapley & Scarf, 1974 - Abdulkadiroglu & Sonmez, 2003)

Tant qu'il reste des agents libres (non appariés) :

* chaque agent du groupe $A$ pointe vers son agent libre préféré du groupe $B$
* chaque agent du groupe $B$ qui a reçu une offre pointe vers son agent libre préféré du groupe $A$
* identifier un *cycle d'échange*, i.e. une liste d'agents $a_1, \dots a_k, a_{k+1}=a_1$ telle que $a_{i+1}$ est pointé par l'agent pointé par $a_i$
* apparier chaque agent $a_i$ du cycle avec l'agent qu'il pointe

## Travail demandé

1. Proposer une représentation des préférences des agents. Formaliser le problème des appariements.
2. Récupérer sur moodle les éléments d'un programme en Go qui permet de créer une instance aléatoire (ou non) du problème.
3. Programmer l'algorithme AI. Vérifier qu'il ne garantit pas la *stabilité* de l'appariement retourné: il peut exister un agent de chacun des groupes qui ne sont pas appariés, mais préféreraient l'être
4. Formaliser la notion de stabilité, et le problème des appariements stables. Implémenter l'algorithme de *dynamique libre* consistant à faire se rencontrer les couples et à résoudre itérativement les instabilités. Discuter.
5. Programmer l'algorithme AD. Discuter les solutions obenues.
6. Programmer l'algorithme TTC. Interpréter son fonctionnement. Discuter les solutions obenues.