Asymptotic Equivalence of Immediate and Deferred Acceptance

Imagine que você é o prefeito de uma cidade movimentada onde cada criança precisa de uma vaga em uma escola, mas há exatamente tantos assentos quanto há alunos. O problema não é apenas encontrar um assento; é encontrar o assento certo. Cada família tem uma lista de escolas que ama, desde a "Minha Escola dos Sonhos" até "Aquela que eu iria se fosse obrigado". A cidade também tem regras: talvez uma escola dê prioridade a crianças que moram perto ou que já têm irmãos lá. A grande questão para os responsáveis é: Como podemos combinar crianças com escolas de modo que todos fiquem o mais felizes possível?

Por décadas, especialistas debateram duas formas principais de fazer isso. A primeira é chamada de Aceitação Diferida (AD). Pense nisso como uma dança lenta e cuidadosa. Os alunos se candidatam à sua primeira escolha. As escolas mantêm os candidatos favoritos, mas não dizem "sim" para sempre; elas apenas dizem "talvez". Se um aluno melhor aparecer depois, a escola pode trocá-lo. Esse processo se repete até que todos estejam estabelecidos. É famosa por ser justa e impossível de trapacear, mas pode ser um pouco confusa e ineficiente.

O segundo método é a Aceitação Imediata (AI), também conhecida como o mecanismo "Boston". Isso é mais como uma corrida frenética. Os alunos fazem fila e se candidatam à sua primeira escolha. As escolas olham para a fila, escolhem seus favoritos com base na prioridade e dizem: "Você está dentro!" imediatamente. Se você for rejeitado, corre instantaneamente para sua segunda escolha. A pegadinha é que, se você se candidatar à sua primeira escolha tarde demais, pode perder sua vaga para alguém com maior prioridade que se candidatou antes, mesmo que você realmente quisesse aquela escola mais do que o outro. Por causa disso, a AI é frequentemente criticada por ser injusta ou fácil de manipular. No entanto, ela tem um superpoder: se todos disserem a verdade sobre o que querem, a IA garante um resultado onde ninguém pode ser feito mais feliz sem tornar outra pessoa infeliz. Isso é chamado de "Eficiência de Pareto".

Então, aqui está a pergunta de um milhão de dólares: O superpoder da IA realmente faz uma grande diferença na vida real? Ela consegue colocar as crianças em escolas que elas gostam muito mais do que o método DA? Ou a diferença é apenas um ponto minúsculo e invisível? Este é o enigma que Josué Ortega aborda em seu artigo.

---

A Grande Corrida Escolar: Um Conto de Dois Mecanismos

Josué Ortega, um pesquisador da Queen's University Belfast, decidiu resolver esse debate realizando um enorme experimento mental. Ele não olhou para cidades reais com sua história e política complicadas. Em vez disso, ele imaginou um "mercado aleatório" — um mundo onde a lista de escolas favoritas de cada aluno é sorteada completamente ao acaso, como tirar nomes de um chapéu. Neste mundo, existem $n$ alunos e $n$ escolas.

Ortega queria medir o "ranking médio". Imagine se cada aluno recebesse uma pontuação baseada em quão alta na sua lista estava a escola atribuída a ele. Se você conseguiu sua escolha nº 1, seu ranking é 1. Se você conseguiu sua escolha nº 100, seu ranking é 100. O objetivo é manter esse número o mais baixo possível.

Por muito tempo, sabíamos a resposta para a dança lenta e cuidadosa (DA). Nos anos 1970, matemáticos descobriram que, em um mercado aleatório, o aluno médio acaba em uma escola classificada em cerca de $\log n$ (logaritmo de $n$). Se você tem 1.000 alunos, o ranking médio é aproximadamente 7. Se você tem 100.000 alunos, é aproximadamente 11. O número cresce, mas de forma muito lenta.

Mas e quanto à corrida frenética (IA)? Como a IA funciona de forma diferente — onde a ordem de candidatura importa e os alunos podem ser rejeitados apenas por serem "atrasados" — matemáticos pensaram que poderia ser muito mais complexo. Alguns cientistas da computação tentaram resolver o problema, mas só conseguiam calcular as chances de obter um ranking específico, não o ranking médio para todos. Eles supunham que também seria logarítmico, mas ninguém conseguia provar.

O Segredo do "Colecionador de Cupons"

A grande descoberta de Ortega foi perceber que ambos os mecanismos, apesar de parecerem totalmente diferentes, estão secretamente jogando o mesmo jogo. Ele usou um clássico enigma chamado Problema do Colecionador de Cupons para explicá-lo.

Imagine que você está tentando colecionar um conjunto completo de $n$ cartões colecionáveis diferentes. Cada vez que você compra uma caixa de cereal, recebe um cartão aleatório. Quantas caixas você precisa comprar para conseguir cada um dos cartões pelo menos uma vez?
A resposta é aproximadamente $n \times \log n$. Você gasta muito tempo comprando caixas apenas para encontrar os últimos poucos cartões raros que lhe faltam.

Ortega mostrou que a Aceitação Diferida é exatamente como isso. Os alunos continuam se candidatando às escolas até que cada escola tenha recebido pelo menos uma candidatura. O número total de candidaturas feitas por todos é aproximadamente o mesmo que o número de caixas de cereal que você precisaria comprar para coletar todos os cupons. Como o aluno médio faz cerca de $\log n$ candidaturas, seu ranking final de escola também é cerca de $\log n$.

Então, Ortega voltou seu olhar para a Aceitação Imediata. À primeira vista, parecia diferente porque os alunos não podem simplesmente continuar se candidatando imediatamente; eles têm que esperar um "round" terminar antes de tentar novamente. Mas Ortega percebeu que, se você olhar para o processo de uma maneira específica, é também um colecionador de cupons.

Ele imaginou uma versão ligeiramente "amnésica" do jogo. Suponha que um aluno continue escolhendo escolas aleatoriamente, mesmo que já tenha tentado aquela escola. Se ele escolher uma escola que já tentou, ele apenas ignora (isso é um "desperdício" de tentativa). Ortega provou que, mesmo com esses desperdícios, o número de candidaturas reais necessárias para preencher todas as escolas ainda é aproximadamente o mesmo que o problema do colecionador de cupons.

A Grande Revelação

Aqui está o ápice: a diferença entre os dois métodos é surpreendentemente pequena.

Ortega provou matematicamente que, conforme o mercado se torna gigante (conforme $n$ se torna muito grande), o ranking médio para os alunos em o sistema de Aceitação Imediata (IA) é também aproximadamente $\log n$.

Isso significa que, embora a IA seja "eficiente de Pareto" (significando que é teoricamente perfeita se todos disserem a verdade), ela não oferece uma vantagem massiva aos alunos em termos de conseguir suas primeiras escolhas comparada ao método DA. A melhoria de "primeira ordem" — o ganho grande e perceptível — simplesmente não existe.

O artigo de Ortega descarta explicitamente a ideia de que a IA é uma solução mágica que melhora drasticamente os resultados dos alunos em grandes mercados aleatórios. Embora a IA possa ser ligeiramente melhor em cenários minúsculos e específicos ou com regras de prioridade específicas, o artigo mostra que, no caso geral, os dois mecanismos são assintoticamente equivalentes. Ambos colocam os alunos em escolas classificadas aproximadamente de forma logarítmica em relação ao tamanho do mercado.

Por Que Isso Importa

Esta descoberta é um pouco desanimadora para os fãs do sistema de "Aceitação Imediata", mas é um alívio para a matemática. Ela nos diz que a "eficiência de Pareto" da IA é um pouco um miragem quando se trata de felicidade média. O mecanismo que é frequentemente criticado por ser injusto e manipulável não entrega, de fato, um resultado médio significativamente melhor do que aquele que é justo e difícil de trapacear.

O trabalho de Ortega estende essa descoberta para outras variações também. Quer as escolas tenham múltiplas vagas (correspondência muitos-para-um) ou se os alunos puderem pular escolas cheias (uma variação chamada "IA com saltos"), o resultado permanece: o ranking médio permanece em torno de $\log n$.

Portanto, da próxima vez que ouvir alguém argumentar que devemos usar o "mecanismo Boston" porque é mais eficiente, você pode sorrir e dizer: "Bem, talvez seja eficiente, mas não consegue colocar as crianças em escolas melhores, em média, do que o outro jeito". Na grande corrida da escolha escolar, ambos os corredores estão cruzando a linha de chegada quase ao mesmo tempo.