Problema do emparelhamento estável

O problema do emparelhamento estável ("Stable Matching Problem") possui diversas aplicações em nosso cotidiano. Algumas das principais são os processos seletivos para universidades, a seleção de residentes,[1] o problema da estabilidade do casamento ("stable marriage problem"), a seleção de estagiários e a escolha de colegas de quarto ("roomate problem").[2]

Os pesquisadores americanos David Gale (1921-2008)[3] e Lloyd Shapley (1923- ) foram os primeiros a desenvolver um algoritmo eficiente para resolver esses problemas. Esse algoritmo foi apresentado em um artigo da revista American Mathematical Monthly, Vol. 69, No. 1 de janeiro de 1962,[4] que abordava principalmente os processos de admissão em universidades e o problema da estabilidade do casamento ("stable marriage problem"). Esse trabalho, e seus desenvolvimentos posteriores, inclusive, valeram a L. S. Shapley e A. E. Roth o prêmio Nobel em Economia no ano de 2012 .

Processo seletivo para Universidades

Vamos supor que um determinado estudante foi aceito pela universidade A e encontra-se na lista de espera da universidade B (que ele prefere em relação à A). Caso por algum motivo, o estudante venha a ser chamado pela universidade B, ele provavelmente abandonaria a universidade A para estudar na universidade B, e deixaria A com uma vaga ociosa. Isso levaria A a também chamar algum candidato de sua lista de espera, e deixaria uma vaga ociosa em alguma outra universidade. Essa situação poderia fazer com que terminássemos o processo seletivo com vagas ociosas em algumas universidades e alunos interessados nelas, mas que não foram aceitos em nenhuma universidade.

O objetivo do algoritmo que será apresentado a seguir é distribuir os candidatos entre as vagas de forma a satisfazer ambos os grupos, candidatos e universidades.

Considere um processo seletivo no qual n candidatos devem ser designados para m universidades, onde ${\displaystyle q_{i}}$ é a quantidade de vagas na i-ésima universidade. Cada candidato deve listar as universidades por ordem de preferência (sem empates), excluindo apenas aquelas em que não deseja estudar em hipótese alguma. Da mesma forma, cada universidade deve listar os candidatos (dentre os que aplicaram para ela), excluindo apenas aqueles estudantes que não admitiria de forma alguma (essa lista poderia ser baseada nas notas de um exame de seleção, onde as universidades poderiam atribuir pesos diferentes às diversas matérias e excluir os candidatos que estivessem abaixo da nota mínima estipulada).

Considere um processo seletivo em que haja dois candidatos ${\displaystyle \alpha }$ e ${\displaystyle \beta }$ e duas universidades A e B com uma vaga cada uma. O candidato ${\displaystyle \alpha }$ prefere a universidade A e o candidato ${\displaystyle \beta }$ prefere a universidade B, mas a universidade A prefere o candidato ${\displaystyle \beta }$ e a universidade B prefere o candidato ${\displaystyle \alpha }$. Nesse caso, não há uma distribuição que satisfaça todas as preferências. Considerando que as universidades existem para atender os estudantes, e não o contrário, vamos designar ${\displaystyle \alpha }$ para universidade A e ${\displaystyle \beta }$ para a universidade B. Assim, será adotada como premissa que, quando outros aspectos forem iguais, o desejo dos candidatos terá prioridade em relação ao das universidades.

O ponto central é obter uma distribuição onde não ocorra a situação definida a seguir.

DEFINIÇÃO: Uma designação de candidatos para universidades é considerada instável se há dois candidatos ${\displaystyle \alpha }$ e ${\displaystyle \beta }$ designados para as universidades A e B, respectivamente, embora ${\displaystyle \beta }$ prefira a universidade A à universidade B, e a universidade A prefira o candidato ${\displaystyle \beta }$ ao candidato ${\displaystyle \alpha }$ .

Supondo que a situação definida acima ocorra, o candidato ${\displaystyle \beta }$ tentaria transferir-se para a universidade A, que o admitiria em detrimento do candidato ${\displaystyle \alpha }$. Essa mudança seria vantajosa tanto para ${\displaystyle \beta }$ quanto para A. Dessa forma, a distribuição original é considerada instável, pois pode ser subvertida por ${\displaystyle \beta }$ e A agindo juntos, de maneira que ambos sejam beneficiados.

A condição essencial que deve ser satisfeita para uma designação de candidatos para universidades é que ela não tenha instabilidades. Entretanto, não sabemos se é sempre possível obter uma designação sem instabilidades (ou seja, um "emparelhamento estável") para qualquer combinação de candidatos, universidades e preferências.

Por enquanto, vamos supor que existam soluções estáveis e analisar dentre essas soluções qual escolher, ou seja, qual delas é a "melhor", tendo em vista a premissa estabelecida de que o desejo dos candidatos tem prioridade em relação ao das universidades. A definição a seguir estabelece a condição para que uma designação seja considerada "ótima".

DEFINIÇÃO: Um emparelhamento estável é considerado ótimo se cada candidato está tão satisfeito quanto em qualquer outro emparelhamento estável.

Não é possível afirmar que haja uma designação ótima, mas, se existir, a designação ótima será única. Supondo que houvesse duas designações ótimas distintas e lembrando que na lista de preferências não há empates, então pelo menos um dos candidatos estaria mais satisfeito em uma das designações do que na outra e, portanto, uma delas não seria ótima (de acordo com a definição acima).

Assim, se conseguirmos garantir a existência de um emparelhamento estável e ótimo, teremos a certeza de que essa solução é única.

Problema do Casamento Estável (Stable Marriage Problem)

A fim de analisar as questões de existência, vamos estudar um problema mais simples: o Problema do Casamento Estável. Esse problema consiste em tentar casar de maneira satisfatória as pessoas de um grupo de n homens e n mulheres, onde cada uma das pessoas deve classificar todas as do sexo oposto por ordem de preferência para o casamento. Neste caso, um emparelhamento será dito instável se houver um homem e uma mulher que não estão casados, mas preferem um ao outro a seus atuais parceiros.

TEOREMA: Sempre existe um conjunto de casamentos estáveis.

Demonstração:

Primeira parte: Determinação dos casais

O teorema será provado apresentando-se um método para encontrar o emparelhamento estável. Inicialmente, cada homem propõe casamento à sua mulher favorita. Cada mulher rejeita todas as propostas que recebeu, exceto a sua favorita. Os casais formados são então considerados noivos. Na segunda etapa, os homens que foram rejeitados propõem casamento a sua próxima escolha. Cada mulher então escolhe o seu favorito entre os novos proponentes e seu noivo. O favorito torna-se então (ou permanece sendo) seu noivo. Esse procedimento então continua sendo repetido. Os homens rejeitados no segundo estágio propõem casamento à sua próxima escolha e as mulheres escolhem para noivo o melhor entre os novos proponentes e seu noivo. Em algum momento (não mais do que n^2 estágios), todas as mulheres terão recebido propostas, pois se alguma mulher não recebeu proposta, ela não está noiva e ainda há homens disponíveis efetuando propostas. Além disso, os homens não podem propor casamento à mesma mulher duas vezes. Assim que a última mulher recebeu sua proposta, o procedimento é encerrado, e cada mulher deve então casar-se com seu noivo. Note que como todas as mulheres recebem propostas, todas ficam noivas, pois uma mulher só troca seu noivo por outro melhor.

Segunda parte: O conjunto de casamentos assim obtido é estável

Suponha que um homem H e uma mulher M não estão casados, mas H prefere M à sua mulher. Então em algum momento H propôs a M e em algum momento foi rejeitado em favor de alguém que M preferia. Dessa forma, M prefere seu marido a H e não há instabilidade.

Observe que o procedimento acima funciona de maneira similar quando a quantidade de homens e mulheres não é a mesma. No caso de haver mais mulheres do que homens, o procedimento termina assim que todos os homens ficam noivos. No caso de haver mais homens que mulheres, o procedimento termina assim que todos os homens ou estão noivos ou foram rejeitados por todas as mulheres.

O procedimento descrito no qual os homens propõem casamento às mulheres resulta em uma solução ótima para os homens. Adotando um procedimento análogo no qual as mulheres é que propõem casamento aos homens, a solução é ótima para as mulheres. As soluções obtidas nesses dois procedimentos somente serão iguais quando houver um único conjunto de casamentos estáveis.

A fim de ilustrar a aplicação do procedimento descrito acima, foi desenvolvido um código na linguagem Python para a solução do Problema dos Casamentos Estáveis.[5]

Algoritmo

funcao emparelhamentoEstavel {
    Inicialize todos os h ∈ H e m ∈ M como solteiros
    Enquanto (∃ um homem solteiro h que ainda foi chamado por uma mulher m para namorar {
        m = primeira mulher na lista lista do homem m que ainda não chamou ele para namorar
        Se m esta disponivel
            (h, m) começam a namorar
        Senao (h', m) já namoram
            Se m prefere o h do que o h'
                h' fica solteiro
                (h, m) começam a namorar
            Senao
                (h', m) continuam namorando
    }
}

De volta ao Processo Seletivo para Universidades

Vamos adequar o procedimento descrito para o Problema dos Casamentos Estáveis ao Processo Seletivo para Universidades. Por comodidade, vamos supor que se uma universidade não está disposta a aceitar um estudante em hipótese alguma (por exemplo, porque ele não atingiu a nota mínima no exame de admissão), então ele não pode se candidatar para essa universidade.

Inicialmente, todos estudantes se candidatam para sua primeira escolha. Cada uma das universidades inclui em sua lista de espera os candidatos com a melhor classificação limitado ao seu número de vagas e rejeita os outros. Os estudantes rejeitados se candidatam à sua segunda opção e as universidades incluem em sua lista de espera os candidatos com melhor classificação limitado ao número de vagas dentre os novos candidatos e os que já estavam em sua lista de espera, rejeitando os outros. O procedimento termina quando todos os estudantes estão em uma lista de espera ou foram rejeitados por todas as universidades a que poderiam se candidatar. Nesse momento as universidades aceitam em definitivo todos os estudantes em sua lista de espera. A distribuição assim obtida é um emparelhamento estável (a demonstração é análoga àquela feita para o Problema dos Casamentos Estáveis).

A designação dos estudantes para as universidades obtida de acordo com o procedimento acima é ótima para os estudantes.

TEOREMA: Na designação obtida pelo procedimento descrito acima, cada estudante está tão satisfeito quanto estaria em qualquer outra designação estável.

Demonstração:

Vamos apresentar uma demonstração por indução. Consideremos uma universidade possível para um estudante se existe um emparelhamento estável no qual ele é aceito nessa universidade. Assumindo que em um determinado ponto do desenvolvimento do procedimento, nenhum candidato ainda foi rejeitado por uma universidade A que é possível para um estudante ${\displaystyle \alpha }$. Suponha que a universidade A recebeu candidaturas de v estudantes ${\displaystyle \beta _{1},\beta _{2},...,\beta _{v}}$ mais bem classificados do que ${\displaystyle \alpha }$ preenchendo todas as suas v vagas, o que a levou a rejeitar o estudante ${\displaystyle \alpha }$. Cada um dos candidatos ${\displaystyle \beta _{i}}$ prefere A a todas as outras universidades, exceto àquelas que já o rejeitaram anteriormente. A nossa hipótese de indução é que essa universidades são impossíveis para eles. Vamos provar que a universidade A é impossível para ${\displaystyle \alpha }$. Consideremos, por absurdo, uma distribuição que designa ${\displaystyle \alpha }$ para A e todos os outro estudantes para universidades que são possíveis para eles. Pelo menos um dos estudantes ${\displaystyle \beta _{i}}$ irão para uma universidade que ele deseja menos do que A. Mas essa distribuição é instável, visto que ${\displaystyle \beta _{i}}$ prefere A em relação à universidade para a qual foi designado e A prefere ${\displaystyle \beta _{i}}$ em relação à ${\displaystyle \alpha }$. Portanto, a universidade A é impossível para ${\displaystyle \alpha }$

Conclui-se que, no curso do procedimento descrito, apenas são rejeitados por universidades estudantes que não seriam designados para essas universidades em nenhum emparelhamento estável. Logo, a designação obtida é ótima.

Exemplos de aplicações

• O algoritmo descrito acima poderia ser implementado com vantagens no Sistema de Seleção Unificada (Sisu). Ele permite a adoção de pesos diferentes e a adoção de notas mínimas por curso. Para a questão das vagas reservadas pelas políticas afirmativas ou sistema de cotas, o procedimento de emparelhamento estável deveria ser aplicado primeiro para o preenchimento dessas vagas e depois novamente para as vagas remanescentes. Além disso, o candidato precisaria acessar o sistema apenas uma vez e escolher quantos cursos quisesse dentre aqueles em que ele atingiu a nota mínima. O resultado do processo seletivo alocaria cada estudante no melhor curso possível com a sua nota.

• Concurso de Educadores de Infância e de Professores dos Ensinos Básico e Secundário, relativo ao ano escolar de 2004/05 em Portugal.[6]

• Otimização dos transplantes de rins nos Estados Unidos, associando pares paciente-doador incompatível com outros na mesma situação.[7]

Implementações em pacotes de software

• R: O algoritmo de Gale-Shapley para o problema do emparelhamento estável está disponível como parte do pacote matchingMarkets.[8][9]
• API: A API MatchingTools fornece uma interface de programação de aplicativos para o algoritmo.[10]

Ver também

• Acoplamento (teoria dos grafos)

Referências

1. National resident matching algorithm[1]
2. Stable roomate problem [2]
3. David Gale [3]
4. D. Gale e L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly, vol. 69, No. 1, jan 1962 (link)
5. L. G. M. Castro: Código em Python para o Problema dos Casamentos Estáveis (link)
6. Technical Report DCC-05-02 (Emparelhamentos, Casamentos Estáveis e Algoritmos de Colocação de Professores) de autoria de Ana Paula Tomás da Universidade do Porto
7. Al Roth: An economist who saves lives.
8. Klein, T. (2015). «Analysis of Stable Matchings in R: Package matchingMarkets» (PDF). Vignette to R Package matchingMarkets 
9. «matchingMarkets: Analysis of Stable Matchings». R Project 
10. «MatchingTools API» 

Bibliografia

• J. Kleinberg e Éva Tardos, Algorithm Design; Pearson Education, Inc., 2006.
• D. Gusfield e R. W. Irving, The Stable Marriage Problem: Structure and Algorithms; MIT Press, 1989.
• P. M. Rodrigues, Notas Sobre Elementos de Matemática Finita, cap. 5, 2013.
• L. Evered e W. May, A Java Program for the Gale-Shapley Algorithm.
• C. P. Teo, J. Sethuraman e W. P. Tan, Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications, Management Science, vol. 47, no. 9, set 2001.
• N. Schulz, The Roommates Problem Discussed, 2008.
• The Prize in Economic Sciences 2012 (Nobel Prize)- Information for the Public, Stable matching: Theory, evidence, and practical design.