Proportionality Degree in Participatory Budgeting

Este estudo inicia a análise do grau de proporcionalidade no orçamento participativo, demonstrando teoricamente e validando experimentalmente que, embora o Método das Partes Iguais (MES) ofereça garantias axiomáticas mais fortes, ele e a Regra Sequencial de Phragmen apresentam o mesmo grau de proporcionalidade quantitativa.

O essencial

Imagine que você e seus vizinhos têm uma grande caixa de dinheiro (o orçamento) para gastar em melhorias para o bairro: um novo parque, um playground, uma praça com bancos ou uma biblioteca. O desafio é: como dividir esse dinheiro de forma justa?

Se o grupo de pessoas que quer o parque é muito grande, eles merecem mais dinheiro do que um grupo pequeno que quer apenas uma fonte de água. Mas como garantir matematicamente que o grupo grande realmente recebe sua "fatia justa" do bolo, mesmo que o dinheiro seja limitado?

Este artigo de pesquisa é como um teste de justiça para dois métodos populares usados para tomar essa decisão: o Método das Partes Iguais (Equal Shares) e a Regra Sequencial de Phragmén.

Aqui está a explicação simplificada, usando analogias do dia a dia:

1. O Problema: A "Fome" de Representação

Na democracia, queremos que grupos grandes de pessoas (digamos, 30% da população) consigam financiar projetos que representem 30% do orçamento.

• A Teoria Antiga: Os cientistas já sabiam que certas regras eram "justas" ou "injustas" de forma binária (sim ou não). Era como dizer: "Esta regra é um bom juiz" ou "Esta regra é um mau juiz".
• A Nova Medida (Grau de Proporcionalidade): Os autores deste artigo criaram uma régua mais precisa. Em vez de apenas dizer "é justo", eles medem quanto de justiça existe. É como medir não apenas se o bolo foi dividido, mas se cada pessoa recebeu a fatia exata que deveria, considerando o tamanho do grupo.

2. Os Dois Concorrentes

Os pesquisadores compararam dois "juízes" famosos:

• O Método das Partes Iguais (Equal Shares - MES):

  • A Analogia: Imagine que cada pessoa recebe um cartão de crédito virtual com a mesma quantia de dinheiro. Quando um projeto é escolhido, os apoiadores pagam por ele usando seus cartões. Se o dinheiro de um grupo acabar, eles param de votar.
  • Reputação: É considerado o "campeão" teórico porque segue regras muito rígidas de justiça (chamadas EJR). Acreditava-se que ele era o melhor de todos.

• A Regra Sequencial de Phragmén:

  • A Analogia: Imagine que o dinheiro não é dado de uma vez, mas cai como uma chuva constante. As pessoas "enchem seus balões" de dinheiro ao longo do tempo. Assim que um grupo de pessoas tem água suficiente para encher o balão de um projeto, o projeto é escolhido e os balões deles são esvaziados.
  • Reputação: É um pouco mais "relaxado" nas regras teóricas (não segue a regra rígida EJR), então muitos achavam que ele seria menos justo.

3. A Grande Surpresa: A Corrida Acabou Empate!

O resultado mais chocante do artigo é que, na prática e na matemática pesada, os dois métodos são praticamente idênticos em justiça.

• A Descoberta: Mesmo que o "Método das Partes Iguais" tenha regras mais estritas no papel, quando você coloca a régua de medição (o grau de proporcionalidade) neles, eles entregam a mesma quantidade de justiça.
• A Metáfora: É como se dois corredores tivessem estilos de corrida diferentes. Um corre com uma técnica perfeita e rígida, o outro com uma técnica mais solta. Mas, ao cruzar a linha de chegada, ambos levam a mesma medalha de ouro. O artigo prova que, matematicamente, nenhum deles consegue garantir mais justiça do que o outro.

4. O Vilão: A Regra "Gananciosa" (Greedy)

O estudo também comparou esses dois com o método mais simples usado na vida real: a Regra Gananciosa.

• A Analogia: É como escolher os projetos apenas olhando para quem tem mais votos, sem se importar com grupos menores. É como pegar os maiores pedaços de bolo primeiro, deixando os grupos pequenos com migalhas.
• O Resultado: Tanto o "Método das Partes Iguais" quanto o "Phragmén" são muito superiores à regra gananciosa. A regra gananciosa é injusta para grupos coesos (grupos que querem a mesma coisa).

5. O Experimento Real

Os pesquisadores não ficaram apenas na teoria. Eles pegaram dados reais de 100 eleições de orçamento participativo do mundo real (de cidades e escolas) e rodaram os dois métodos neles.

• O Que Aconteceu: Os resultados reais espelharam a teoria. Os dois métodos funcionaram muito bem e de forma muito similar. Às vezes, um era ligeiramente melhor que o outro, mas a diferença era mínima. Ambos destruíram a regra gananciosa em termos de justiça.

Conclusão: O Que Isso Significa para Você?

Se você é um cidadão participando de um orçamento público:

1. Não se preocupe tanto com qual método usar: Se a cidade usar o "Método das Partes Iguais" ou o "Phragmén", você pode ficar tranquilo. Ambos são excelentes e garantem que grupos grandes recebam sua parte justa do dinheiro.
2. Fuja do método simples: Evite métodos que apenas contam votos um por um (o método ganancioso), pois eles tendem a ignorar grupos menores que têm opiniões em comum.

Resumo em uma frase:
Este artigo prova matematicamente e com dados reais que duas das melhores regras de divisão de dinheiro público são, na verdade, "gêmeas" em termos de justiça, garantindo que grupos de pessoas recebam o que merecem, muito melhor do que os métodos simples que usamos hoje.

Resumo técnico

Resumo Técnico: Grau de Proporcionalidade em Orçamento Participativo

1. Problema e Contexto

O Orçamento Participativo (PB) é um processo democrático onde cidadãos influenciam diretamente a alocação de fundos públicos. Embora existam muitas regras computacionais para PB, a maioria das análises anteriores focou em garantias axiomáticas binárias (uma regra satisfaz ou não um axioma, como a Representação Justificada Estendida - EJR).

O artigo aborda uma lacuna na literatura: a falta de uma medida quantitativa de quão bem uma regra de PB alcança a representação proporcional. O conceito central é o Grau de Proporcionalidade (Proportionality Degree), que quantifica o limite inferior do grau de satisfação média que um grupo coeso de eleitores (que apoia unanimemente um conjunto de projetos) pode garantir, em relação ao tamanho do grupo e ao custo dos projetos.

O objetivo do trabalho é analisar teoricamente e experimentalmente o grau de proporcionalidade de duas das regras mais populares e justas no PB:

1. Método das Partes Iguais (Method of Equal Shares - MES): Conhecido por satisfazer axiomas fortes como EJR.
2. Regra Sequencial de Phragm´en: Satisfaz axiomas mais fracos (como PJR), mas não EJR.

2. Metodologia

2.1. Definições Fundamentais

• Instância de PB: Um conjunto de eleitores $N$, projetos $T$, orçamento $B$, custos $C$ e perfis de aprovação $A$.
• Grupo $T$-Coeso: Um grupo de eleitores $V$ que aprova unanimemente um conjunto de projetos $T$, tal que a fração do orçamento necessária para $T$ é proporcional ao tamanho do grupo ($cost(T)/B \le |V|/n$).
• Grau de Proporcionalidade ($d_f(T)$): O maior limite inferior garantido para a satisfação média de qualquer grupo $T$-coeso sob uma regra $f$.

2.2. Abordagem Teórica

Os autores derivam limites inferiores e superiores (tight bounds) para o grau de proporcionalidade de MES e Phragm´en.

• Lema 1 e Teorema 1 (MES): Utilizam uma construção de ordenação de pagamentos para provar que o MES garante um grau de proporcionalidade de pelo menos $\frac{1}{2} \left( \frac{cost(T)}{\max cost(t)} - 1 \right)$.
• Teorema 2 (Limite Superior para MES): Constroem uma instância adversária onde a satisfação média é limitada superiormente por $\approx \frac{1}{2} \frac{cost(T)}{\max cost(t)} + 1$.
• Teorema 3 (Generalização): Estendem o limite inferior para qualquer regra que satisfaça EJR em instâncias "ordinárias" (onde nenhum projeto é excessivamente barato).
• Teorema 4 e 5 (Phragm´en): Utilizam argumentos de função potencial (similar a trabalhos em votação multi-vencedora) para provar que a Regra Sequencial de Phragm´en atinge o mesmo limite inferior e superior que o MES, apesar de não satisfazer EJR.

2.3. Abordagem Experimental

• Dados: 100 instâncias reais do conjunto de dados Pabulib.
• Regras Testadas: MES, Phragm´en Sequencial, MES com exaustão (exhaustion), Phragm´en com exaustão e uma regra greedy (seleção baseada na pontuação de aprovação).
• Método: Como calcular o grau para todos os subconjuntos é exponencial, os autores utilizam amostragem aleatória de subconjuntos de tamanhos variados ($k=1$ a $15$) para estimar o grau médio de proporcionalidade.

3. Principais Contribuições e Resultados

3.1. Resultados Teóricos

• Equivalência Quantitativa: A descoberta mais surpreendente é que, embora o MES satisfaça axiomas mais fortes (EJR) e o Phragm´en não, ambas as regras possuem o mesmo grau de proporcionalidade (dentro de fatores constantes pequenos).
  • Limite Inferior: $d(T) \ge \frac{1}{2} \left( \frac{cost(T)}{\max cost(t)} - 1 \right)$.
  • Limite Superior: $d(T) \le \frac{1}{2} \frac{cost(T)}{\max cost(t)} + 1$.
• Implicação Estrutural: Isso sugere uma similaridade estrutural profunda entre as duas regras no que tange à garantia quantitativa de representação, desafiando a intuição de que axiomas mais fortes implicam necessariamente em melhores garantias quantitativas de proporcionalidade.
• Conjectura de Optimalidade: Os autores conjecturam que essas regras são ótimas para o problema, pois o limite superior de qualquer regra é limitado por $\frac{cost(T)}{\max cost(t)} - 1$.

3.2. Resultados Experimentais

• Desempenho Prático: Os experimentos confirmam a teoria. Tanto MES quanto Phragm´en (com e sem exaustão) apresentam desempenho muito superior à regra greedy em termos de grau de proporcionalidade.
• Comparação MES vs. Phragm´en:
  • Na prática, as versões com "exaustão" (que usam a regra greedy para gastar o orçamento restante) performam de forma comparável.
  • Curiosamente, o Phragm´en (mesmo sem exaustão) muitas vezes supera ligeiramente o MES em alguns conjuntos de dados reais.
  • A regra greedy é consistentemente a pior, falhando em garantir representatividade para grupos coesos menores.

4. Significado e Conclusão

O trabalho estabelece o Grau de Proporcionalidade como uma métrica fundamental para avaliar regras de Orçamento Participativo, indo além das verificações binárias de axiomas.

• Validação de Práticas: Os resultados fornecem suporte empírico e teórico para o uso de MES e Phragm´en em implementações reais de PB, em detrimento de métodos simples baseados em aprovação acumulada (greedy).
• Insight Teórico: A descoberta de que regras com garantias axiomáticas distintas (EJR vs. PJR) podem ter o mesmo desempenho quantitativo de proporcionalidade abre novas direções para a pesquisa em teoria da escolha social, sugerindo que a estrutura de "mercado" subjacente a ambas as regras é o fator determinante para a proporcionalidade, e não apenas a satisfação de axiomas específicos.
• Futuro: O artigo propõe que provar a optimalidade exata dessas regras (fechando a pequena lacuna entre os limites inferior e superior) é um desafio técnico interessante para trabalhos futuros.

Em suma, o paper demonstra que, tanto na teoria quanto na prática, o Método das Partes Iguais e a Regra de Phragm´en oferecem garantias robustas e equivalentes de proporcionalidade, superando significativamente abordagens heurísticas comuns.