🔢 mathematics

Counting Votes with Multisets

Este artigo demonstra como as propriedades categóricas dos multiconjuntos — especificamente sua estrutura como um monoide comutativo livre, funtor e monada — podem ser aplicadas de forma eficaz para derivar e expressar resultados em vários sistemas de votação, incluindo o de segundo turno (instant-runoff), De Borda e o voto único transferível.

Autores originais: Bart Jacobs, Michael Johnson, Richard Buckland

Publicado 2026-06-05

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Bart Jacobs, Michael Johnson, Richard Buckland

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está conduzindo uma votação, mas em vez de contar cédulas de papel uma por uma, você está gerenciando um saco gigante de bolinhas coloridas. Esta é a ideia central do artigo: Multisets (Multiconjuntos).

Aqui está uma explicação simples do que os autores, Bart Jacobs, Michael Johnson e Richard Buckland, estão propondo, usando analogias do cotidiano.

1. O Saco Mágico (O que é um Multiset?)

Normalmente, na matemática, um "conjunto" é como uma lista de itens únicos. Se você tem um conjunto de frutas, pode ter uma maçã e uma banana, mas não pode ter "duas maçãs" na definição do conjunto; é apenas "maçãs".

Um Multiset é como um saco de bolinhas.

Se você colocar 4 bolinhas vermelhas, 3 azuis e 2 verdes em um saco, a ordem não importa.
O que importa é a contagem.
Os autores escrevem isso como: 4|R⟩ + 3|B⟩ + 2|G⟩.
Em uma eleição, este saco representa os votos. Não importa quem votou ou quando votou; o que importa é que existem 4 votos para Vermelho, 3 para Azul e 2 para Verde.

Por que isso é bom?
Se você mantiver os votos em uma lista (como uma planilha), a ordem da lista pode acidentalmente revelar quem votou em quem. Mas se você apenas despejar tudo em um "saco de multiset", a ordem desaparece. Você obtém uma contagem limpa e anônima que é impossível de rastrear até os indivíduos.

2. Os Três Jogos de Votação

O artigo mostra como essa abordagem de "saco de bolinhas" torna três sistemas de votação complexos muito mais fáceis de entender e calcular. Eles usam alguns termos matemáticos sofisticados (como "funtores" e "mônadas"), mas pense neles como regras para mover as bolinhas ao redor.

Jogo A: Votação com Execução Instantânea (O Jogo da "Eliminação")

Como funciona: Os eleitores classificam os candidatos (1º lugar, 2º lugar, 3º lugar). Se ninguém obtiver 50% dos votos, a pessoa com menos votos é eliminada. Os votos dela são então atribuídos à segunda escolha dos eleitores.
O Truque do Multiset: Imagine que seu saco de cédulas é uma pilha de listas.
1. Você olha para o topo de cada lista (1ª escolha) e conta as bolinhas.
2. Você encontra o perdedor (Candidato C).
3. Você usa uma "borracha mágica" (chamada de functor no artigo) para deletar o Candidato C de todas as listas no saco.
4. Agora, as 2ª escolhas tornam-se as novas 1ª escolhas. Você conta o saco novamente.
5. Você repete isso até que alguém tenha a maioria.
O Benefício: Em vez de riscar nomes manualmente em milhares de papéis, você apenas aplica a regra de "deletar" para todo o saco de uma só vez.

Jogo B: Contagem de De Borda (O Jogo dos "Pontos Ponderados")

Como funciona: Os eleitores classificam os candidatos. A 1ª escolha recebe 4 pontos, a 2ª recebe 3 pontos, a 3ª recebe 2 pontos, etc. Todos os pontos são somados.
O Truque do Multiset:
1. Em vez de apenas contar votos, você transforma cada cédula individual em um mini-saco de bolinhas ponderadas. Uma cédula dizendo "A, B, C, D" torna-se 4|A⟩ + 3|B⟩ + 2|C⟩ + 1|D⟩.
2. Você despeja todos esses mini-sacos em um único super-saco gigante.
3. Você usa uma ferramenta de "achatamento" (chamada de monad) para esmagar todas as camadas.
4. O resultado é uma contagem única de pontos totais para cada candidato.
O Benefício: Transforma um problema matemático complexo em uma operação simples de "somar tudo".

Jogo C: Voto Único Transferível (O Jogo do "Compartilhamento de Excedente")

Como funciona: Isso é usado para eleger várias pessoas (como um conselho municipal). Existe uma "quota" (um número mínimo de votos necessários para vencer). Se um candidato obtiver muito mais votos do que o necessário, os votos extras não devem ser desperdiçados; eles devem ser transferidos para a próxima escolha dos eleitores.
O Truque do Multiset:
1. Imagine que um candidato vença com 93 votos, mas a quota é de apenas 63. Ele tem 30 votos de "excedente".
2. Em vez de escolher 30 papéis aleatórios para transferir (o que seria injusto), os autores sugerem um truque matemático: Desvalorizar os votos.
3. Você pega todos os 93 votos para esse vencedor e os reduz por uma fração específica (como encolher uma foto).
4. Você então "deleta" o vencedor das listas e transfere esses votos "encolhidos" para os próximos candidatos.
5. Isso permite que a matemática lide com frações de votos perfeitamente, garantindo que nenhum voto seja desperdiçado ou contado duas vezes.

3. Por que isso importa?

Os autores não estão tentando inventar um novo tipo de matemática; eles estão mostrando que a matemática antiga (Teoria das Categorias) é a ferramenta perfeita para a votação moderna.

Transparência: Como os multisets ignoram a ordem dos votos, o processo de contagem é matematicamente garantido como anônimo.
Simplicidade: Regras complexas (como deletar perdedores ou dividir o excedente de votos) tornam-se operações simples em um saco de bolinhas.
Corretude: Se você escrever um programa de computador para contar votos usando essas regras de "saco", é muito mais difícil cometer um erro do que se tentar organizar pilhas de papel.

Em resumo: O artigo argumenta que, se pararmos de pensar nos votos como uma pilha bagunçada de papel e começarmos a pensar neles como um saco de bolinhas coloridas, podemos usar regras matemáticas simples e poderosas para contá-los de forma justa, rápida e sem erros.

Resumo Técnico: Contagem de Votos com Multiconjuntos

Enunciado do Problema
O artigo aborda o desafio de descrever, explicar e implementar algoritmos de contagem de votos para sistemas eleitorais complexos, particularmente aqueles que envolvem votação preferencial (preferendums) e múltiplas opções ponderadas. Enquanto eleições simples (ex: dois candidatos, voto único) podem ser descritas via listas ou contagens simples, mecanismos como o Voto de Segundo Turno Instantâneo (IRV - Instant-Runoff Voting), as contagens de De Borda e o Voto Único Transferível (STV) envolvem a transferência de excedentes de votos, a eliminação de candidatos e o reponderamento de preferências. Os autores argumentam que tipos de dados padrão, como listas, são subótimos para essas tarefas porque retêm a ordem (o que é irrelevante para o resultado) e podem vazar informações relativas à sequência de votação, potencialmente comprometendo a confidencialidade. Além disso, implementar esses algoritmos com listas frequentemente leva a códigos complexos e ad-hoc, que são difíceis de verificar quanto à correção e transparência.

Metodologia
O artigo propõe modelar os resultados eleitorais e os processos de contagem de votos usando multiconjuntos (conjuntos onde os elementos podem ocorrer múltiplas vezes) em vez de listas. Os autores empregam técnicas elementares de teoria das categorias para formalizar as operações nesses multiconjuntos. A metodologia central envolve:

Seleção de Tipo de Dado: Representar uma coleção de votos como um multiconjunto $N(X)$ (ou $M(X)$ para votos fracionários), onde os elementos são candidatos e as multiplicidades são contagens de votos. Isso abstrai a ordem dos votos.
Estruturas Categóricas: Os autores utilizam três propriedades categóricas específicas de multiconjuntos para derivar e expressar algoritmos de votação:
- Monoide Comutativo: Multiconjuntos formam um monoide comutativo livre, permitindo a adição de contagens de votos (união de urnas) onde a ordem é irrelevante.
- Functorialidade: A construção de multiconjunto $N$ atua como um funtor. Isso permite que funções definidas sobre candidatos (ex: "cabeça da lista" ou "deletar candidato") sejam elevadas para funções sobre multiconjuntos de listas. Esta propriedade é usada para agregar preferências primárias e para redistribuir votos quando um candidato é eliminado.
- Estrutura de Mônada: Multiconjuntos formam uma mônada com unit (criando um multiconjunto de elemento único) e flatten (colapsando um multiconjunto de multiconjuntos). Esta estrutura é usada para lidar com contagens ponderadas, onde um único voto (uma lista de preferências) é decomposto em contribuições ponderadas para múltiplos candidatos.

Contribuições Principais e Resultados
O artigo demonstra a aplicação dessas estruturas categóricas através de três mecanismos de votação específicos, utilizando exemplos de pequena escala (verificados via scripts Python da biblioteca EfProb) para ilustrar a abstração:

Voto de Segundo Turno Instantâneo (IRV):
- Mecanismo: Candidatos com o menor número de votos de primeira preferência são eliminados iterativamente, e seus votos são transferidos para a próxima preferência.
- Aplicação: Os autores utilizam a functorialidade dos multiconjuntos. A função head (selecionar a primeira preferência) e a função delete (remover um candidato eliminado) são elevadas para operar sobre o multiconjunto de listas de preferências. Isso permite que a agregação de primeiras preferências e a subsequente redistribuição de votos sejam expressas como composições funcionais simples ( $N(\text{hd})$ e $N(\text{del } c)$ ), evitando o processamento iterativo complexo de listas.
Contagem de De Borda:
- Mecanismo: Eleitores classificam os candidatos, e pontos são atribuídos com base na classificação (ex: 1º lugar recebe $n$ pontos, 2º recebe $n-1$ , etc.).
- Aplicação: A estrutura de mônada é utilizada. Cada lista de preferências é mapeada para um multiconjunto de candidatos ponderados (via unit e atribuição de pontos). A coleção de todos esses multiconjuntos ponderados forma um multiconjunto de multiconjuntos. A operação flatten então colapsa essa estrutura em um único multiconjunto de pontuações totais, somando eficientamente as contribuições ponderadas.
Voto Único Transferível (STV):
- Mecanismo: Utilizado para circunscrições de múltiplos membros. Candidatos que excedem uma quota (quota de Droop) são eleitos, e seu excedente de votos é transferido para a próxima preferência.
- Aplicação: Os autores estendem o tipo de dado para multiconjuntos fracionários ( $M(X)$ ) para lidar com o "valor de transferência" (uma fração de um voto). Eles utilizam a estrutura de monoide para subtração (desvalorização de votos usados para eleger um candidato) e a functorialidade para redistribuição. O processo é modelado como uma subtração iterativa dos votos ponderados pela quota do candidato eleito do multiconjunto total, seguida pela remoção do candidato eleito e pela transferência dos pesos fracionários restantes para a próxima preferência.

Significância e Alegações
O artigo alega modestamente que sua principal contribuição não é uma teoria das categorias profunda, mas o reconhecimento e exploração de estruturas categóricas existentes (funtores, mônadas, monoides) dentro do domínio dos sistemas de votação. Os autores argumentam que:

Abstração: Descrever esses algoritmos em termos de multiconjuntos os torna "abstratos", permitindo que mecanismos complexos sejam descritos em poucas linhas de notação matemática.
Correção e Transparência: A abordagem de multiconjuntos garante inerentemente a estabilidade sob a permutação de votos (independência de ordem), um requisito fundamental para uma contagem justa. Ela separa a lógica de contagem da representação física ou sequencial das cédulas.
Implementação: A abstração facilita a criação de implementações comprovadamente corretas em linguagens de programação funcional (ex: Haskell) que suportam multiconjuntos.
Acessibilidade: O artigo visa tornar essas técnicas categóricas acessíveis a não especialistas, demonstrando que são ferramentas práticas para garantir a transparência e a precisão nos resultados eleitorais, em vez de construções puramente teóricas.

O artigo conclui que, embora simplificações tenham sido feitas (ex: comprimentos de lista uniformes), a abordagem de multiconjuntos oferece um arcabouço robusto para futuras implementações de referência e para a análise de algoritmos eleitorais, indo além da dependência histórica de ordenação de cédulas físicas.