Resumo Técnico: Transporte Ótimo sob Restrições de Equidade de Grupo

1. Enunciado do Problema

O artigo aborda o desafio de garantir a equidade de grupo (group fairness) em mecanismos de correspondência (matching) algorítmicos, que são cada vez mais utilizados para alocar recursos escassos (ex: empregos, admissões escolares, trocas de rins). Embora o Transporte Ótimo (OT) padrão forneça um arcabouço poderoso para parear duas distribuições com base na similaridade de características, ele pode inadvertidamente reforçar ou amplificar disparidades existentes se as características estiverem correlacionadas com atributos sensíveis (ex: status socioeconômico ou etnia).

Os autores formalizam uma nova noção de equidade de grupo para OT. Diferente de trabalhos anteriores focados em equidade individual ou restrições específicas (como participação mínima), esta abordagem permite que um planejador central especifique uma matriz de alvo de equidade $F$. Esta matriz define a probabilidade desejada de parear indivíduos de qualquer grupo $s$ na população de origem com qualquer grupo $w$ na população de destino. O objetivo é encontrar um plano de transporte que minimize o custo de transporte enquanto satisfaz essas restrições explícitas de massa intergrupal.

2. Metodologia

O artigo propõe uma hierarquia de abordagens para resolver este problema, variando de restrições exatas a formulações relaxadas.

2.1. Equidade Exata: FairSinkhorn

Para cenários que exigem adesão estrita aos alvos de equidade, os autores definem o problema de OT com equidade $F$ (F-fair Optimal Transport). Isso envolve minimizar o objetivo de OT entrópico sujeito a restrições lineares onde a massa marginal entre os grupos $(s, w)$ deve ser igual a $F_{sw}$.

• Algoritmo: Eles derivam um algoritmo Sinkhorn modificado, denominado FairSinkhorn. Ao analisar a formulação dual, eles mostram que a solução retém a estrutura multiplicativa das iterações padrão do Sinkhorn, mas inclui um passo de projeção adicional para impor as restrições de nível de grupo.
• Garantia Teórica: Sob a suposição de medidas de suporte compacto, eles provam a existência e unicidade do plano de OT equitativo.

2.2. Estratégias de Equidade Aproximada

Reconhecendo que a equidade exata pode degradar significativamente a qualidade do pareamento (o "preço da equidade"), os autores propõem duas estratégias de relaxação:

A. OT com Penalidade de Equidade

Esta abordagem incorpora a violação de equidade como um termo de penalidade no objetivo:
$$\min_{\Pi} \text{Tr}[\Pi^\top C] + \varepsilon \text{KL}(\Pi) + \lambda L_F(\Pi)$$
onde $L_F(\Pi)$ é o erro quadrático entre as probabilidades reais de pareamento de grupo e o alvo $F$, e $\lambda$ controla o trade-off.

• Otimização: O problema permanece convexo. É resolvido usando um algoritmo de gradiente condicional generalizado, onde cada iteração lineariza a penalidade de equidade e resolve um subproblema (um OT entrópico com custo modificado) via o algoritmo Sinkhorn padrão.
• Complexidade de Amostragem: Os autores derivam um novo limite de complexidade de amostra finita para este problema penalizado. Eles mostram que o erro de estimativa escala como $O(n^{-1/2})$, acompanhando o OT entrópico padrão, implicando que adicionar a penalidade de equidade não reduz a eficiência estatística.

B. Aprendizado de Custo via Otimização Bilevel

Esta estratégia aprende uma função de custo de base $c_\theta$ tal que o plano de OT resultante satisfaça naturalmente os alvos de equidade.

• Formulação: Um problema de otimização bilevel é proposto onde o loop externo minimiza a perda de equidade $L_F(\Pi_\varepsilon(c_\theta))$ em relação aos parâmetros de custo $\theta$, e o loop interno resolve o problema de OT para um custo fixo.
• Parametrizações: A função de custo pode ser parametrizada como uma distância de Mahalanobis (transformação linear de características) ou via redes neurais (embeddings não lineares).
• Generalização: Uma vantagem fundamental é a reutilização; uma vez que $c_\theta$ é aprendido, ele pode ser aplicado a novas amostras não vistas usando o OT padrão sem reotimização.
• Garantia Teórica: Os autores estabelecem um limite uniforme sobre o desvio da equidade entre a solução da população e as aproximações de amostra finita para qualquer custo na família parametrizada. O limite depende do tamanho da amostra e da limitação da função de custo.

3. Principais Contribuições

1. Nova Noção de Equidade: Introdução de uma definição de equidade de grupo baseada em alvos e flexível para OT, permitindo que planejadores especifiquem arbitrárias probabilidades de pareamento intergrupal.
2. Algoritmos:
   • FairSinkhorn: Um solver exato para planos de OT equitativos.
   • OT Penalizado: Uma relaxação convexa que permite trade-offs ajustáveis entre custo e equidade.
   • Aprendizado de Custo: Um arcabouço de otimização bilevel para aprender custos que induzam pareamentos equitativos, permitindo a generalização para novos dados.
3. Análise Teórica:
   • Prova de existência/unicidade para o OT com equidade exata.
   • Derivação de um limite de complexidade de amostragem para o OT entrópico penalizado (mostrando convergência de $O(n^{-1/2})$).
   • Derivação de um limite de desvio uniforme para a abordagem de aprendizado de custo, garantindo equidade em dados não vistos.
4. Validação Empírica: Experimentos com dados sintéticos (misturas Gaussianas e distribuições circulares) e um conjunto de dados semissintético de um aplicativo de namoro demonstram a eficácia das abordagens e os trade-offs entre custo e equidade.

4. Resultados

• Controle de Trade-off: A abordagem penalizada interpola com sucesso entre o OT vanilla (baixo custo, alta desigualdade) e o FairSinkhorn (equidade perfeita, alto custo), permitindo controle refinado via o parâmetro de penalidade $\lambda$.
• Sensibilidade à Geometria: Em conjuntos de dados sintéticos, a abordagem penalizada geralmente alcança um melhor trade-off custo-equidade do que o aprendizado de custo quando a geometria dos dados é complexa (ex: distribuições circulares), pois o OT penalizado não impõe restrições estruturais ao mapa de transporte. No entanto, o aprendizado de custo com redes neurais pode aproximar alvos complexos onde custos lineares (Mahalanobis) falham.
• Generalização: No experimento de "reutilização", os custos aprendidos (tanto Mahalanobis quanto MLP) mantiveram níveis de equidade em novas amostras de teste comparáveis ao desempenho de treinamento, superando significativamente o OT vanilla. O tempo de inferência para aplicar um custo aprendido foi significativamente menor do que resolver um novo OT penalizado para cada novo lote.
• Aplicação no Mundo Real: No conjunto de dados do aplicativo de namoro (alta dimensionalidade, múltiplos grupos), os métodos reproduziram o trade-off convexo custo-equidade observado em configurações sintéticas, validando sua aplicabilidade a cenários complexos do mundo real.

5. Significância e Alegações

O artigo afirma fornecer um arcabouço principiado para reguladores e designers de mercado para impor alvos de equidade em mecanismos de correspondência. Ao enquadrar a equidade como restrições de massa explícitas entre grupos, este trabalho preenche a lacuna entre a teoria do transporte ótimo e requisitos práticos de políticas (ex: cotas, metas de diversidade).

Os autores enfatizam que seu trabalho:

• Oferece uma definição flexível de equidade que pode acomodar vários objetivos legislativos ou políticos (ex: a "regra dos quatro quintos" ou cotas de diversidade).
• Fornece garantias teóricas tanto sobre a eficiência estatística da abordagem penalizada quanto sobre a capacidade de generalização da abordagem de aprendizado de custo.
• Destaca o trade-off entre eficiência (custo de transporte) e equidade, demonstrando que, embora a equidade exata seja possível, abordagens relaxadas frequentemente oferecem um equilíbrio mais prático.

O artigo conclui observando limitações: o arcabouço atual foca em equidade de grupo e não se estende diretamente à equidade individual. Além disso, embora os métodos otimizem o processo de pareamento, o artigo reconhece que o design do próprio alvo de equidade permanece uma decisão política e ética fora do escopo do algoritmo. Sugere-se que trabalhos futuros explorem a equidade individual, análises mais profundas do trade-off entre equidade e viés, e a modelagem do impacto dos pareamentos nos resultados individuais.