Resumo Técnico: Representação Proporcional em Agregação de Rankings

Definição do Problema

O artigo aborda o problema da agregação de rankings, onde o objetivo é combinar um perfil de rankings de entrada ponderados em um único ranking de saída. Neste cenário, um perfil $R$ consiste em um conjunto de candidatos $C$ e uma função que mapeia cada ranking possível $\succ$ para um peso $R(\succ) \in [0, 1]$, de tal forma que a soma de todos os pesos seja igual a 1. Esses pesos representam a importância de diferentes critérios (por exemplo, preço vs. avaliação em uma reserva de hotel) ou a parcela de eleitores que apoia um ranking específico.

O desafio central identificado é que as Funções de Bem-Estar Social (SWFs) clássicas, como a regra de Kemeny, a contagem de Borda e as regras do tipo Condorcet, são inerentemente majoritárias. Elas tendem a selecionar o ranking de saída que minimiza a distância em relação ao ranking de maior peso, efetivamente ignorando as preferências das minorias. Por exemplo, se dois rankings inversos possuem pesos de 51% e 49%, as SWFs padrão frequentemente retornam apenas o ranking de 51%, falhando em representar o grupo de 49%. O artigo busca projetar SWFs que garantam a representação proporcional, assegurando que cada ranking de entrada influencie a saída proporcionalmente ao seu peso.

Metodologia e Estrutura

Os autores formalizam a proporcionalidade definindo a utilidade de um ranking de entrada $\succ$ para um ranking de saída $\triangleright$ como o número de concordâncias entre pares entre eles:
$$u(\succ, \triangleright) = |\{(x, y) \in C^2 : x \succ y \text{ e } x \triangleright y\}|$$
Como existem $\binom{m}{2}$ comparações entre pares no total para $m$ candidatos, um ranking de entrada com peso $\alpha$ deve idealmente obter uma utilidade de pelo menos $\lfloor \alpha \binom{m}{2} \rfloor$.

O artigo introduz uma hierarquia de axiomas de proporcionalidade inspirados na votação de comitê baseada em aprovação e no orçamento participativo:

1. Representação Justificada Unânime (uJR): Um enfraquecimento que exige que qualquer ranking de entrada com peso $\ge 1/\binom{m}{2}$ obtenha pelo menos uma concordância entre pares.
2. Representação Justificada Proporcional Unânime (uPJR): O axioma central que exige que um ranking de entrada com peso $\alpha$ obtenha utilidade de pelo menos $\lfloor \alpha \binom{m}{2} \rfloor$.
3. Representação Justificada Proporcional Forte (sPJR): Um fortalecimento que estende a garantia para grupos de rankings. Se um subperfil $S$ possui peso total $\alpha$, a saída deve concordar com pelo menos $\lfloor \alpha \binom{m}{2} \rfloor$ comparações entre pares da união dos rankings em $S$.

Para alcançar esses axiomas, os autores adaptam o conceito de preçabilidade (priceability) do orçamento participativo. Eles modelam a construção do ranking de saída como um processo de compra sequencial onde candidatos (ou pares de candidatos) são "comprados" usando os orçamentos dos rankings de entrada.

Contribuições Principais e Resultados

1. Limitações de Métodos Existentes

O artigo analisa primeiro a Regra de Kemeny Quadrática (proposta por Lederer et al. [2024] para ranking proporcional). Os autores provam que, para $m \ge 5$, a Regra de Kemeny Quadrática falha até mesmo no axioma mais fraco, uJR. Especificamente, eles constroem perfis onde um ranking de entrada com peso significativo recebe utilidade zero da saída da Regra de Kemeny Quadrática, demonstrando a necessidade de novos mecanismos.

2. A Regra de Borda Sequencial Proporcional (PSB)

Para satisfazer a uPJR, os autores propõem a Regra de Borda Sequencial Proporcional (PSB).

• Mecanismo: A PSB opera sequencialmente. Em cada rodada, ela seleciona o candidato que maximiza a pontuação de Borda ponderada com base nos orçamentos atuais. Em seguida, ela atualiza os orçamentos dos rankings de entrada proporcionalmente à contribuição de cada um para a pontuação do candidato selecionado, efetivamente "pagando" pela colocação do candidato.
• Garantia Teórica: Os autores introduzem um axioma estruturado chamado rank-preçabilidade (rank-priceability), que espelha a preçabilidade no orçamento participativo. Eles provem que a rank-preçabilidade implica uPJR.
• Resultado: O Teorema 4.5 estabelece que a PSB satisfaz a rank-preçabilidade e, consequentemente, a uPJR.
• Garantia Quantitativa: Além da satisfação axiomática, o Teorema 4.6 prova que a PSB garante a cada subperfil $S$ uma utilidade média de pelo menos $\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$. Isso fornece um limite inferior linear de utilidade em relação ao peso do grupo.

3. A Regra de Borda com Ajuste de Fluxo (FB)

Os autores mostram que a PSB falha na sPJR porque seu esquema de pagamento não protege adequadamente grupos de rankings que atuam em conjunto. Para resolver isso, eles introduzem a pair-preçabilidade (pair-priceability), um axioma refinado onde os pagamentos são feitos para pares específicos de candidatos, em vez de apenas postos (ranks).

• Mecanismo: A Regra de Borda com Ajuste de Fluxo (FB) é um refinamento da PSB. Assim como a PSB, ela seleciona o vencedor de Borda sequencialmente. No entanto, em vez de um pagamento proporcional simples, a FB determina os pagamentos resolvendo um problema de fluxo máximo em uma rede construída. Esta rede garante que a razão custo por utilidade seja minimizada, respeitando as restrições de orçamento e de pares.
• Resultado: O Teorema 5.5 prova que a FB satisfaz a pair-preçabilidade, que por sua vez implica sPJR (Teorema 5.3).
• Garantia Quantitativa: O Teorema 5.6 mostra que a FB fornece a mesma garantia de utilidade média linear da PSB ($\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$), garantindo forte equidade tanto para indivíduos quanto para grupos.

4. Variantes Adicionais

No apêndice, os autores discutem o Método de Partes Iguais Rankeado (RMES), uma variante inspirada no Método de Partes Iguais (MES) do orçamento participativo. Eles mostram que o RMES satisfaz a rank-preçabilidade (e, portanto, a uPJR) e oferece um perfil utilitário ligeiramente diferente, selecionando os primeiros $\lfloor m/4 \rfloor$ candidatos puramente com base nas pontuações iniciais de Borda.

Significância e Alegações

O artigo afirma apresentar as primeiras Funções de Bem-Estar Social verdadeiramente proporcionais para agregação de rankings. Sua principal significância reside em:

• Ponte entre Campos: Ele transfere com sucesso resultados profundos da votação de comitê baseada em aprovação e do orçamento participativo (especificamente PJR e preçabilidade) para o domínio da agregação de rankings.
• Resolução de um Problema Aberto: Resolve o problema aberto de projetar SWFs que satisfaçam uPJR e sPJR, algo que tentativas anteriores (como a Kemeny Quadrática) não conseguiram alcançar.
• Força Axiomática e Quantitativa: As regras propostas (PSB e FB) não apenas são provadas para satisfazer condições de equidade axiomática forte, mas também fornecem garantias quantitativas robustas sobre a utilidade média para qualquer grupo de eleitores, garantindo que as preferências das minorias não sejam sistematicamente ignoradas.

Os autores observam que, embora seu trabalho foque no acordo entre pares como a métrica de utilidade, esta é uma abordagem padrão na literatura. Eles sugerem que trabalhos futuros poderiam explorar noções de equidade mais fortes (como EJR ou estabilidade do núcleo) e funções de utilidade mais gerais que levem em conta o valor variável de diferentes posições no ranking.