Note on the size of a stable matching

Resumo Técnico: Nota sobre o Tamanho de um Emparelhamento Estável

Enunciado do Problema
O artigo investiga a relação entre o tamanho de um emparelhamento estável e o tamanho do maior emparelhamento individualmente racional (máximo) em um mercado de emparelhamento de dois lados um-para-um (trabalhadores e empresas com uma única posição). Embora o framework de Gale-Shapley garanta a existência de emparelhamentos estáveis, ele não garante que esses emparelhamentos maximizem o número de trabalhadores empregados ou de posições preenchidas. Os autores abordam a seguinte questão: Dado um mercado onde o maior emparelhamento individualmente racional contém $n$ pares, qual é o limite inferior para o número de pares em qualquer emparelhamento estável? Além disso, eles buscam caracterizar as estruturas de preferências específicas que forçam os emparelhamentos estáveis a serem o menor possível em relação ao máximo, e analisam a sobreposição entre pares estáveis e pares máximos.

Metodologia
Os autores empregam uma abordagem de teoria dos grafos para modelar o mercado de emparelhamento, utilizando formulações de grafos não direcionados e direcionados.

1. Formulação de Grafo Não Direcionado: O mercado é modelado como um grafo bipartido $G = (W, F; E)$, onde as arestas representam pares aceitáveis. Os autores utilizam as propriedades de emparelhamentos maximais e máximos para estabelecer limites.
2. Formulação de Grafo Direcionado (Digrafo): Para caracterizar as estruturas de preferência, os autores adotam a formulação de digrafo de emparelhamento proposta por Maffray (1992). Neste digrafo $D = (V, A)$, os vértices representam pares aceitáveis $(w, f)$, e os arcos representam classificações de preferência (por exemplo, um arco de $(w, f)$ para $(w, f')$ indica que o trabalhador $w$ prefere $f'$ a $f$).
3. Exclusão Iterativa de Alternativas Não Atraentes (IDUA): Os autores utilizam o procedimento IDUA (Balinski e Ratier, 1997; Gutin et al., 2023) para reduzir o mercado à sua "forma normal". Este processo remove iterativamente pares que não podem pertencer a nenhum emparelhamento estável (por exemplo, pares onde um participante está emparelhado com um parceiro menos preferido enquanto seu parceiro mais preferido está desemparelhado).
4. Caracterização Construtiva: Os autores definem classes específicas de mercados ($G_n$ e $F_n$) construindo perfis de preferência que estendem um mercado base com um emparelhamento estável máximo, adicionando novos participantes cujas preferências são estruturadas para serem "não atraentes" para os participantes estáveis existentes.

Principais Contribuições e Resultados

• Teorema 1 (Limite de Tamanho): O principal resultado estabelece que, em qualquer mercado onde o maior emparelhamento individualmente racional tem tamanho $n$, todo emparelhamento estável deve ter um tamanho de pelo menos $\lceil n/2 \rceil$.

  • Lógica da Prova: A prova baseia-se em dois fatos: (i) um emparelhamento estável é um emparelhamento maximal (não existe um par aceitável com ambos os membros desemparelhados), e (ii) qualquer emparelhamento maximal em um grafo é pelo menos metade do tamanho de um emparelhamento máximo.
  • Implicação: A taxa de emprego de equilíbrio nunca pode cair abaixo de 50% do emprego máximo atingível, desde que o emparelhamento máximo seja individualmente racional.

• Teorema 2 (Caracterização de Preferências Extremas): O artigo caracteriza a classe de perfis de preferência ($F_n$) que atingem este limite inferior.

  • Um mercado atinge o limite (tamanho estável = $\lceil n/2 \rceil$, tamanho máximo = $n$) se, e somente se, pertencer à classe $F_n$.
  • Propriedade Estrutural: Nesses mercados, os participantes que não aparecem em nenhum emparelhamento estável (os "desemparelhados" no equilíbrio) devem considerar uns aos outros inaceitáveis. Se eles se considerassem aceitáveis, formariam um par de bloqueio, aumentando o tamanho do emparelhamento estável.
  • Acordo no Topo: Uma subclasse natural desses mercados exibe "acordo no topo", onde os participantes no núcleo estável classificam todos os novos participantes não estáveis abaixo de seu parceiro estável menos preferido.

• Teorema 3 (Sobreposição e Sacrifício): Os autores analisam a interseção entre o conjunto de pares em um emparelhamento estável ($\mu^*$) e um emparelhamento máximo ($\mu$).

  • Seja $r$ o número de pares comuns. O teorema afirma: $|\mu^*| \geq (|\mu| + r) / 2$.
  • Implicação: Quando o emparelhamento estável é minimizado (isto é, $|\mu^*| = \lceil |\mu|/2 \rceil$), a sobreposição $r$ deve ser zero. Isso significa que, se o mercado for estruturado de tal forma que os emparelhamentos estáveis sejam o menor possível, nenhum dos pares no emparelhamento estável aparece no emparelhamento máximo.
  • Custo da Estabilidade: Maximizar o emprego (preencher todas as vagas) pode exigir o "sacrifício" de todos os pares de equilíbrio que de outra forma existiriam em uma configuração estável menor.

Significância e Escopo
O artigo enquadra sua análise como uma exploração do "custo da estabilidade". Ele quantifica o compromisso entre estabilidade e eficiência (medida pelo tamanho do emparelhamento). Os autores observam que, embora a estabilidade garanta que não haja pares de bloqueio, ela pode resultar em uma redução significativa no número de trabalhadores empregados em comparação com o máximo teórico, especificamente em mercados com as estruturas de preferência identificadas no Teorema 2.

Os autores limitam explicitamente o escopo de seus resultados a mercados de emparelhamento de dois lados um-para-um. Eles reconhecem que, embora o framework seja amplamente aplicável (por exemplo, estudante-faculdade, médico-hospital), os limites específicos e as caracterizações derivadas aqui não se estendem automaticamente para ambientes mais complexos, como mercados de muitos-para-um, mercados com casais ou problemas de "colega" (roommate) de um lado. O artigo não propõe novos algoritmos ou aplicações experimentais, mas fornece um limite teórico e uma caracterização estrutural dos cenários de pior caso para as taxas de emprego em equilíbrios estáveis.