The Distribution of Envy in Matching Markets

Resumo Técnico: A Distribuição da Inveja em Mercados de Emparelhamento

1. Problema e Motivação

O artigo investiga a distribuição da "inveja" em mercados de emparelhamento aleatórios de dois lados, especificamente sob o algoritmo de Aceitação Diferida (Deferred Acceptance - DA). Embora a estabilidade (ausência de inveja justificada) seja o critério padrão para mecanismos como a escolha escolar, o foco deste trabalho é quantificar a inveja total (injustificada ou não).

Os autores concentram-se em duas categorias específicas de agentes (estudantes) no lado proponente:

1. Estudantes que não invejam ninguém: Aqueles que são atribuídos à sua primeira escolha (ou que não preferem nenhum outro parceiro ao seu).
2. Estudantes que ninguém inveja: Aqueles que são tão desejados que nenhum outro agente prefere o seu parceiro ao seu próprio.

A relevância deste estudo baseia-se em três pilares:

• Eficiência Pareto: O DA não é necessariamente Pareto-eficiente. Entender a distribuição da inveja ajuda a identificar a magnitude de melhorias possíveis.
• Bem-estar: A proporção de estudantes que obtêm sua primeira escolha é uma métrica de bem-estar comum usada por formuladores de políticas.
• Limites de Melhoria: Estudantes que não invejam ninguém ou que não são invejados por ninguém são "improváveis" (unimprovable); não podem ser melhorados através de trocas a partir do resultado do DA. Quantificar esses grupos estabelece um limite inferior para o número de agentes que podem ser melhorados.

2. Metodologia e Modelo

• Configuração do Mercado: O modelo considera um mercado de escolha escolar com $n$ estudantes e $n$ escolas (um-para-um). As preferências dos estudantes e as prioridades das escolas são estritas, completas e desenhadas independentemente e uniformemente ao acaso (i.i.d.).
• Mecanismo: O algoritmo de Aceitação Diferida (DA) é implementado na sua versão sequencial proposta por McVitie e Wilson (1971).
• Ferramentas Analíticas:
  • Problema do Coleccionador de Cupons (Coupon Collector Problem): Utilizado para modelar a dinâmica das propostas e a descoberta de escolas.
  • Princípio da Decisão Diferida (Principle of Deferred Decisions): As preferências são geradas "sob a demanda" (on the fly) durante a execução do algoritmo para facilitar a análise probabilística.
  • Análise Assintótica e Exata: O artigo deriva expressões exatas para mercados finitos e limites assintóticos para mercados grandes.
  • Simulações: Validação empírica através de 2.000 instâncias aleatórias para diferentes tamanhos de mercado ($n$).

3. Principais Resultados

A. Estudantes que Ninguém Inveja (Under-demanded Schools)

O artigo define $NE_n$ como o número esperado de estudantes atribuídos a escolas "subdemandadas" (escolas que recebem propostas de exatamente um estudante distinto durante toda a execução do DA).

• Resultado Exato (Proposição 1): O número esperado de estudantes que ninguém inveja é exatamente o $n$-ésimo número harmônico:
  $$NE_n = H_n = \sum_{k=1}^{n} \frac{1}{k}$$
• Comportamento Assintótico: Como $H_n \approx \ln(n) + \gamma$, o número de estudantes não invejados cresce apenas logaritmicamente com o tamanho do mercado.
• Implicação: A fração de estudantes não invejados tende a zero ($NE_n/n \to 0$) quando $n \to \infty$. Para um mercado de 10.000 alunos, espera-se que menos de 10 alunos não sejam invejados.
• Conexão Técnica: O número de escolas subdemandadas no DA coincide com o número de "cupons únicos" (singleton coupon types) no problema clássico do coleccionador de cupons no momento de parada.

B. Estudantes que Não Invejam Ninguém (Top Choices)

Define-se $EN_n$ como o número esperado de estudantes que obtêm sua primeira escolha (não invejam ninguém).

• Distribuição de Ranks: A distribuição dos ranks (posições) das atribuições sob o DA aproxima-se de uma distribuição geométrica com parâmetro $1/H_n$.
• Resultado Assintótico (Corolário 1): Para $n$ suficientemente grande:
  $$EN_n \approx \frac{n}{H_n}$$
• Implicação: Embora este número seja maior do que o de estudantes não invejados, ele ainda representa uma fração vanishing (que tende a zero) do mercado total. Por exemplo, para $n=10.000$, estima-se que cerca de 1.100 estudantes obtenham sua primeira escolha, o que é uma fração pequena (11%).

C. Comparação com Ditadura Serial Aleatória (RSD)

Os autores comparam o DA com a Ditadura Serial Aleatória (RSD), onde os estudantes escolhem em ordem aleatória.

• Estudantes que não invejam ninguém:
  • DA: $\approx n / H_n$ (cresce sublinearmente).
  • RSD: $(n+1)/2$ (constante, cerca de 50% dos estudantes).
  • Conclusão: O RSD é muito superior em termos de alocação de primeiras escolhas.
• Estudantes que ninguém inveja:
  • DA: $H_n$.
  • RSD: $H_n$.
  • Descoberta Surpreendente: Ambos os mecanismos produzem exatamente o mesmo número esperado de estudantes que ninguém inveja, apesar de suas estruturas serem fundamentalmente diferentes. Este resultado também se estende ao mecanismo de Top Trading Cycles (TTC) com endowments aleatórios.

4. Contribuições Chave

1. Fórmula Exata para Mercados Finitos: A derivação de $NE_n = H_n$ é válida para qualquer $n$ inteiro positivo, não apenas assintoticamente, o que é raro na literatura de mercados aleatórios.
2. Conexão com o Problema do Cupom: Estabelece uma ligação rigorosa entre a implementação sequencial do DA e o problema do coleccionador de cupons, permitindo o uso de resultados conhecidos sobre cupons únicos.
3. Caracterização da "Improvabilidade": Demonstra que a fração de agentes que são garantidamente "improváveis" (seja por não invejarem ninguém ou por não serem invejados) tende a zero à medida que o mercado cresce.
4. Universalidade do $H_n$: A descoberta de que tanto o DA quanto o RSD resultam em $H_n$ estudantes não invejados sugere que esta é uma propriedade fundamental dos mercados aleatórios, e não uma falha específica de um mecanismo.

5. Significado e Conclusão

O trabalho conclui que, em mercados grandes e aleatórios, o algoritmo de Aceitação Diferida gera uma distribuição de inveja onde a vasta maioria dos participantes está envolvida em ciclos de inveja.

• Poucos estudantes são "satisfeitos" (primeira escolha) e poucos são "invejados" (alocados a escolas que ninguém prefere).
• A comparação com o RSD revela que, embora o DA seja inferior em termos de alocação de primeiras escolhas, a quantidade de agentes que ninguém inveja é um invariante entre mecanismos aleatórios comuns.
• O artigo sugere que a melhoria de Pareto sobre o resultado do DA é limitada apenas por uma fração vanishing do mercado, indicando que, em grandes mercados aleatórios, o DA é "quase" Pareto-eficiente no sentido de que quase todos os agentes podem ser melhorados, mas o número de agentes que não podem ser melhorados é insignificante em termos relativos.

Códigos JEL: C78.
Palavras-chave: Emparelhamento de dois lados, mercados aleatórios, Aceitação Diferida, Problema do Cupom.