Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty

Este artigo propõe um modelo de expansão de capacidade em duas etapas para mercados de pareamento estável, como a escolha escolar, que considera a incerteza nas preferências dos alunos (sejam elas verdadeiras ou estratégicas) para otimizar as decisões de capacidade e melhorar os resultados de alocação por meio de aproximações e heurísticas.

O essencial

Imagine que você é o diretor de uma rede de escolas públicas. O seu grande desafio é decidir antes de saber exatamente o que os alunos vão querer: quantas novas salas de aula você deve construir em cada escola?

Se você construir salas demais na escola errada, gasta dinheiro à toa. Se construir de menos, alunos ficam sem lugar. O problema é que os alunos só dizem onde querem estudar depois que as salas já estão construídas. E, além disso, eles podem não dizer a verdade: podem mentir sobre onde gostariam de ir para aumentar suas chances de entrar.

Este artigo de pesquisa propõe uma "bola de cristal matemática" para ajudar os diretores a tomarem essas decisões difíceis. Vamos descomplicar o conceito usando analogias do dia a dia.

1. O Cenário: A Loteria das Preferências

Pense no sistema de matrícula escolar como um grande jogo de loteria.

• O Diretor (Clearinghouse): Precisa comprar os bilhetes (construir salas) antes de saber quais números vão sair.
• Os Alunos: São os jogadores que escolhem seus números (escolas).
• A Incerteza: Ninguém sabe exatamente quais números os alunos vão escolher.

O artigo diz que a maioria dos estudos anteriores assumia duas coisas erradas:

1. Que os alunos sempre dizem a verdade.
2. Que sabemos exatamente o que eles vão querer antes de construir as salas.

Na vida real, os alunos são inteligentes (e às vezes um pouco trapaceiros). Eles olham para as salas disponíveis e pensam: "Se eu pedir a escola X, que é muito popular, talvez eu não entre. Melhor pedir a escola Y, que tem mais vagas, para garantir." Isso cria um efeito dominó: se todos pensam assim, a demanda muda dependendo de quantas salas foram construídas.

2. As Três Formas de Jogar (Comportamento dos Alunos)

Os autores criaram um modelo para simular três tipos de jogadores:

• O "Honesto" (Comportamento UM): O aluno diz exatamente o que quer, sem se importar se é difícil entrar. É como alguém que compra o bilhete da loteria com o número da sorte do seu cachorro, mesmo sabendo que é improvável ganhar.
• O "Estrategista Sofisticado" (Comportamento CEUM): Este aluno é um mestre de xadrez. Ele calcula: "Se eu pedir a escola A, tenho 80% de chance de entrar. Se pedir a B, tenho 90%. Mas se eu pedir A e B, e A me recusar, B ainda está lá?" Ele tenta maximizar sua felicidade considerando o risco de ser rejeitado. É como um jogador que não aposta em todos os números, mas escolhe uma combinação que equilibra risco e recompensa.
• O "Estrategista Simples" (Comportamento IEUM): Este aluno é um pouco menos esperto. Ele olha apenas para a chance de entrar em cada escola individualmente, sem se preocupar com o risco de ser rejeitado pela primeira escolha. É como alguém que escolhe as escolas apenas olhando o número de vagas, ignorando a concorrência.

3. A Solução: A "Simulação de Milhares de Futuros"

Como prever o futuro? Os autores usam uma técnica chamada Aproximação pela Média de Amostras (SAA).

Imagine que, em vez de tentar adivinhar uma única realidade, o computador cria 100 ou 1.000 cenários possíveis (como se fosse um filme com 1.000 finais diferentes).

• Em alguns filmes, todos querem a escola do centro.
• Em outros, todos preferem a escola da praia.
• Em outros, os alunos são estratégicos e mudam de ideia.

O algoritmo testa diferentes planos de construção de salas em todos esses 1.000 filmes. O plano vencedor é aquele que funciona bem na média, garantindo que, não importa qual "filme" (cenário) aconteça, o resultado seja o melhor possível para a maioria dos alunos.

4. O Que Eles Descobriram? (As Lições)

• Não confie no "Média": Se o diretor apenas olhar para a média histórica (ex: "50% querem a escola A") e construir baseado nisso, ele vai errar feio quando os alunos agirem de forma estratégica. O modelo deles mostrou que considerar a incerteza e o comportamento estratégico melhora drasticamente o resultado.
• A Mentira Custa Caro: Se o diretor planejar as salas achando que os alunos são "Honestos", mas eles forem "Estrategistas", o resultado será pior. Alunos ficarão em escolas que não gostam ou ficarão sem lugar.
• O Tamanho da Lista Importa: Se os alunos podem listar muitas escolas (ex: 10 opções), eles tendem a agir de forma mais honesta. Se só podem listar 2 ou 3, eles ficam mais estratégicos e calculistas. O modelo ajuda a entender isso.
• Ferramentas Rápidas: Como calcular 1.000 cenários é muito pesado para o computador, eles criaram "atalhos inteligentes" (heurísticas). São como receitas de bolo simplificadas que dão um resultado quase perfeito em segundos, em vez de horas.

Resumo em uma Frase

Este artigo ensina que, para planejar escolas (ou qualquer sistema de vagas), não basta olhar para o passado ou assumir que as pessoas são ingênuas; é preciso usar matemática avançada para simular milhares de futuros possíveis e entender como as pessoas vão realmente se comportar, garantindo que ninguém fique sem lugar e que o dinheiro público seja bem gasto.

É como um GPS para decisões públicas: em vez de seguir um mapa estático, ele recalcula a rota em tempo real, considerando que os outros motoristas (alunos) podem mudar de direção dependendo do tráfego (vagas disponíveis).

Resumo técnico

Resumo Técnico: Expansão Estocástica de Capacidade em Duas Etapas em Emparelhamento Estável sob Incerteza de Preferências

1. O Problema (2-STMMP)

O artigo propõe e formaliza o Problema de Expansão de Capacidade Estocástica em Duas Etapas em Emparelhamento Muitos-para-Um com Preferências Incertas (2-STMMP). Este problema modela mercados de emparelhamento centralizados (como escolha escolar ou alocação de residências médicas) onde a decisão de expandir a capacidade das instituições (escolas) deve ser tomada antes que as preferências dos agentes (alunos) sejam reveladas.

O problema é caracterizado por três elementos fundamentais:

1. Decisão de Primeira Etapa (Planejamento): Um "centro de compensação" (clearinghouse) decide a expansão de capacidade das escolas sob um orçamento limitado, sem conhecer as preferências futuras dos alunos.
2. Incerteza de Preferências: As preferências dos alunos são incertas e podem ser:
   • Exógenas (Não Estratégicas): Os alunos relatam suas preferências verdadeiras (comportamento de Maximização de Utilidade - UM). A incerteza é independente da decisão de capacidade.
   • Endógenas (Estratégicas): Os alunos agem estrategicamente, relatando preferências baseadas em suas verdadeiras preferências e em suas crenças sobre as chances de admissão, que dependem diretamente das capacidades decididas no primeiro estágio. Isso cria uma incerteza endógena (dependente da decisão).
3. Decisão de Segunda Etapa (Emparelhamento): Após a revelação das preferências relatadas, o centro de compensação executa um emparelhamento estável ótimo para os alunos (usando o algoritmo de Aceitação Diferida - DAA) com base nas capacidades expandidas e nas prioridades das escolas.

O objetivo é minimizar o valor esperado da soma das classificações (ranks) das escolas atribuídas aos alunos, considerando todas as possíveis realizações das preferências e o comportamento estratégico.

2. Metodologia

Para resolver o 2-STMMP, os autores utilizam uma abordagem baseada em Aproximação Média de Amostra (SAA - Sample Average Approximation), pois a enumeração completa de cenários é intratável devido à continuidade das utilidades e à complexidade das preferências endógenas.

Modelagem de Comportamento:
O artigo define três modelos de comportamento para os alunos:

• UM (Utility Maximization): Alunos relatam verdadeiramente suas preferências (incerteza exógena).
• CEUM (Conjoint Expected Utility Maximization): Alunos estratégicos que maximizam a utilidade conjunta esperada, considerando não apenas a chance de admissão em cada escola, mas também o risco de rejeição em escolas preferidas (baseado no problema de escolha de portfólio de Chade e Smith, 2006).
• IEUM (Individual Expected Utility Maximization): Alunos estratégicos que maximizam a soma das utilidades individuais esperadas, ignorando o risco de rejeição de escolas superiores (uma aproximação da racionalidade limitada).

Abordagens de Solução:
Devido à complexidade computacional (o problema é NP-difícil e envolve programas de dois níveis para comportamentos estratégicos), os autores desenvolveram um conjunto de métodos exatos e heurísticos:

• Formulações Matemáticas Exatas:
  • Para o caso UM: Uma formulação modificada de "Restrições L" (L-constraints) para garantir estabilidade.
  • Para os casos CEUM e IEUM: Formulações de nível único exatas que transformam o problema de dois níveis (onde a preferência relatada é uma otimização interna) em um único nível, utilizando transformações de variáveis e linearização de termos não lineares.
• Heurísticas:
  • Relaxação Lagrangiana (LR): Específica para o caso UM, relaxando as restrições de estabilidade para obter limites inferiores fortes e combinando com o DAA para obter limites superiores.
  • Busca Local (LS) e Recozimento Simulado (SA): Heurísticas gerais aplicáveis a todos os comportamentos. Elas exploram o espaço de decisões de capacidade, calculam as preferências relatadas (usando algoritmos específicos como MIA para CEUM e IOA para IEUM) e avaliam o emparelhamento via DAA.

3. Contribuições Principais

1. Novo Modelo (2-STMMP): Introdução do primeiro modelo que integra simultaneamente expansão de capacidade, incerteza de preferências e comportamento estratégico endógeno em mercados de emparelhamento estável.
2. Tratamento da Incerteza Endógena: Aplicação do método de transformação de variáveis aleatórias (Bazotte et al., 2025) para modelar preferências estratégicas como funções das decisões de capacidade e preferências verdadeiras, permitindo o uso de métodos de amostragem (SAA).
3. Kit de Solução Versátil: Desenvolvimento de formulações exatas e heurísticas eficientes (LR, LS, SA) que lidam com a complexidade adicional dos comportamentos estratégicos, oferecendo soluções de alta qualidade em tempos computacionais viáveis.
4. Análise de Impacto: Demonstração empírica de que ignorar a incerteza ou o comportamento estratégico leva a decisões de capacidade subótimas.

4. Resultados Experimentais

Os autores realizaram extensos experimentos com instâncias pequenas e grandes, comparando a abordagem estocástica (SAA) com a abordagem determinística baseada em cenário médio (EV - Expected Value).

• Valor da Solução Estocástica (VSS): A abordagem SAA superou consistentemente a abordagem EV em todos os comportamentos.
  • A SAA resultou em emparelhamentos de maior qualidade (menores ranks) e aumentou significativamente o número de alunos que conseguem entrar no sistema ou melhorar sua atribuição.
  • O ganho foi mais pronunciado quando as decisões de capacidade são baseadas em um cenário médio, que falha em capturar a variabilidade das preferências.
• Impacto do Comportamento Estratégico:
  • Decisões de capacidade otimizadas assumindo comportamento verdadeiros (UM) performaram pior quando os alunos agiam estrategicamente (CEUM ou IEUM).
  • A suposição incorreta do tipo de estratégia (ex: assumir IEUM quando os alunos seguem CEUM) causou perdas significativas na qualidade do emparelhamento.
  • O tamanho da lista de preferências (K) influencia a similaridade entre os comportamentos: listas longas tornam o comportamento estratégico mais próximo do verdadeiro, enquanto listas curtas exacerbam as diferenças.
• Desempenho Computacional:
  • O caso UM é resolvido eficientemente com formulações exatas ou a heurística Lagrangiana.
  • Os casos estratégicos (CEUM/IEUM) são computacionalmente muito mais difíceis devido à natureza endógena. As heurísticas de Recozimento Simulado (SA) mostraram-se as mais equilibradas, oferecendo soluções de alta qualidade (gap de limite superior < 0.5% em média) com tempos de execução estáveis, superando métodos exatos que frequentemente falharam em encontrar soluções ótimas dentro de limites de tempo razoáveis para instâncias grandes.

5. Significância e Conclusão

O trabalho destaca que o planejamento de capacidade em sistemas de alocação pública não pode ser tratado como um problema determinístico.

• Implicações Econômicas e Sociais: Ignorar a incerteza e o comportamento estratégico leva a investimentos ineficientes (escolas super ou subdimensionadas) e a resultados sociais piores (alunos não atendidos ou em escolas menos preferidas).
• Relevância Prática: O modelo é aplicável a contextos onde o investimento em infraestrutura precede a demanda real, como expansão de escolas, alocação de vagas em residências médicas, distribuição de vacinas e reassentamento de refugiados.
• Conclusão: A modelagem estocástica combinada com a representação precisa do comportamento dos agentes é crucial para maximizar o bem-estar dos alunos e a eficiência dos recursos. As heurísticas propostas fornecem ferramentas viáveis para tomadores de decisão lidarem com a complexidade desses problemas em escala real.