Experimental Design for Matching

Resumo Técnico: Desenho Experimental para Emparelhamento

Definição do Problema
Os mecanismos de emparelhamento (matching) são infraestruturas críticas na gestão de operações, abrangendo educação, saúde e plataformas digitais. Um desafio fundamental surge quando profissionais buscam comparar empiricamente um novo algoritmo de emparelhamento (tratamento) contra um status quo (controle) em uma população finita. Os métodos padrão de inferência causal enfrentam um obstáculo único neste cenário: a interferência de emparelhamento. Diferente de unidades experimentais independentes, atribuir uma unidade a um par específico no plano de tratamento pode impedir sua atribuição no plano de controle devido a restrições de capacidade e compatibilidade. Consequentemente, os contrafatuais ao nível individual são inobserváveis, e as decisões de randomização são acopladas entre as unidades. A literatura existente foca frequentemente na mitigação de viés dentro de um mecanismo de emparelhamento fixo ou assume modelos comportamentais específicos. Este artigo aborda a lacuna de como comparar experimentalmente dois planos de emparelhamento predeterminados sem impor modelos de resultados ou comportamentais, baseando-se exclusivamente em uma perspectiva de desenho (design-based).

Metodologia
Os autores propõem o Desenho de Caminhos Alternados Randomizados (Desenho AP), um arcabouço fundamentado na teoria dos grafos e na inferência baseada em desenho.

1. Conjunto de Desacordo e Decomposição:
   A percepção estrutural central é a definição do conjunto de desacordo ($\Delta M_{(t,c)}$), que compreende pares de emparelhamento presentes em exatamente um dos dois planos (tratamento ou controle). O artigo prova que, para emparelhamentos um-para-um, este conjunto admite uma decomposição única em caminhos alternados e ciclos disjuntos. Nessas estruturas, as arestas alternam entre o emparelhamento de tratamento ($M_t$) e o de controle ($M_c$). Devido às restrições de capacidade, arestas adjacentes em um caminho ou ciclo alternado não podem ser simultaneamente realizadas.

2. Esquema de Randomização:
   O Desenho AP realiza a randomização sequencial ao longo desses caminhos e ciclos.

   • Caso de Caminho: Para um caminho aberto, a primeira aresta é selecionada com probabilidade $p/(1+p)$. As arestas subsequentes são selecionadas com probabilidade condicional $p$ se o predecessor não foi selecionado; caso contrário, a aresta é deterministicamente ignorada (probabilidade 0).
   • Caso de Ciclo: Regras sequenciais semelhantes se aplicam, com a aresta final sendo determinada deterministicamente com base na realização da primeira e da penúltima arestas para garantir a viabilidade.
   • Independência: A randomização é realizada independentemente entre diferentes caminhos e ciclos.

3. Estimação:
   Os autores utilizam o estimador de Horvitz-Thompson para estimar o Efeito Médio do Tratamento (ATE). Eles estabelecem a não-viesagem deste estimador sob o desenho AP.

4. Otimização (Estrutura Minimax):
   Para otimizar a eficiência, os autores analisam a variância de pior caso do estimador sob uma suposição de resultado potencial limitado. Eles formulam um problema minimax para encontrar a probabilidade de randomização condicional ótima $p$.

   • Resultado Assintótico: Para caminhos e ciclos longos, o $p$ ótimo converge para $\sqrt{2} - 1 \approx 0,4142$. Este valor é estritamente menor que 0,5, refletindo um compromisso (trade-off) onde a redução da contribuição de variância da aresta atual requer considerar a interferência a jusante (downstream).

5. Extensão Muitos-para-Um:
   O arcabouço é estendido para emparelhamentos muitos-para-um (ex: atribuições de alunos a escolas), onde as restrições de capacidade complicam a decomposição. Os autores constroem um grafo direcionado desbalanceado auxiliar para representar o conjunto de desacordo. Eles reduzem o problema de encontrar uma decomposição viável a duas tarefas de teoria dos grafos:

   • Encontrar caminhos de aumento em uma rede de fluxo construída para lidar com desequilíbrios nos graus dos nós.
   • Realizar decomposições de tour de Euler no grafo balanceado residual.
     Isso garante que os caminhos e ciclos alternados resultantes satisfaçam as restrições de capacidade, permitindo que o desenho AP e as garantias de inferência sejam transferidos.

Principais Resultados

• Não-viesagem: O estimador de Horvitz-Thompson sob o desenho AP é não-viesado para o ATE.
• Escalonamento da Variância: Ao contrário de desenhos ingênuos (que selecionam todo o emparelhamento de tratamento ou controle com probabilidade 0,5), onde a variância não desaparece conforme o tamanho da população $N \to \infty$, a variância do estimador AP diminui a uma taxa de $O(1/N)$.
• Teorema do Limite Central (TLC): O artigo estabelece um TLC de população finita para o estimador. Este resultado é não trivial porque a decomposição do conjunto de desacordo pode exibir padrões complexos, heterogêneos e potencialmente instáveis (misturas de componentes curtos e longos) conforme a população cresce. A prova combina argumentos de Lindeberg-Feller com técnicas de $\alpha$-mistura e o teorema de Bolzano-Weierstrass.
• Limites de Variância: Os autores derivam um limite superior estimável para a variância que depende apenas de quantidades observáveis, permitindo a construção de intervalos de confiança assintóticos.
• Validação Numérica: Utilizando um conjunto de dados de força de trabalho (Revelio Labs), experimentos numéricos confirmam que o desenho AP supera significativamente o desenho ingênuo em termos de redução de variância. A distribuição empírica do estimador alinha-se com a distribuição normal padrão, validando o TLC. O $p$ empiricamente ótimo ($\approx 0,417$) aproxima-se do ótimo teórico de pior caso ($\sqrt{2}-1$).

Significância e Alegações
O artigo afirma fornecer um arcabouço baseado em desenho e livre de suposições para testar mecanismos de emparelhamento. Sua significância reside em:

1. Abordar a Interferência de Emparelhamento: Oferece uma solução principista para o problema específico de interferência inerente aos mercados de emparelhamento, onde as unidades não são independentes.
2. Inovação Estrutural: A decomposição única do conjunto de desacordo em caminhos e ciclos alternados fornece uma base estrutural rigorosa para gerenciar a interferência.
3. Inferência Robusta: Ao estabelecer um TLC que acomoda estruturas de componentes instáveis e heterogêneas, o trabalho possibilita inferência assintótica válida em ambientes de emparelhamento complexos sem exigir modelos de resultados.
4. Aplicabilidade Prática: A extensão para emparelhamentos muitos-para-um via ferramentas de teoria dos grafos (caminhos de aumento e tours de Euler) torna a metodologia aplicável a cenários do mundo real com restrições de capacidade, como troca de órgãos e escolha escolar.

Os autores posicionam este trabalho como uma perspectiva complementar à modelagem estrutural, oferecendo um campo de teste empírico direto para novos algoritmos de emparelhamento contra o status quo na gestão de operações e design de plataformas.