Resumo Técnico: Uma Teoria Geral da Proporcionalidade com Utilidades Aditivas

1. Definição do Problema

O artigo aborda o problema de selecionar um subconjunto viável de candidatos de um conjunto $C$ com base nas preferências dos eleitores, sujeito a restrições de viabilidade gerais definidas por uma família de subconjuntos $\mathcal{F} \subseteq 2^C$. Este arcabouço generaliza vários modelos estabelecidos na teoria da escolha social, incluindo:

• Eleições de comitê: Seleção de um número fixo de candidatos.
• Orçamento Participativo (OP): Seleção de projetos dentro de um orçamento total.
• Tomada de decisão pública e agregação de julgamentos: Tomada de decisões sobre múltiplas questões independentes.
• Restrições de diversidade: Garantia de propriedades estruturais específicas (ex: equilíbrio de gênero) no conjunto selecionado.

Embora axiomas de proporcionalidade (como a Representação Justificada) tenham sido definidos para este modelo geral, as regras existentes são projetadas primariamente para votos de aprovação (onde os eleitores atribuem utilidade 0 ou 1). O artigo foca no cenário mais complexo de utilidades aditivas, onde cada eleitor $i$ atribui uma utilidade numérica $u_i(c) \geq 0$ a cada candidato $c$. O objetivo é projetar regras que garantam representação justa para grupos coesos de eleitores sob estas restrições gerais e utilidades cardinais.

2. Metodologia

Os autores propõem duas abordagens algorítmicas primárias inspiradas no conceito de eleitores "comprando" candidatos com moeda virtual.

2.1 A Regra PropRank

O PropRank é uma regra sequencial inspirada na regra sequencial de Phragmén, mas adaptada para utilidades aditivas.

• Mecanismo: Os eleitores ganham dinheiro virtual a uma taxa constante ao longo do tempo. A regra simula um processo de compra onde os eleitores decidem quanto gastar em candidatos.
• Mecanismo de Previsão (Foresight): Diferente das abordagens gananciosas (greedy) padrão, o PropRank prevê oportunidades futuras. Os eleitores calculam um "fator de escala" $\lambda_i$ baseado na melhor razão possível entre pagamento e utilidade que poderiam alcançar se esperassem por um candidato mais desejável para se tornar acessível.
• Função de Gasto: Um eleitor $i$ concorda em gastar no máximo $x_i(c, r)$ no candidato $c$ na rodada $r$, definido por uma fórmula envolvendo o orçamento atual do eleitor, a utilidade do candidato e o fator de escala. Isso garante que a razão pagamento-utilidade não exceda a melhor compra fracionária disponível.
• Ranking: O algoritmo constrói um ranking completo de candidatos por seus carimbos de tempo (timestamps) de compra. Como os candidatos inviáveis não são removidos durante o processo (apenas ao final da construção do ranking para tamanhos de comitê específicos), cada prefixo do ranking satisfaz a proporcionalidade.

2.2 Método Generalizado de Partes Iguais (MES)

Os autores estendem o Método de Partes Iguais (originalmente para OP) para restrições gerais.

• Estrutura: O algoritmo opera em rodadas. Em cada rodada, determina a quantidade máxima de dinheiro que pode ser alocada aos eleitores de modo que a sub-rotina de "Partes Iguais" possa comprar um conjunto de candidatos sem violar as restrições de viabilidade.
• Previsão no MES: Semelhante ao PropRank, o MES generalizado incorpora um mecanismo de previsão. Ele calcula limites superiores de gastos ($capi$) para evitar que os eleitores gastem cedo demais em candidatos que possam ser menos eficientes do que os disponíveis em iterações futuras.
• Heurísticas de Backtracking: O artigo introduz variantes heurísticas (PropRankRem, PropRankBacktrack) que reiniciam o procedimento ou realizam o backtracking quando candidatos são removidos, visando reduzir orçamentos não gastos e melhorar o desempenho prático, embora estas careçam das mesmas garantias teóricas das regras base.
• Gasto Limitado (BOS): Uma adaptação do método BOS é proposta para restrições gerais, onde o algoritmo identifica o maior carimbo de tempo válido para compra antes que a viabilidade seja violada.

3. Contribuições Principais

3.1 Arcabouço Teórico

• Axiomas de Proporcionalidade para Utilidades Aditivas: O artigo generaliza axiomas como a Representação Justificada Estendida (EJR) e a Representação Justificada Proporcional (PJR) para o cenário de utilidade aditiva com restrições gerais.
• Grau de Proporcionalidade: Os autores definem e analisam o "grau de proporcionalidade", quantificando a satisfação média de um grupo coeso. Eles estabelecem a relação entre EJR e o grau de proporcionalidade, mostrando que, para restrições gerais, a garantia depende do tamanho do grupo coeso ($\gamma = |S|/n$).

3.2 Garantias Teóricas

• Garantias do PropRank:
  • Para restrições de Orçamento Participativo, o PropRank satisfaz um grau de proporcionalidade de $d(\alpha) = (\alpha - u_{max})/2$.
  • Para restrições gerais, satisfaz um grau de $d(\alpha) \geq \alpha \cdot \frac{1-\gamma}{2} - \frac{u_{max}}{2}$.
  • Para restrições de Matroide, satisfaz um grau de proporcionalidade fraco de $(\alpha - u_{max})/2$.
• Garantias de PJR: As regras satisfazem garantias de grau de PJR de $d(\alpha) = (\alpha - u_{max})/(\kappa + 1)$, onde $\kappa$ é um parâmetro que controla a flexibilidade de gasto.

3.3 Extensões Algorítmicas

• O artigo fornece a primeira generalização do Método de Partes Iguais para restrições de viabilidade arbitrárias com utilidades aditivas.
• Introduz heurísticas (PropRankRem, PropRankBacktrack) para lidar com a questão de orçamentos não gastos em cenários práticos.

4. Resultados Experimentais

Os autores avaliaram suas regras em mais de 1.300 instâncias reais de orçamento participativo do dataset Pabulib.

• Métricas: A avaliação foi baseada em violações de EJR+ (proporcionalidade), Razão de Exclusão (fração de eleitores com utilidade zero) e Custo-Satisfação Média (eficiência utilitária).
• Descobertas:
  • Parâmetro $\kappa$: Os experimentos indicam que o PropRank com $\kappa = 1$ (permitindo maior flexibilidade de gasto) performa significativamente melhor em termos de proporcionalidade (menos violações de EJR+) do que $\kappa = 0$.
  • Heurísticas: As variantes heurísticas (PropRankRem, PropRankBacktrack) combinadas com $\kappa = 0$ mostraram pouquíssimas violações de EJR+ e razões de exclusão favoráveis, frequentemente superando o PropRank base em métricas práticas, apesar de carecerem de provas formais para essas heurísticas específicas.
  • Adaptação BOS: O Método de Partes Iguais adaptado com Gasto Limitado (Bounded Overspending) teve um desempenho excepcional, superando o BOS-PB original em violações de EJR+ e igualando-o em razão de exclusão e utilidade. Também foi observado como o mais eficiente computacionalmente entre as técnicas propostas.
  • Comparação: As regras propostas geralmente alcançaram custo-satisfação comparável ou superior às regras existentes específicas de PB (MES-PB, BOS-PB), enquanto lidam com restrições gerais.

5. Significância e Alegações

O artigo afirma fornecer uma teoria geral da proporcionalidade que une modelos específicos (como eleições de comitê e OP) ao panorama mais amplo de problemas de seleção com restrições.

• Generalização: Demonstra que métodos estabelecidos (Phragmén e Partes Iguais) podem ser estendidos para restrições de viabilidade arbitrárias e utilidades aditivas sem perder suas propriedades centrais de proporcionalidade.
• Ranking: Uma contribuição significativa é a capacidade de gerar rankings proporcionais (onde cada prefixo é um comitê proporcional) no cenário de utilidade aditiva, preenchendo uma lacuna na literatura.
• Praticidade: Embora as garantias teóricas sejam fortes, os autores observam modestamente que as variantes heurísticas, que sacrificam parte da tratabilidade teórica para obter melhor desempenho prático (reduzindo orçamentos não gastos), são altamente eficazes em instâncias do mundo real.
• Limitações: O artigo reconhece que as técnicas de prova para os algoritmos base não se estendem diretamente às variantes heurísticas, e que a complexidade computacional das heurísticas de backtracking pode ser exponencial (mitigada por um parâmetro $\sigma$).

Em resumo, o trabalho estabelece uma base teórica robusta para a representação proporcional sob restrições gerais e utilidades aditivas, oferecendo tanto algoritmos provadamente justos quanto heurísticas práticas que performam bem em dados reais.