Models for Iterative Multi-winner Approval Voting

Abstract

[EN] In this thesis we study the multi-winner voting rules known as Proportional Approval Voting and Phragm´en’s Voting Rule; as well as their sequential variants. Here voters submit their preferences through approval ballots. These voting rules are applied to an iterative framework, meaning that once the initial vote is submitted voters may deviate from their vote given the current state of the game. The framework for this voting system is defined. We describe heuristics to model the behavior that voters can take, when voting strategically, i.e. how voters can deviate from their initial true preferences to obtain a better outcome. Furthermore, we describe examples of games in which each heuristic introduced causes a change in utility. We also apply the considered heuristics to the sequential variants of the voting rules introduced in this thesis. Additionally, we study whether the different heuristics guarantee (or not) reaching a stable solution. For this reason, we introduce the concept of Stable States. We also introduce and explain the concept of Dynamic Price of Anarchy (DPoA), since it is used to evaluate the outputs of the voting systems. We provide different approaches for the generation of random voter preferences for its use in the experiments. We conduct experiments to assess how each heuristic behaves with each voting rule when changing different experimental values (such as number of voters, number of candidates, committee size or heuristic distribution) and we compare the initial and final winner committees. In such experiments, we play games in which all voters use the same heuristic. On the other hand, we follow this by setting up experiments in which different heuristics play against each other, to investigate how the heuristics presented in this thesis behave altogether. Finally, we end the thesis giving our conclusions on strategic voting in an iterative setting with approval multi-winner voting rules and identify possibilities for future work.

[ES] En esta tesis el alumno estudiará las votaciones con múltiples ganadores, donde los votantes entregan un voto de aprobación. Este sistema de votación se aplicará a un entorno iterativo: una vez entregado el voto, los votantes pueden cambiar de opinión dado el estado actual de la votación. Desarrollará heurísticas para modelar el comportamiento de votantes, que explicaran como los votantes pueden manipular sus preferencias para obtener un mejor resultado, dando ejemplos de cada uno. Aplicará estas heurísticas a diferentes reglas de votación, como Votación Proporcional de Aprobación (PAV) o la regla de Phragmén, además de las versiones secuenciales de ambas reglas. Se estudiará para que reglas se puede alcanzar un equilibrio de Nash y para que heurísticas se puede alcanzar un estado estable. Se prepararán experimentos donde se aplicarán las heurísticas para averiguar cómo cambiando diferentes variables (número de votantes, número de candidatos, número de ganadores y distribución de heurísticas) afecta al resultado, comparando el comité ganador de la votación sincera y el comité ganador de la votación estratégica. Se estudiarán diferentes formas para generar las preferencias aleatorias de los votantes en los experimentos.