Control de elección multi-ganador a través de influencia social: dificultad y algoritmos para casos restringidos
Autores: Abouei Mehrizi, Mohammad; D"Angelo, Gianlorenzo
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Control de elección multi-ganador a través de influencia social: dificultad y algoritmos para casos restringidos
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Campañas políticas
Influencia social
Control electoral
Votantes
Modelos de difusión
Sistema de votación
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 22
Citaciones: Sin citaciones
Hoy en día, muchas campañas políticas están utilizando la influencia social para convencer a los votantes de apoyar/oponerse a un candidato/partido específico. En el problema de control de elecciones a través de la influencia social, un atacante intenta encontrar un conjunto limitado de influencers para comenzar a difundir un mensaje político en una red social de votantes. Un votante cambiará su opinión cuando reciba y acepte el mensaje. En el caso constructivo, el objetivo es maximizar el número de votos/ganadores de un candidato/partido objetivo, mientras que en el caso destructivo, el atacante intenta minimizarlos. Trabajos recientes han considerado el problema en diferentes modelos y han presentado algunos resultados de dificultad y aproximación. En este trabajo, consideramos el control de elecciones de múltiples ganadores a través de la influencia social en diferentes estructuras de gráficos y modelos de difusión, y nuestro objetivo es maximizar/minimizar el número de ganadores en nuestro partido objetivo. Mostramos que el problema es difícil de aproximar cuando las conexiones de los votantes forman un gráfico, y el modelo de difusión es el modelo de umbral lineal. También demostramos el mismo resultado considerando una arborescencia bajo el modelo de cascada independiente. Además, presentamos un algoritmo de programación dinámica para los casos en que el sistema de votación es una variación de votación de partido único, y los votantes forman un árbol.
Descripción
Hoy en día, muchas campañas políticas están utilizando la influencia social para convencer a los votantes de apoyar/oponerse a un candidato/partido específico. En el problema de control de elecciones a través de la influencia social, un atacante intenta encontrar un conjunto limitado de influencers para comenzar a difundir un mensaje político en una red social de votantes. Un votante cambiará su opinión cuando reciba y acepte el mensaje. En el caso constructivo, el objetivo es maximizar el número de votos/ganadores de un candidato/partido objetivo, mientras que en el caso destructivo, el atacante intenta minimizarlos. Trabajos recientes han considerado el problema en diferentes modelos y han presentado algunos resultados de dificultad y aproximación. En este trabajo, consideramos el control de elecciones de múltiples ganadores a través de la influencia social en diferentes estructuras de gráficos y modelos de difusión, y nuestro objetivo es maximizar/minimizar el número de ganadores en nuestro partido objetivo. Mostramos que el problema es difícil de aproximar cuando las conexiones de los votantes forman un gráfico, y el modelo de difusión es el modelo de umbral lineal. También demostramos el mismo resultado considerando una arborescencia bajo el modelo de cascada independiente. Además, presentamos un algoritmo de programación dinámica para los casos en que el sistema de votación es una variación de votación de partido único, y los votantes forman un árbol.