Justifiable Priority Violations

Este artigo propõe um novo critério endógeno para justificar violações de prioridade no mecanismo de Aceitação Diferida, demonstrando que ele permite melhorias de Pareto inatingíveis pelo modelo baseado em consentimento prévio e apresentando um algoritmo polinomial que converge para um emparelhamento eficiente dentro dessas restrições.

O essencial

Imagine que você é o diretor de uma escola e precisa distribuir vagas limitadas entre centenas de alunos. Cada aluno tem uma lista de preferências (quer ir para a Escola A, depois B, depois C) e cada escola tem uma lista de prioridades (quem tem irmão na escola, quem mora perto, quem tem notas melhores).

O método padrão usado no mundo todo para fazer essa distribuição é chamado de Alocação Deferrada (DA). Ele é justo e evita que ninguém fique com raiva de ter sido "pulado" por alguém com menos direito, mas tem um defeito: às vezes, ele deixa vagas vazias ou coloca alunos em escolas ruins, quando seria possível fazer um "troca de cadeiras" que deixaria todos mais felizes.

O problema é: como fazer essas trocas sem violar as regras de prioridade? Se o Aluno X tem prioridade sobre o Aluno Y na Escola A, você não pode simplesmente dar a vaga a Y, certo? Ou pode?

É aqui que entra o artigo de Josué Ortega e R. Pablo Arribillaga. Eles propõem uma nova maneira de pensar sobre essas "quebras de regra" para melhorar o sistema.

A Grande Metáfora: O Jogo de Troca de Cartas

Pense no sistema de escolas como um jogo de troca de cartas.

• O Método Padrão (DA): É como se cada jogador recebesse uma carta e o jogo acabasse. Ninguém pode trocar, mesmo que o João tenha uma carta que o Pedro quer, e o Pedro tenha uma que o João quer. O resultado é estável, mas pode ser ineficiente (ninguém fica com a melhor carta possível).
• A Solução Antiga (Consentimento Prévio): Para permitir trocas, o diretor pergunta a todos: "Você concorda em abrir mão da sua prioridade se isso ajudar alguém?". Se o João disser "sim", ele pode trocar. Se disser "não", ele fica onde está.
  • O problema: Às vezes, o João diz "não" porque não vê benefício imediato, mas se ele aceitasse, todo o grupo ganharia. Ou, pior, o sistema permite que o João troque, mas acaba prejudicando o Pedro (que disse "não") sem que o Pedro ganhe nada.

A Nova Ideia: "Justificabilidade" (Justifiable)

Os autores dizem: "Esqueça o 'sim' ou 'não' dado antes do jogo. Vamos olhar para o resultado final e perguntar: essa troca foi justificável?"

Eles criam três categorias de alunos para decidir quem pode ser "pulado":

1. Os Beneficiados: Alunos que, com a troca, vão para uma escola melhor. Eles não têm direito de reclamar se alguém com prioridade menor for colocado na frente deles, porque eles ganharam com a troca. É como se dissessem: "Ok, você pulou minha fila, mas no final eu ganhei uma cadeira melhor, então valeu a pena".
2. Os Impossíveis de Melhorar: Alunos que, não importa o que aconteça, nunca conseguiriam uma escola melhor do que a que o método padrão deu. Eles não têm nada a ganhar, então se alguém com prioridade menor pegar a vaga deles, não faz mal, pois eles já estavam no "pior cenário possível".
3. Os "Possíveis, mas Não Beneficiados" (O Problema): Alunos que poderiam ter ganhado com uma troca, mas não ganharam na troca específica escolhida. Aqui está a regra de ouro: Você NUNCA pode violar a prioridade deste grupo. Se você pular a fila de alguém que poderia ter ganho, mas não ganhou, isso é injustificável.

Em resumo: Você pode quebrar a regra de prioridade se a pessoa que foi "pula" ou ganhou com a troca, ou nunca poderia ter ganho de qualquer jeito. Mas você não pode pular quem poderia ter ganho e ficou de fora.

A Máquina Mágica: SJBC+

Como encontrar essas trocas perfeitas? Os autores criaram um algoritmo chamado SJBC+.

Imagine que o algoritmo é um detetive de trocas:

1. Ele começa fazendo as trocas mais seguras (aquelas que só pulam a fila de quem não tem chance de ganhar).
2. Depois, ele olha: "Quem ganhou com essa primeira troca? Ah, o João ganhou! Ótimo, agora que o João ganhou, ele 'consentiu' (de forma automática) em ter sua prioridade violada para ajudar o Pedro a ganhar também."
3. O algoritmo usa esse "consentimento" do João para fazer novas trocas, criando uma cadeia de melhorias.
4. Ele para apenas quando não há mais ninguém que possa ganhar sem prejudicar alguém que não ganhou.

Por que isso é melhor que pedir permissão antes?

O artigo mostra que pedir permissão antes (o método antigo) é limitado.

• Se você pede permissão, as pessoas podem ter medo de dizer "sim" e perder algo, ou o sistema pode travar porque ninguém quis abrir mão da prioridade.
• Com a "Justificabilidade", o sistema encontra soluções que o método de permissão nunca encontraria. Às vezes, o sistema consegue fazer uma troca que deixa 90% das pessoas felizes, mas o método de permissão só consegue deixar 50% felizes porque as pessoas não concordaram antes.

O Que os Números Dizem?

Os autores fizeram simulações com milhares de cenários aleatórios (como se fossem loterias de escolas).

• O método deles (SJBC+) conseguiu tornar o sistema perfeitamente eficiente (ninguém poderia ficar melhor sem que outro ficasse pior) em mais de 60% a 85% dos casos.
• O método antigo (pedindo permissão) só conseguiu isso em menos de 10% dos casos quando a permissão era parcial.
• Além disso, o método deles sempre respeita a regra de "justificabilidade", enquanto o método antigo, às vezes, acaba violando a prioridade de quem não ganhou nada, o que é injusto.

Conclusão Simples

Imagine que você está organizando uma festa e precisa sentar as pessoas.

• O método antigo pergunta: "Você aceita sentar longe da mesa principal se eu puder sentar seu amigo na mesa VIP?" Se a pessoa disser não, a festa fica meio vazia.
• O método novo diz: "Vamos sentar todo mundo. Se alguém sentar longe da mesa principal, mas ganhar um convite para a festa do ano seguinte, ou se essa pessoa nunca tivesse chance de entrar na festa de qualquer jeito, então está tudo bem. Mas se alguém poderia ter entrado e ficou de fora, não podemos fazer isso."

Esse novo método permite que a festa seja mais cheia, mais divertida e mais justa, sem precisar que todos concordem com tudo antes de começar. É uma forma inteligente de melhorar o sistema escolar sem quebrar a confiança das famílias.

Resumo técnico

Resumo Técnico: Violações de Prioridade Justificáveis

1. O Problema

O mecanismo de Atribuição Diferida (Deferred Acceptance - DA) é o padrão-ouro para escolha escolar, pois produz um emparelhamento estável e ótimo para os estudantes (não há outro emparelhamento estável que pareto-domine o DA). No entanto, o DA é frequentemente Pareto-ineficiente, gerando perdas de bem-estar significativas.

Para melhorar a eficiência do DA, é necessário violar as prioridades legais dos estudantes (ou seja, permitir que um estudante com menor prioridade em uma escola seja alocado nela em detrimento de um estudante com maior prioridade). A questão central do artigo é: quais violações de prioridade são justificáveis?

A abordagem dominante na literatura é o consentimento ex-ante (ex: mecanismo EADA), onde os estudantes concordam previamente em renunciar à sua prioridade se isso beneficiar outros. Os autores argumentam que essa abordagem tem limitações teóricas e práticas, propondo uma alternativa baseada em justificabilidade endógena.

2. Metodologia e Conceitos Fundamentais

Os autores introduzem uma nova classificação dos estudantes em relação a uma melhoria do DA:

1. Beneficiários: Estudantes que melhoram sua alocação em relação ao DA.
2. Inmelhoráveis (Unimprovable): Estudantes que, por definição, não podem ser beneficiados por nenhuma melhoria Pareto do DA.
3. Melhoráveis Não-Beneficiários: Estudantes que poderiam ter sido beneficiados por alguma melhoria, mas não o foram na melhoria escolhida.

Definição de Justificabilidade:
Uma violação de prioridade é considerada justificável se e somente se afetar apenas:

• Estudantes inmelhoráveis (que nunca ganhariam de qualquer forma); ou
• Beneficiários (que ganham com a melhoria específica).

Uma violação é injustificável se afetar um "melhorável não-beneficiário" (alguém que poderia ter ganho, mas não ganhou, e teve sua prioridade violada).

O Critério Endógeno:
Diferente do consentimento ex-ante, a justificabilidade é endógena: depende do resultado final da melhoria. Se um estudante se beneficia, ele "consente" implicitamente na violação de sua própria prioridade (ou de outros que também se beneficiam) como parte do processo de troca.

3. Contribuições Principais e Algoritmos

Os autores desenvolvem uma estrutura teórica e algoritmos para encontrar emparelhamentos que sejam justificados e eficientes:

A. Mecanismo "Just Below Cutoffs" (JBC)

• Objetivo: Encontrar uma melhoria fortemente justificável (Strongly Justifiable).
• Funcionamento: O algoritmo identifica escolas que rejeitaram estudantes "melhoráveis". Para cada escola, ele seleciona o estudante com a maior prioridade entre aqueles que estão logo abaixo da "cota" (cutoff) do DA, mas que preferem a escola à sua alocação atual.
• Propriedade: O JBC executa ciclos de troca disjuntos que violam apenas as prioridades de estudantes inmelhoráveis. Nenhuma prioridade de estudante melhorável é violada.
• Teorema 1: Se o DA é ineficiente, sempre existe uma melhoria fortemente justificável, e o JBC encontra o conjunto maximal de tais ciclos.

B. Algoritmo Sequencial SJBC+ (Sequential Just Below Cutoffs)

• Motivação: O JBC é muito conservador (apenas violações em inmelhoráveis). A justificabilidade permite violar prioridades de estudantes que se beneficiam. O SJBC+ expande o JBC iterativamente.
• Funcionamento:
  1. Começa com a alocação do JBC.
  2. Identifica novos caminhos de aumento (augmenting paths) em um grafo bipartido de estudantes melhoráveis.
  3. Permite violações de prioridade contra estudantes que já se tornaram beneficiários nas iterações anteriores.
  4. Itera até que nenhum novo beneficiário possa ser criado sem violar a justificabilidade.
  5. Inclui uma fase de refinamento para permutar alocações entre os beneficiários finais.
• Teorema 2: O SJBC+ produz um emparelhamento que:
  • Pareto-domina o DA.
  • É justificável.
  • Não pode ser Pareto-aperfeiçoado por nenhum outro emparelhamento justificável sem expandir estritamente o conjunto de beneficiários.
  • É computado em tempo polinomial.

4. Resultados Teóricos e Limitações

• Incompatibilidade com Eficiência Total (Proposição 1): Nem sempre é possível alcançar um emparelhamento que seja simultaneamente justificável e Pareto-eficiente. Às vezes, para atingir a eficiência total, seria necessário violar a prioridade de um "melhorável não-beneficiário", o que é proibido pelo critério.
• Limitações do Consentimento Ex-Ante (Teorema 3 e 4):
  • O mecanismo EADA (Efficiency-Adjusted DA) com consentimento total pode gerar resultados que não são justificáveis (viola prioridades de estudantes que não se beneficiam).
  • Existe um conflito estrutural em mecanismos baseados em consentimento: não é possível satisfazer simultaneamente (i) eficiência sempre que possível, (ii) eficiência restrita (constrained efficiency) e (iii) incentivos para consentir (onde consentir não prejudica o estudante).
• Diferenciação: A justificabilidade permite melhorias que o EADA não consegue alcançar sob nenhuma estrutura de consentimento, e vice-versa.

5. Resultados Empíricos (Simulações)

Os autores simularam mercados com 50 e 100 estudantes, comparando o SJBC+, o DA e o EADA (com 50% e 100% de consentimento).

• Eficiência: O SJBC+ alcança Pareto-eficiência em 63% a 85% dos casos, dependendo da estrutura de preferências. Em mercados correlacionados, o EADA com 50% de consentimento tem taxa de eficiência próxima de zero, enquanto o SJBC+ mantém mais de 70%.
• Beneficiários: O SJBC+ beneficia, em média, mais estudantes do que o EADA (mesmo com consentimento total).
• Justificabilidade: O SJBC+ é 100% justificável por construção. Em contraste, a taxa de justificabilidade do EADA cai drasticamente com o tamanho do mercado e a correlação de preferências (chegando a 0,3% em mercados grandes e correlacionados com consentimento total).
• Ranking Médio: O SJBC+ oferece melhorias significativas no ranking médio dos estudantes em comparação ao DA, com desempenho superior ao EADA com consentimento parcial.

6. Significado e Conclusão

O artigo propõe uma mudança de paradigma na escolha escolar:

1. Novo Paradigma Normativo: Substitui a necessidade de consentimento explícito (ex-ante) por uma justificativa ex-post baseada no benefício real obtido.
2. Viabilidade Prática: Demonstra que é possível recuperar grande parte da eficiência perdida pelo DA (frequentemente alcançando eficiência total) sem violar a lógica de justiça das prioridades, desde que as violações ocorram apenas em favor de quem ganha com a troca.
3. Limitações Reconhecidas: O trabalho admite que a eficiência total não é garantida teoricamente sob o critério de justificabilidade, mas as simulações mostram que essa restrição raramente é um obstáculo prático.

Em suma, o trabalho oferece uma ferramenta robusta (SJBC+) para autoridades educacionais que desejam melhorar a eficiência da alocação escolar mantendo uma defesa ética sólida contra violações arbitrárias de prioridade, superando as limitações dos mecanismos baseados em consentimento.