6.2 Relação com o problema do casamento

6.2 Relação com o problema do

casamento

Suponha que começamos com um problema de casamento entre grupos de mesmo número de homens e mulheres, com listas completas. Ao final de cada lista de preferência de um homem (ou mulher), acrescente os demais homens (ou mulheres, respectivamente) em uma ordem arbitrária, obtendo listas de preferência para um problema de colegas de quarto.

Por um lado, qualquer emparelhamento estável entre os grupos de homens e mulheres, como solução ao problema do casamento, também é estável como solução para esse problema de colegas de quarto: não há pares de bloqueio formados por um homem e uma mulher (já que, se existissem, bloqueariam os casamentos originais), nem pares formados por dois homens ou duas mulheres, porque cada membro foi colocado, na lista do outro, após seu parceiro.

Por outro, não pode haver qualquer novo emparelhamento estável: se houver dois homens em um quarto e duas mulheres em outro, bastará formar um par qualquer com um desses homens e uma dessas mulheres para bloquear o emparelhamento, já que se preferirão entre si em relação aos colegas de quarto que vêm no final de suas listas.

Assim, como sempre há uma alocação estável entre homens e mulheres, se realizarmos o procedimento acima, então obteremos um emparelhamento dentro da união dos conjuntos de homens e mulheres, que de fato combina homens a mulheres e é uma solução estável para o problema de casamento. Exceto por saber-se de antemão que o problema do casamento pode ser sempre resolvido, esta é uma pequena redução ao problema de colegas de quarto. (GUSFIELD; IRVING, 1989, lema 4.1.1.)

Enquanto a primeira parte do algoritmo dos colegas de quarto, referente às propostas dos indivíduos, é semelhante ao mecanismo deferred acceptance de resolução do problema do casamento, a segunda parte é nova, ao utilizar um outro procedimento intitulado minimal differences ("diferenças mínimas").

É esse o algoritmo responsável pela eliminação das rotações, que reduz as listas de preferência até que ou alguma lista se torne vazia, caso em que não há solução estável, ou cada lista seja reduzida a uma única entrada, de modo que a associação correspondente é estável. Contudo, como há várias ordens em que as rotações podem ser identificadas e escolhidas para serem eliminadas, o emparelhamento obtido não precisa ser único (em contraste com Gale-Shapley no problema do casamento). Por outro lado, as rotações ocorrem também no problema do casamento e são instrumentais em investigações mais avançadas.