Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting

Este artigo demonstra que, embora encontrar o maior emparelhamento crítico e relaxadamente estável em cenários muitos-para-muitos com empates e cotas seja NP-difícil, é possível obter uma aproximação de 2/3 para esse problema em tempo polinomial.

O essencial

Imagine que você está organizando um grande festival de intercâmbio cultural. De um lado, temos Estudantes (o grupo A) e, do outro, temos Cursos (o grupo B).

O objetivo é emparelhar os melhores estudantes com os melhores cursos. Mas a vida real é complicada, e este artigo resolve um quebra-cabeça muito difícil que mistura três regras difíceis:

1. Preferências com "Empates": Às vezes, um estudante não consegue decidir entre o Curso de Arte e o Curso de Música; para ele, são iguais. Da mesma forma, um curso pode achar dois alunos igualmente talentosos. Não há uma lista rígida de "1º, 2º, 3º", mas sim "1º, 1º (empate), 2º".
2. Cotas Mínimas (O "Mínimo Vital"): Alguns cursos só funcionam se tiverem pelo menos 5 alunos (senão são cancelados). Alguns alunos precisam de pelo menos 3 cursos para se formarem. Se não atingirmos esses números, o sistema falha.
3. A Regra de Ouro (Estabilidade): Ninguém deve se arrepender. Se um estudante e um curso se olham e pensam "Ei, nós nos gostaríamos mais do que nossos parceiros atuais", eles devem poder trocar. Um sistema estável é aquele onde ninguém quer fazer essa troca.

O Problema: O "Sonho Impossível"

O problema é que, quando você mistura empates com cotas mínimas, o "sonho perfeito" (uma solução onde todos estão satisfeitos, ninguém quer trocar e todas as cotas mínimas são atendidas) pode não existir. É como tentar encaixar peças de um quebra-cabeça que foram cortadas de forma irregular: às vezes, você é obrigado a escolher entre "ter todos os alunos satisfeitos" ou "ter todos os cursos funcionando".

Se tentarmos forçar uma solução perfeita, o sistema pode travar e não encontrar nenhuma resposta.

A Solução Criativa: O "Acordo de Paz" (Estabilidade Relaxada)

Os autores do artigo propõem uma solução inteligente chamada Emparelhamento Crítico e Estabilidade Relaxada. Vamos usar uma analogia para entender:

Imagine que o festival está quase acabando e alguns cursos estão prestes a fechar por falta de alunos (estão "deficientes").

• Emparelhamento Crítico: A prioridade número 1 é garantir que o máximo possível de cursos e alunos atinjam seu "mínimo vital". Se um curso precisa de 5 alunos e só tem 4, o sistema vai fazer de tudo para conseguir o 5º, mesmo que não seja o aluno favorito do curso. É como salvar o barco antes de escolher o melhor lugar para sentar.
• Estabilidade Relaxada: Aqui entra a mágica. Normalmente, se um aluno e um curso se gostam mais do que seus parceiros atuais, eles trocam. Mas, na "Estabilidade Relaxada", fazemos uma exceção:
  • Se o curso que o aluno quer é aquele que está quase fechando (precisa desesperadamente de alunos para sobreviver), o sistema diz: "Ok, vocês podem se gostar, mas não troquem agora, porque o curso precisa desesperadamente do aluno que já está lá para não fechar".
  • O sistema ignora a "ciúme" do aluno se o motivo for salvar o curso de fechar as portas.

É como se o diretor do festival dissesse: "Eu sei que você prefere o João ao Pedro, mas o Pedro é o único que mantém o Clube de Teatro aberto. Então, você fica com o Pedro, e o João vai para outro lugar. É um sacrifício necessário para que o clube não feche."

O Algoritmo: O "Jogo de Propostas"

Como encontrar essa solução? Os autores criaram um algoritmo (um passo a passo de computador) que funciona como um jogo de "propostas":

1. Fase de Sobrevivência: Primeiro, os alunos propõem apenas para os cursos que precisam desesperadamente de gente (os que têm cotas mínimas). Eles tentam preencher esses "buracos" primeiro.
2. Fase de Preferência: Depois que as cotas mínimas estão o mais preenchidas possível, os alunos começam a fazer propostas baseadas em seus gostos reais (incluindo os empates).
3. O Truque das "Propostas Incertas": Quando há um empate (dois cursos são iguais para o aluno), o algoritmo usa uma técnica engenhosa. Ele diz: "Vou fazer uma proposta para o Curso A, mas vou deixá-la 'incerta' por um momento. Se o Curso B também me quiser, eu decido depois". Isso evita que o sistema fique preso em decisões ruins e garante que o tamanho do grupo final seja o maior possível.

O Resultado: O Melhor Possível

O grande feito deste trabalho é provar que:

1. Sempre existe uma solução que salva o máximo de cursos (crítica) e onde ninguém faz trocas "injustificadas" (relaxadamente estável).
2. Encontrar a solução perfeita (a maior possível) é impossível de fazer rápido demais (é um problema computacionalmente difícil).
3. MAS, o algoritmo deles encontra uma solução que é pelo menos 2/3 do tamanho da solução perfeita.

Em resumo:
Imagine que o tamanho ideal do festival é 100 pessoas. O algoritmo garante que você terá pelo menos 66 ou 67 pessoas, e que ninguém vai reclamar de forma injusta, e que nenhum curso vai fechar as portas por falta de alunos. É a melhor solução possível para um cenário caótico, garantindo que o festival aconteça e seja o maior e mais justo possível, mesmo com as regras difíceis.

É como um maestro que, mesmo com músicos que não sabem exatamente qual nota tocar e orquestras que precisam de um número mínimo de instrumentos para tocar, consegue fazer a sinfonia tocar sem que ninguém saia da sala, garantindo o som mais alto e harmonioso possível.

Resumo técnico

Resumo Técnico: Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting

1. Problema Investigado

O artigo aborda o problema de emparelhamento bipartido muitos-para-muitos (many-to-many) em cenários onde existem duas características complexas simultaneamente:

1. Empates nas Preferências (Ties): Os agentes (vértices) podem ser indiferentes entre vários parceiros, permitindo que múltiplos vizinhos recebam o mesmo rank na lista de preferências.
2. Cotas Inferiores (Lower Quotas): Cada vértice possui uma cota mínima ($q^-$) e uma cota máxima ($q^+$). A cota mínima representa o número mínimo de parceiros que devem ser atribuídos a um vértice para que a alocação seja considerada viável (ex: um hospital precisa de um número mínimo de residentes, ou um aluno precisa de um número mínimo de disciplinas).

Objetivo: Encontrar um emparelhamento que seja:

• Crítico: Maximiza o atendimento das cotas inferiores (minimiza a "deficiência" total, ou seja, a soma das diferenças entre a cota mínima e o número real de parceiros atribuídos).
• Ótimo em relação às preferências: O emparelhamento deve ser o mais estável possível, dado que a estabilidade clássica pode não existir quando há empates e cotas inferiores.

O artigo demonstra que um emparelhamento que seja simultaneamente crítico e estritamente estável pode não existir. Além disso, o conceito de "popularidade" (popular matching) também falha em garantir existência na presença de empates. Portanto, os autores recorrem ao conceito de Estabilidade Relaxada (Relaxed Stability).

2. Metodologia e Algoritmo Proposto

Os autores desenvolvem um algoritmo baseado em propostas (proposal-based) que combina e estende duas linhas de trabalho anteriores:

1. O algoritmo de Király (para emparelhamento estável com empates em cenários muitos-para-um).
2. O algoritmo de Nasre et al. (para emparelhamento crítico popular com cotas inferiores em cenários muitos-para-muitos com preferências estritas).

Conceitos Chave da Metodologia:

• Definição de Estabilidade Relaxada (Relaxed Stability - RSM):
  Uma definição generalizada para o cenário muitos-para-muitos. Um par bloqueador $(a, b)$ é considerado "justificado" (e, portanto, não invalida a estabilidade relaxada) se:

  • O agente $a$ estiver totalmente preenchido (full-subscribed) e todos os seus parceiros atuais que são menos preferidos que $b$ estiverem em déficit (não atingiram sua cota mínima).
  • Ou, symmetricamente, se $b$ estiver totalmente preenchido e seus parceiros menos preferidos estiverem em déficit.
    Isso permite que pares bloqueadores existam apenas se eles não violarem as cotas mínimas de agentes que já estão "suficientemente atendidos".

• Estrutura do Algoritmo (Níveis e Clones):
  O algoritmo opera em múltiplos níveis ($0$a$s+t$), onde$s$e$t$são a soma das cotas inferiores dos conjuntos$A$e$B$, respectivamente.

  • **Fase 1 (Níveis $0$a$t-1$):** Foca em satisfazer as cotas inferiores do lado$B$. Os vértices de$A$propõem apenas para vértices de$B$ que possuem cotas inferiores (lq-vertices).
  • Fase 2 (Nível $t$ - Passo de Király): Implementa a lógica de Király para lidar com empates. Introduz o conceito de proposta incerta (uncertain proposal). Se um vértice propõe para um vizinho com empate e há outro vizinho com o mesmo rank que ainda não foi proposto e está sub-atendido, a proposta é marcada como "incerta". Isso permite que o algoritmo mantenha a estabilidade mesmo com empates, permitindo que propostas sejam rejeitadas temporariamente para serem reconsideradas.
  • Fase 3 (Níveis $t+1$ a $s+t$): Foca em satisfazer as cotas inferiores do lado $A$ para vértices que ainda estão em déficit após a Fase 2.

• Tratamento de Empates e "Vizinhos Favoritos":
  O algoritmo redefine o conceito de "vizinho favorito" para lidar com múltiplos vértices no mesmo rank, garantindo que as propostas sejam processadas de forma determinística e correta, evitando ciclos ou instabilidades.

• Construção do Grafo Clonado ($G_M$):
  Para provar a correção, os autores utilizam uma técnica de "grafo clonado", onde cada vértice $v$ é replicado $q^+(v)$ vezes. Isso transforma o problema muitos-para-muitos em um problema de emparelhamento um-para-um ($M^*$), facilitando a análise de caminhos alternantes e a prova de otimalidade.

3. Contribuições Principais

1. Generalização do Modelo: É o primeiro trabalho a considerar simultaneamente empates e cotas inferiores em ambos os lados da partição bipartida no cenário muitos-para-muitos. Trabalhos anteriores focavam em cenários mais restritos (um-para-um, ou cotas apenas em um lado).
2. Existência Garantida: Prova que um Emparelhamento Crítico Relaxadamente Estável (CRITICAL-RSM) sempre existe neste cenário generalizado.
3. Refinamento Teórico: Identifica e corrige uma falha técnica na definição de "proposta incerta" do trabalho original de Király, adaptando-a corretamente para o cenário muitos-para-muitos.
4. Algoritmo de Aproximação: Apresenta um algoritmo polinomial que calcula uma aproximação para o emparelhamento CRITICAL-RSM de maior cardinalidade.

4. Resultados Teóricos

• Complexidade: O problema de encontrar o emparelhamento CRITICAL-RSM de máxima cardinalidade é NP-difícil.
• Fator de Aproximação: O algoritmo proposto alcança um fator de aproximação de $2/3$.
  • Isso significa que o tamanho do emparelhamento encontrado pelo algoritmo é pelo menos $2/3$ do tamanho do emparelhamento ótimo (de maior tamanho possível).
  • Este é o mesmo limite de aproximação conhecido para o problema de emparelhamento estável máximo com empates (sem cotas inferiores), e é considerado o melhor possível sob a Hipótese de Expansão de Pequenos Conjuntos (Small Set Expansion Hypothesis).
• Tempo de Execução: O algoritmo roda em tempo polinomial, especificamente $O(m^2)$, onde $m$ é o número de arestas no grafo.

5. Significado e Impacto

Este trabalho é significativo porque resolve um problema prático comum em alocação de recursos (como alocação de estudantes para cursos ou trabalhadores para empresas) onde:

• Há requisitos mínimos obrigatórios (cotas inferiores) que não podem ser ignorados.
• As preferências não são estritas (há empates).
• A estabilidade clássica é impossível de garantir.

Ao introduzir a Estabilidade Relaxada neste contexto complexo, os autores fornecem uma solução viável e eficiente que garante o máximo possível de satisfação das cotas mínimas (crítica) enquanto mantém uma estabilidade robusta contra desvios, com uma garantia teórica forte sobre o tamanho do emparelhamento resultante. A abordagem combina a robustez das cotas inferiores com a flexibilidade necessária para lidar com preferências não estritas.