Um exercício matemático e computacional sobre os métodos usados para alocar vagas nas eleições proporcionais do Brasil. Estava refletindo sobre isso uns dias atrás e estou colocando aqui para sistematizar, compartilhar e saber o que outras pessoas acham. A epígrafe é: O quociente eleitoral está morto; vida longa à menor sobra!

O Código Eleitoral brasileiro determina a forma como são eleitos os candidatos a cargos proporcionais (deputados e vereadores) no seu capítulo IV. O método consiste, em resumo, em:

1. Calcular o quociente eleitoral $q$, definido como a soma do total de votos válidos (isso é, sem contar abstenções, brancos e nulos) $t$ dividida pela quantidade de vagas a preencher $s$, arredondada para o número inteiro mais próximo. Isso é, $q := \left[\frac{t}{s}\right]$.
2. Para cada partido ou coligação $i$, calcular o quociente partidário $p_i$, definido como o número de votos obtidos pelo partido ou coligação $v_i$ dividido (divisão inteira, ou seja, desprezada a fração) pelo quociente eleitoral $q$. Isso é, $p_i := \left\lfloor \frac{v_i}{q} \right\rfloor \forall i$. Então, $p_i$ é a quantidade inicial de vagas atribuídas ao partido ou coligação $i$.
3. Dividir as $s - \sum_{i} p_i$ vagas restantes de acordo com o Cálculo das Sobras, também conhecido como Cálculo das Médias. Tal método é definido pela repetição do seguinte processo enquanto houver vagas restantes (copiado da lei): “o número de votos válidos atribuídos a cada partido político ou coligação será dividido pelo número de lugares por eles obtidos mediante o cálculo do quociente partidário mais um, cabendo ao partido político ou à coligação que apresentar a maior média um dos lugares a preencher, desde que tenha candidato que atenda à exigência de votação nominal mínima”.

Para além desse algoritmo, vale fazer duas considerações importantes sobre o método que vão reaparecer em outros momentos deste texto:

1. Até a eleição de 2016, os partidos ou coligações $i$ que não tivessem quociente partidário $p_i \geq 1$ não participavam do Cálculo das Sobras. Tal restrição foi removida na reforma eleitoral de 2017.
2. A partir da eleição de 2016, foi imposta uma cláusula de barreira (aprovada em 2015) que exige que candidatos tenham 10% do quociente partidário para poderem ser eleitos (a não ser no caso em que não há candidatos nessa condição). Esse fato vai ser desprezado nesse artigo. Ou seja, vamos assumir que todos os partidos ou coligações que tiverem uma vaga de acordo com o método têm também candidatos aptos a serem eleitos.

A implementação do método descrito acima em C++ (escolhi essa linguagem para usar a fila de prioridades da STL) seria como segue:

// Estrutura usada para ordenar partidos de acordo com suas sobras.
struct party {
  int index, votes, seats;
  bool operator < (const party &o) const {
    return votes / (double) (seats + 1) < o.votes / (double) (o.seats + 1);
  }
};

vector <int> codigoEleitoral(vector <int> v, int s) {
  // Pré-calculo de t, o número total de votos válidos.
  int t = 0;
  for (int i = 0; i < v.size(); i++) {
    t += v[i];
  }

  // Passo 1: calcular o quociente eleitoral.
  int q = round(t / (double) s);

  // Passo 2: calcular o quociente partidário e alocar primeiras vagas.
  priority_queue <party> Q;
  for (int i = 0; i < v.size(); i++) {
    s -= (int) (v[i] / q);
    Q.push((party) {i, v[i], v[i] / q});
  }

  // Passo 3: Cálculo das Sobras ou Médias.
  while (s--) {
    party p = Q.top();
    Q.pop();
    p.seats++;
    Q.push(p);
  }

  // Reconstrução do resultado.
  vector <int> result(Q.size(), 0);
  while (!Q.empty()) {
    party p = Q.top();
    result[p.index] = p.seats;
    Q.pop();
  }

  return result;
}

Sua complexidade é $\Theta((n+s) \log n)$, onde $n$ é o número de partidos ou coligações. O logaritmo vem do uso da heap implementada pela STL (priority_queue).

A partir dessas definições e desse método, gostaria de compartilhar alguns pensamentos.

Equivalência com D’Hondt

Primeiramente, é bom observar que o Método D’Hondt é exatamente o que é chamado de Cálculo das Médias no Código Eleitoral. Como descreve a Wikipedia:

O método [D’Hondt] consiste numa fórmula matemática, ou algoritmo, destinada a calcular a distribuição dos mandatos pelas listas concorrentes, em que cada mandato é sucessivamente alocado à lista cujo número total de votos dividido pelos números inteiros sucessivos, começando na unidade (isto é no número 1) seja maior. O processo de divisão prossegue até se esgotarem todos os mandatos e todas as possibilidades de aparecerem quocientes iguais aos quais ainda caiba um mandato.

A tabela abaixo, da distribuição de 8 vagas para 4 partidos, ajuda a visualizá-lo:

Mais interessante do que perceber que o Cálculo das Médias do Código Eleitoral é o Método D’Hondt, porém, é observar que o método completo brasileiro (não apenas o cálculo das médias) é equivalente matematicamente ao Método D’Hondt, isso é, os dois métodos distribuem as vagas da mesma forma.

Creio que a forma mais fácil de provar isso consista em demonstrar que um partido ou coligação tem uma vaga pelo Código Eleitoral se e somente se tem tal vaga pelo Método D’Hondt. Talvez mostrar que o D’Hondt e o Código Eleitoral decidem as $\sum_i p_i$ primeiras vagas da mesma forma? Será que não bastaria provar que o quociente eleitoral é maior ou igual ao menor número negrito na tabela do D’Hondt (conceito que chamaremos de menor sobra e definiremos melhor até o final desse artigo)? Intuitivamente isso parece não ser muito difícil, mas na prática não fiz e vou considerar que essa prova maravilhosa não cabe nas margens desse artigo.

O importante é que, aceitando esse fato, nota-se que o Código Eleitoral poderia ser simplificado deixando de lado o cálculo do quociente eleitoral e do quociente partidário, aplicando apenas o Cálculo das Sobras/Médias (ou Método D’Hondt) desde o princípio. Sua implementação poderia ser, assim, reduzida para:

vector <int> dhondt(vector <int> v, int s) {
  priority_queue <party> Q;
  for (int i = 0; i < v.size(); i++) {
    Q.push((party) {i, v[i], 0});
  }

  // Cálculo das Sobras ou Médias (D'Hondt).
  while (s--) {
    party p = Q.top();
    Q.pop();
    p.seats++;
    Q.push(p);
  }

  // Reconstrução do resultado.
  vector <int> result(Q.size(), 0);
  while (!Q.empty()) {
    party p = Q.top();
    result[p.index] = p.seats;
    Q.pop();
  }

  return result;
}

A complexidade computacional claramente seria a mesma, mas reduzir o esforço mental para entender o cálculo e também o código — evitando calcular os arredondamentos de quociente eleitoral e quociente partidário — parece bom.

A verdade é que isso nos motiva a perceber que a única utilidade do quociente eleitoral $q$ tem a ver com as duas considerações que fiz acima e informei que iriam aparecer em outros momentos do texto. De fato, em 2018, a única utilidade do quociente eleitoral será barrar candidatos que não tenham 10% desse quociente.

Já o quociente partidário $p_i$ teria importância se ainda houvesse a necessidade dos partidos ou coligações $i$ terem $p_i \geq 1$ para participar do Cálculo das Médias. Sem tal mecanismo, já não serve para nada.

A menor sobra é o xis da questão

O quociente eleitoral tinha importância porque era nele que se devia mirar para eleger o primeiro candidato de um partido ou coligação. Com a mudança no Código Eleitoral, o número fundamental da eleição deixa de ser o quociente eleitoral e passa a ser a menor sobra $x$, que defino como o menor número na tabela do Método D’Hondt que garante vaga.

Matematicamente, $x := \min_i \frac{v_i}{r_i}$, onde $v_i$ é a quantidade de votos do partido ou coligação $i$ e $r_i$ é o número de vagas alocadas ao partido ou coligação $i$ no final do processo.

A menor sobra não é importante apenas para que se saiba quantos votos são necessários para eleger o primeiro candidato de um partido ou coligação (como antes era o quociente eleitoral), mas para saber quantos candidatos cada partido ou coligação vai eleger. Com efeito, é fácil ver que o número de candidatos a serem eleitos por um partido ou coligação é $\left\lfloor\frac{v_i}{x}\right\rfloor$. Isso a torna especialmente interessante, muito mais útil do que o velho quociente.

Refletir sobre a importância da menor sobra sugere um algoritmo que evita a implementação do D’Hondt e da fila de prioridades: uma simples busca binária para encontrar $x$, dado que quanto menor [maior] é $x$ mais [menos] candidatos são eleitos.

vector <int> menorSobra(vector <int> v, int s) {
  int a = 0, b = 0;

  // Encontrando o limite superior para a busca binária.
  for (int i = 0; i < v.size(); i++) {
    b = max(b, v[i] + 1);
  }

  // Busca binária para encontrar x.
  while ((b - a) > 1) {
    int x = (a + b) / 2, y = 0;
    for (int i = 0; i < v.size(); i++) {
      y += v[i] / x;
    }
    if (y < s) {
      b = x;
    } else {
      a = x;
    }
  }

  // Construção do resultado dividindo votos de cada partido por x.
  vector <int> result(v.size(), 0);
  int x = (a + b) / 2;
  for (int i = 0; i < v.size(); i++) {
    result[i] = v[i] / x;
  }

  return result;
}

Esse algoritmo tem complexidade $\Theta(n \log t)$, que me parece razoável.

Por tudo isso, exceto se a sua preocupação for com a cláusula de barreira de 2015 — isso é, com fazer seu candidato atingir 10% do quociente eleitoral —, pareceria que vale esquecer o quociente eleitoral e o algoritmo do TSE, dando centralidade à menor sobra.

Do ponto de vista prático, como, porém, estimar a menor sobra antes de ter os dados de uma eleição (que ainda não tenha acontecido, por exemplo)?

Bem, sabemos que ela é limitada superiormente pelo quociente eleitoral ($x \leq q$), que é fácil de estimar já que se conhece o tamanho do colégio eleitoral, o número de vagas a serem preenchidas e dá pra chutar uma proporção de votos válidos. Ao menos, é bem mais fácil do que estimar a configuração completa do resultado de uma eleição. Então, só por isso, talvez valha, ainda, não descartar o quociente eleitoral.

Imagine-se num prédio de 100 andares com várias bolas. A partir de um determinado andar (desconhecido), quando você joga uma bola pela janela, a bola quebra. Você quer determinar precisamente qual é esse andar e a única coisa que pode fazer é jogar bolas de andares diferentes.

Se você tem muitas bolas e não se importa em quebrar quantas forem necessárias, você pode realizar uma busca binária. Uma busca binária, para começar com um exemplo, é aquilo que você faz naquele diálogo clássico:

— Pense num número de 1 a 100 e eu vou tentar adivinhar. A cada palpite, você precisa me dizer se o número que você pensou é maior ou menor do que meu chute.
— Pensei.
— 50
— Maior.
— 75
— Menor.
— 63
— Menor.
— 57
— Menor.
— 54
— Menor.
— 52
— Menor.
— 51
— Acertou!

A cada passo numa busca binária você divide o intervalo de possibilidades por dois. Você descarta metade dos números que poderiam ser a solução. Por isso, mesmo que você pense num número de 1 a 1.000.000.000 (um bilhão) eu certamente não vou demorar mais de 30 (isso é, logaritmo de um bilhão na base dois) tentativas para acertar exatamente o número que você pensou.

Por que logaritmo de um bilhão na base dois? Como eu comentei anteriormente, a cada número que eu chuto e você diz se é maior ou menor do que o resultado eu corto meu intervalo por dois. Portanto, o número de chutes necessários (no pior caso) é precisamente a quantidade de vezes que preciso dividir um bilhão por dois até chegar a um (até sobrar um único número possível para eu chutar, que necessariamente vai ser o número que você pensou).

Nosso problema é encontrar quantos 2 tem aí. Dividir um número por 2 k vezes é o mesmo que dividir por $2^k$. Logo, nosso problema é encontrar quanto vale k:

Multiplicando os dois lados da igualdade por $2^k$, temos:

Tirando o logaritmo na base 2, concluímos:

Ou seja, o logaritmo de n na base 2 é o número de vezes que precisamos dividir n por 2 para chegar em 1. Voltando ao problema inicial, como $log_2 100 < 7$, precisaremos jogar no máximo 7 bolas para determinar a partir de qual andar a bola quebrar. Quando você jogar uma bola, se ela quebrar é a mesma coisa que o seu amigo que pensou num número dizendo “O número que eu pensei é menor.” Se ela não quebrar, é equivalente ao seu amigo dizendo “O número que eu pensei é maior.”

Realizando uma busca binária, o pior caso (aquele caso no qual quebraremos mais bolas – e que jogaremos a maior quantidade de vezes) é quando a bola quebra no primeiro andar. Você joga as bolas dos andares 50 (poft!), 25 (poft!), 13 (poft!), 7 (poft!), 4 (poft!), 2 (poft!), 1, jogando um total de 7 e quebrando um total de 6 bolas.

Nada muito novo para quem já conhecia busca binária. Por isso, vamos modificar o problema: Suponha que você não tenha quantas bolas desejar, mas apenas duas bolas. Quando uma bola cai sem quebrar, você pode descer, pegá-la e jogá-la de novo. Qual a menor quantidade de vezes que você vai ter que jogar a bola para com certeza determinar a partir de qual andar as bolas começam a quebrar?

Fazer uma busca binária não funciona mais. No caso de a bola quebrar a partir do primeiro andar, assim que você joga uma bola do andar 50 (uma bola quebra) e outra do 25 (outra bola quebra), você não tem mais bolas e não tem ideia de qual é o andar a partir do qual as bolas começam a quebrar (tudo o que você sabe é que é algum andar entre 1 e 25).

Como usar as duas bolas para determinar exatamente o andar a partir do qual as bolas começam a quebrar jogando as bolas a menor quantidade possível de vezes? Qual é essa quantidade mínima de vezes que será necessário jogar bolas pela janela?

Obrigado ao David por ter me apresentado o problema. A solução é bem legal!

Editado para ficar mais claro: A quantidade mínima que queremos é a do pior caso, isso é, a menor quantidade de vezes que será necessário jogar a bola independente de qual for o andar. Por exemplo, suponha que eu jogue uma bola do andar 5 e não quebre. Aí eu jogue do andar 10 e não quebre. Do 15 e não quebre. E assim sucessivamente (de 5 em 5) enquanto ela não quebrar. Quando ela quebrar, eu pego a outra bola e jogo no último valor que eu joguei menos 4, menos 3, menos 2 e menos 1. O pior caso para esse algoritmo é quando a bola quebrar a partir do andar 99. Jogarei nos andares 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100 (poft!), 96, 97, 98, 99 (poft!), ou seja, 24 vezes. (Mas é possível usar um algoritmo mais esperto que isso: a resposta do problema é menor que 24.)

Editado para programadores: A generalização deste problema (para n andares em vez de 100 e k bolas em vez de 2) caiu na OBI 2010 (o problema se chama Altas Aventuras) e está no SPOJ para quem quiser resolver: ALTAS2. Quem me contou foi o André.