Verification of Stochastic Dominance Envy-Freeness in Time Proportional to Input Size

Resumo Técnico: Verificação de Inveja de Dominância Estocástica em Tempo Proporcional ao Tamanho da Entrada

Definição do Problema
O artigo aborda o problema computacional de verificar a equidade na alocação de bens indivisíveis entre $n$ agentes e $m$ itens. Diferente dos modelos tradicionais que exigem valorações cardinais exatas, este trabalho opera sob preferências ordinais, onde os agentes fornecem um ranking de itens do mais preferido para o menos preferido. Os critérios de equidade específicos investigados são:

1. Inveja de Dominância Estocástica (SD-EF): Uma alocação é SD-EF se nenhum agente prefere o conjunto de outro agente sobre o seu próprio sob qualquer valoração aditiva consistente com sua classificação ordinal. Formalmente, para cada agente $i$ e qualquer outro agente $j$, o conjunto do agente $i$ deve dominar estocasticamente o conjunto do agente $j$.
2. SD-EF até Um Bem (SD-EF1): Uma relaxação da SD-EF onde qualquer inveja que um agente sinta em relação a outro pode ser eliminada pela remoção hipotética de um único item do conjunto do agente invejado.

O desafio central é determinar se uma determinada alocação satisfaz essas propriedades de forma eficiente. Trabalhos anteriores por Aziz (2016) estabeleceram que essas propriedades são verificáveis em tempo polinomial, mas exigiam $\mathcal{O}(n^2 m)$ operações. Essa dependência quadrática no número de agentes ($n$) cria um overhead significativo em sistemas de larga escala, especialmente dado que o tamanho da entrada (uma matriz de preferências e uma alocação) é apenas $\mathcal{O}(nm)$.

Metodologia
Os autores propõem um algoritmo de tempo ótimo que reduz a complexidade de verificação para $\mathcal{O}(nm)$, correspondendo assintoticamente ao tamanho da entrada. A metodologia afasta-se do paradigma de comparação por pares utilizado em abordagens anteriores (que verifica explicitamente cada par de agentes) ao utilizar uma verificação de dominância de prefixo de passagem única por agente combinada com inicialização preguiçosa (lazy initialization).

Componentes técnicos principais incluem:

• Condição de Dominância de Prefixo: O algoritmo itera através da lista de preferências de um agente do mais preferido para o menos preferido. Ele rastreia a contagem cumulativa de itens alocados para cada agente dentro do prefixo atual da lista de preferências. Uma violação de SD-EF ocorre se, em qualquer ponto da iteração, a contagem para o agente sendo avaliado for estritamente menor que a contagem de qualquer outro agente.
• Lema 1 (Ordenação Total Estrita): Os autores provam que, se uma violação de SD-EF ocorrer em um item específico $g$ na lista de preferências do agente $i$, então $g$ deve ser alocado a outro agente $j$, não a $i$. Isso permite que o algoritmo foque na detecção do primeiro ponto de divergência em vez de reavaliar todos os pares.
• Inicialização Preguiçosa com Dirty Bits: Para evitar o overhead de $\mathcal{O}(n)$ ao resetar contadores para cada lista de preferências de um agente (o que resultaria em $\mathcal{O}(n^2 + nm)$), o algoritmo utiliza um array de "dirty bits". Este array rastreia se um contador para um agente específico foi inicializado na iteração atual. Os contadores são inicializados apenas quando um item alocado de um agente específico é encontrado pela primeira vez na iteração da lista de preferências atual.
• Extensão para SD-EF1: Para a relaxação SD-EF1, o algoritmo incorpora uma regra de tratamento específica: ao avaliar a inveja do agente $i$ em relação ao agente $j$, o algoritmo identifica o item mais preferido no conjunto de $j$ (segundo a classificação de $i$) e efetivamente o ignora (simulando sua remoção) durante a comparação de contagem de prefixo.
• Tratamento de Ordenação Total Fraca: Para acomodar empates nas preferências (ordenação fraca), o algoritmo processa itens em "lotes" de preferência igual. Ele mantém o contador máximo de bens entre todos os outros agentes e realiza a verificação de dominância apenas após o processamento de um lote inteiro de itens de preferência igual, garantindo a correção sem custo assintótico adicional.

Principais Contribuições e Resultados

• Redução de Complexidade: A principal contribuição é a redução do tempo de verificação de $\mathcal{O}(n^2 m)$ para $\mathcal{O}(nm)$.
• Otimalidade Assintótica: Como a entrada consiste em uma matriz de preferências $n \times m$ e uma alocação, o algoritmo proposto de $\mathcal{O}(nm)$ é assintoticamente ótimo em relação ao tamanho da entrada. É impossível verificar essas propriedades mais rápido do que ler a entrada.
• Limites Teóricos: O artigo fornece um limite de complexidade definitivo para a verificação de noções ordinais de equidade, fechando a lacuna entre o tamanho da entrada e o custo de verificação.
• Corretude Algorítmica: Os autores fornecem provas formais (via indução e invariantes) demonstrando que a abordagem de passagem única com inicialização preguiçosa identifica corretamente violações de ambas as SD-EF e SD-EF1 sob preferências de ordenação total estrita e fraca.

Significância
O artigo afirma que este resultado fornece uma solução definitiva para a eficiência computacional da verificação de equidade ordinal. Ao eliminar a dependência quadrática no número de agentes, o algoritmo torna a verificação de SD-EF e SD-EF1 viável para sistemas multiagentes de larga escala onde $n$ é substancial. O trabalho serve como um sub-rotina crítica para ferramentas de auditoria automatizada e frameworks de design de mecanismos, garantindo que as garantias de equidade possam ser verificadas eficientemente sem exigir as comparações de pares computacionalmente caras dos métodos anteriores. Os autores observam que pesquisas futuras poderiam explorar se esta complexidade de tempo linear se mantém para configurações mais complexas, como a divisão de tarefas (chores) ou maná misto, onde as utilidades dos itens podem ter sinais heterogêneos.