Límites Estrictos sobre la Distorsión de la Votación Distribuida Aleatorizada y Determinista

Información Básica

• ID del Artículo: 2509.17134
• Título: Tight Bounds On the Distortion of Randomized and Deterministic Distributed Voting
• Autores: MohammadAli Abam, Davoud Kareshki, Marzieh Nilipour, MohammadHossein Paydar, Masoud Seddighin
• Instituciones: Sharif University of Technology (Teherán, Irán); Tehran Institute for Advanced Studies (TeIAS), Khatam University
• Clasificación: cs.GT (Teoría de Juegos)
• Fecha de Publicación: 23 de noviembre de 2025 (arXiv v2)
• Enlace del Artículo: https://arxiv.org/abs/2509.17134v2

Resumen

Este artículo investiga el problema de la distorsión métrica en votación distribuida, donde n votantes se dividen en k grupos, cada grupo selecciona un representante local, y finalmente se elige un ganador de estos representantes (o de todos los candidatos). Esta configuración simula sistemas como las elecciones presidenciales estadounidenses. El artículo propone límites mejorados de distorsión para cuatro objetivos de costo (avg-avg, avg-max, max-avg, max-max). Para mecanismos deterministas, reduce el límite superior de avg-max de 11 a 7, establece un límite inferior estricto de 5 para max-avg (mejorando 2+√5), y ajusta el límite superior de max-max de 5 a 3. Para mecanismos aleatorizados, establece límites estrictos o casi estrictos en ambas configuraciones.

Antecedentes y Motivación de la Investigación

Definición del Problema

En la teoría de la elección social, las reglas de votación necesitan transformar las preferencias de los agentes en un resultado final. La votación centralizada tradicional asume que las preferencias de todos los votantes pueden agregarse directamente, pero en escenarios a gran escala (como las elecciones presidenciales estadounidenses), la toma de decisiones generalmente se realiza a través de un proceso distribuido de dos fases:

1. Fase Intragrupal: Cada grupo selecciona independientemente un representante local
2. Fase Intergrupal: Se selecciona el ganador final de los representantes

Importancia del Problema

1. Aplicación Práctica Generalizada: El sistema de colegio electoral estadounidense, la toma de decisiones federal, y la votación en organizaciones multinivel utilizan estructuras distribuidas
2. Asimetría de Información: Las reglas de votación solo pueden acceder a preferencias ordinales (ordenamientos), no a valores cardinales reales
3. Desafío Teórico: Se requiere evaluar las garantías de desempeño de los mecanismos bajo información limitada

Limitaciones de los Métodos Existentes

• Anshelevich et al. (2022) realizó el primer estudio sistemático de votación distribuida determinista, pero con brechas significativas:
  • avg-max: 2+√5, 11
  • max-avg: 2+√5, 5
  • max-max: 3, 5
• Mecanismos Aleatorizados No Estudiados: Aunque la aleatorización en votación centralizada puede romper el límite inferior de distorsión 3, los mecanismos aleatorizados en escenarios distribuidos están completamente sin explorar
• Espacios Métricos Especiales: Las métricas lineales fueron resueltas por Voudouris (2023), pero los espacios métricos generales aún tienen problemas abiertos

Motivación de la Investigación

1. Explorar si la aleatorización puede traer mejoras de distorsión en configuraciones distribuidas
2. Ajustar los límites conocidos de mecanismos deterministas
3. Proporcionar una caracterización casi completa de la distorsión en votación distribuida

Contribuciones Principales

1. Primer Estudio Sistemático de Mecanismos Distribuidos Aleatorizados:
   • Mecanismo rand-det (solo segunda fase aleatoria): Establece límites estrictos para los cuatro objetivos
   • Mecanismo rand-rand (ambas fases aleatorias): Establece límites estrictos o casi estrictos
2. Mejora de Límites de Mecanismos Deterministas:
   • avg-max: Límite superior reducido de 11 a 7
   • max-avg: Límite inferior mejorado de 2+√5 al límite estricto 5
   • max-max: Límite superior ajustado de 5 a 3
3. Introducción de Nueva Herramienta de Análisis—Torneo Sesgado (Bias Tournament):
   • Captura las preferencias de desempate de reglas deterministas
   • Se utiliza para pruebas de límites inferiores mediante construcción de instancias de alta distorsión
4. Límites Especializados para Espacios Euclidianos:
   • rand-rand: Límite inferior √5-ε
   • rand-det: Límite inferior 2+√5-ε
5. Resultados Secundarios en Votación Centralizada:
   • Demuestra que las reglas de votación aleatorizadas tienen distorsión de al menos 3-ε bajo el objetivo max (casi coincidiendo con el límite superior conocido 3)

Explicación Detallada de Métodos

Definición de Tareas

Entrada:

• Conjunto de votantes V (|V|=n), dividido en k grupos G
• Conjunto de candidatos C (|C|=m)
• Espacio métrico d: V×C→ℝ⁺, satisfaciendo la desigualdad triangular
• Preferencias π: Cada votante ordena candidatos en orden de distancia creciente

Salida:

• Mecanismo distribuido Ψ=(f_in, f_ov) selecciona el ganador w

Objetivo: Minimizar la distorsión D(Ψ) = sup_I Ecost(w|I) / min_c cost(c|I)

Cuatro Objetivos de Costo:

1. avg-avg: Promedio intragrupal luego promedio intergrupal
2. avg-max: Máximo intragrupal luego promedio intergrupal
3. max-avg: Promedio intragrupal luego máximo intergrupal
4. max-max: Máximo intragrupal luego máximo intergrupal

Marco Técnico Principal

1. Torneo Sesgado (Bias Tournament)

Definición: Dado una regla determinista f y un ordenamiento de candidatos σ, construir un grafo dirigido completo T(f,C,σ):

• Vértices: Cada candidato
• Aristas: Para un par de candidatos (u,w), si en elecciones con dos votantes cuyas preferencias son σ↑w↑u y σ↑u↑w la regla f selecciona u, agregar una arista u→w

Propiedades Clave (Observación 2.2): Cualquier torneo con m vértices tiene al menos un vértice con grado de entrada ≥⌈(m-1)/2⌉

Aplicaciones:

• Identificar "candidatos fallidos" (alto grado de entrada)
• Construir instancias donde ese candidato es óptimo pero no puede ser seleccionado
• Utilizado para pruebas de límites inferiores de rand-det y det-det

2. Análisis del Mecanismo rand-det

Diseño del Mecanismo: (f_pm-par, f_ur)

• Primera fase: Plurality Matching with Pareto Efficiency
• Segunda fase: Selección uniforme aleatoria

Teoremas Clave:

Teorema 3.1 (max-avg): D((f_α, f_ur)) ≤ α+2

• Estrategia de prueba: Utilizar eficiencia de Pareto, existe un votante v_g que prefiere w_g sobre o
• Mediante expansión de cadena de desigualdad triangular:

  E[cost(w)] ≤ cost(o) + (1/k)Σ_g d(o,w_g)
               ≤ cost(o) + (1/k)Σ_g [d(o,v_g) + d(v_g,w_g)]
               ≤ cost(o) + (1/k)Σ_g 2d(v_g,o)  [porque d(v_g,w_g)≤d(v_g,o)]
               ≤ (α+2)cost(o)
  

Teorema 3.3 (avg-avg): D((f_α, f_ur)) ≤ α+2-2/k

• Clave: Separar términos intragrupo e intergrupo, los términos intragrupo contribuyen una mejora de -2/k

Teorema 3.5 (avg-max, max-max): D((f_par, f_ur)) ≤ 3

• Solo se requiere eficiencia de Pareto para alcanzar 3 (sin necesidad del supuesto fuerte α=3)

Construcción de Límites Inferiores:

Teorema 3.7 (max-avg, límite inferior 5):

• Usar torneo sesgado para encontrar candidato c₁ con grado de entrada ≥2
• Construir instancia lineal métrica con 4 candidatos, 4 votantes, 2 grupos
• Asegurar que c₂ y c₃ sean representantes, cost(c₁)=1/4, cost(c₂)=cost(c₃)=5/4

Teorema 3.8 (avg-avg, límite inferior 5-2/k):

• Usar métrica de camino más corto de grafo (no lineal)
• k grupos de votante único, 2k candidatos
• Estructura de árbol: candidato central c_2k es óptimo, pero cada grupo tiene representante c_i (1≤i≤k)

3. Análisis del Mecanismo rand-rand

Diseño del Mecanismo: (f_rd, f_ur)

• Primera fase: Random Dictatorship (seleccionar uniformemente el primer candidato preferido de un votante)
• Segunda fase: Selección uniforme aleatoria

Observación Clave (Observación 2.6):

E[cost(w)] = (1/k)Σ_g (1/n_g)Σ_{v∈g} cost(top(v))

Estrategia de Prueba de Límite Superior:

Teorema 4.1 (max-max, límite superior 3): Para cualquier votante v:

cost(top(v)) = d(v**(top(v)), top(v))
             ≤ d(v**(top(v)), o) + d(o,v) + d(v,top(v))  [desigualdad triangular]
             ≤ d(v**(o), o) + d(v,o) + d(v,o)  [top(v) es el candidato más cercano a v]
             ≤ 3d(v**(o), o) = 3cost(o)

Teorema 4.4 (avg-avg, límite superior 3-2/(kn*)):

• Prueba más compleja, requiere manejo fino de doble suma
• Clave: Separar términos donde v'=v, contribuyendo mejora de -2/(kn*)
• Cuando todos los tamaños de grupo son iguales, el límite es 3-2/n

Construcción de Límites Inferiores:

Teorema 4.6 (max-avg, max-max, límite inferior 3):

• 2 votantes, 3 candidatos, 2 grupos de votante único
• Métrica lineal: c₁(-1), c₂(0), c₃(1); v₁(-0.5), v₂(0.5)
• Debe seleccionar c₁ o c₃, cost=3/2, mientras que cost(c₂)=1/2

Teorema 4.7 (avg-max, límite inferior 3-2/n):

• m candidatos, m votantes, grupo único
• Construir m instancias I_i, en I_i el candidato c_i es óptimo
• Preferencias cíclicas: π_i = (c_i, c_{i+1}, ..., c_m, c_1, ..., c_)
• Argumento probabilístico: Debe existir i tal que p_i≤1/m

Corolario 4.8: Esta construcción también prueba el límite inferior 3-ε para votación aleatoria centralizada bajo el objetivo max

Teorema 4.9 (avg-avg, límite inferior 3-2/n):

• k grupos de votante único, k+1 candidatos
• Árbol: candidato central c_m es óptimo, pero no es representante de ningún grupo

4. Mejoras del Mecanismo det-det

Teorema 5.1 (max-max, límite superior 3):

• Mecanismo Arbitrary Dictator alcanza 3
• Mejora el resultado de 5 de Anshelevich et al.

Teorema 5.2 (avg-max, límite superior 2β+3):

• Mecanismo (f_par, f_β)
• Clave: Utilizar eficiencia de Pareto, independiente de α
• Tomando β=2 (f_pm-par), se obtiene límite superior 7

Teorema 5.4 (max-avg, límite inferior 5):

• Usar torneo sesgado y métrica de grafo (no lineal)
• 4 candidatos, 4 votantes, 2 grupos
• Construir dos instancias I₁ e I₂, asegurando que al menos una excluya el candidato óptimo

Puntos de Innovación Técnica

1. Introducción del Torneo Sesgado:
   • Formalizar el comportamiento de desempate de reglas deterministas como estructura de grafo
   • Utilizar propiedades combinatorias de torneos (debe existir vértice de alto grado de entrada)
   • Permitir construcción sistematizada de instancias de límites inferiores
2. Utilización Debilitada de Eficiencia de Pareto:
   • Demostrar que avg-max solo requiere eficiencia de Pareto para alcanzar 3 (sin necesidad de α=3)
   • Desacoplar dependencias de distorsión entre dos fases
3. Análisis Fino de Doble Suma:
   • El objetivo avg-avg requiere manejo de promedios anidados
   • Obtener mejoras separando términos diagonales (v'=v, g'=g)
4. Uso de Espacios Métricos No Lineales:
   • Muchos límites inferiores requieren métrica de camino más corto de grafo (no incrustable en lineal o euclidiano)
   • Demuestra la complejidad esencial del problema
5. Construcción de Símplex Euclidiano:
   • Construir instancias simétricas en R^{l+1}
   • Utilizar geometría de alta dimensión para obtener límite inferior √5

Configuración Experimental

Nota: Este artículo es puramente teórico, sin sección experimental. Todos los resultados se establecen mediante pruebas matemáticas.

Métodos de Verificación Teórica

1. Pruebas Constructivas:
   • Límites inferiores: Construir instancias concretas, calcular distorsión
   • Límites superiores: Analizar desempeño del mecanismo para instancias arbitrarias
2. Tipos de Espacios Métricos:
   • Espacio métrico general (satisfaciendo desigualdad triangular)
   • Métrica lineal (unidimensional)
   • Espacio euclidiano (multidimensional)
   • Métrica de camino más corto de grafo
3. Características de Instancias:
   • Instancias simétricas (todos los tamaños de grupo iguales)
   • Grupos de votante único
   • Instancias pequeñas (2-4 grupos, 2-4 candidatos)

Resultados Experimentales

Resumen de Resultados Principales

Tabla 2: Descripción General de Resultados Completos

Negrita indica nuevos resultados, ↑/↓ indica dirección de mejora

Hallazgos Clave

1. Valor de la Aleatorización:
   • rand-det alcanza o se aproxima al óptimo en todos los objetivos
   • rand-rand mejora aún más avg-avg (de 5-2/k a 3-2/n)
   • Pero max-avg y max-max no pueden romper la barrera de 3
2. Límites de Mecanismos Deterministas:
   • El límite estricto de max-avg es 5 (superior al 3 centralizado)
   • max-max puede alcanzar 3 (igual al centralizado)
   • avg-max aún tiene brecha (7 vs 2+√5)
3. Distribuido vs Centralizado:
   • Votación aleatoria centralizada: distorsión de objetivo max ≥3-ε (Corolario 4.8)
   • Distribuido añade complejidad, ciertos objetivos tienen distorsión más alta
4. Impacto del Espacio Métrico:
   • Métrica lineal: muchos límites inferiores realizables en línea
   • Métrica general: algunos límites inferiores requieren métrica de grafo (como max-avg de 5)
   • Euclidiano: límites ligeramente más bajos (√5 vs 3-2/n)

Perspectivas Técnicas

1. Interacción de Dos Fases:
   • avg-max: Segunda fase dominante (2β+3 independiente de α)
   • max-avg: Ambas fases importantes (α+2)
   • avg-avg: Efecto de doble promedio fino (α+2-2/k)
2. Rol de Eficiencia de Pareto:
   • Suficiente para alcanzar 3 en ciertos objetivos (sin necesidad de Plurality Matching completo)
   • Proporciona restricción clave en relación votante-representante
3. Desafío del Análisis Probabilístico:
   • El límite superior rand-rand de avg-avg requiere manejo de cuádruple suma
   • El manejo preciso de términos diagonales es crítico

Trabajo Relacionado

Distorsión en Votación Centralizada

1. Mecanismos Deterministas:
   • Anshelevich et al. (2018): Límite inferior 3
   • Gkatzelis et al. (2020): Plurality Matching alcanza límite superior 3 (estricto)
   • Kizilkaya & Kempe (2022): Plurality Veto simplificado alcanza 3
2. Mecanismos Aleatorizados:
   • Anshelevich & Postl (2017): Random Dictatorship alcanza 3-2/n
   • Charikar & Ramakrishnan (2022): Límite inferior 2.112
   • Charikar et al. (2024): Límite superior 2.753 (mejor actual)

Votación Distribuida

1. Marco de Utilidad:
   • Filos-Ratsikas et al. (2020): Primer estudio de distorsión distribuida
   • Filos-Ratsikas & Voudouris (2024): Mecanismos aleatorizados, distorsión Θ(km²)
2. Marco Métrico:
   • Anshelevich et al. (2022): Primer estudio sistemático de mecanismos deterministas
   • Voudouris (2023): Límites estrictos para métrica lineal
   • Este Artículo: Mecanismos aleatorizados en métrica general

Otros Problemas de Elección Social

1. Selección de Instalaciones: Aplicación del marco de distorsión métrica
2. Problemas de Emparejamiento: Aproximación bajo preferencias ordinales
3. Elección de Comités: Configuración de múltiples ganadores

Ventajas de Este Artículo

1. Primer estudio completo de mecanismos distribuidos aleatorizados
2. Casi todos los límites son estrictos (9/12 estrictos, 3/12 casi estrictos)
3. Introducción de nueva herramienta (Torneo Sesgado)
4. Cobertura de múltiples espacios métricos (general, lineal, euclidiano)

Conclusiones y Discusión

Conclusiones Principales

1. Caracterización Casi Completa:
   • 9 de 12 límites estrictos, 3 casi estrictos
   • Solo avg-avg de det-det aún tiene brecha significativa (7 vs 11)
2. Efectividad de la Aleatorización:
   • rand-det alcanza límites estrictos en todos los objetivos
   • rand-rand mejora aún más avg-avg
   • Mecanismos simples (Random Dictatorship + selección uniforme) alcanzan lo óptimo
3. Mejora de Mecanismos Deterministas:
   • Resuelve límites estrictos de max-avg y max-max
   • avg-max reducido de 11 a 7
4. Contribución Metodológica:
   • Torneo Sesgado proporciona marco sistematizado para construcción de límites inferiores
   • Utilización debilitada de eficiencia de Pareto

Limitaciones

1. Brechas Restantes:
   • det-det de avg-avg: 7, 11
   • rand-rand de avg-avg: 3-2/n, 3-2/(kn*) (estricto solo en caso simétrico)
   • rand-rand de avg-max: 3-2/n, 3
2. Mecanismo det-rand No Estudiado:
   • Primera fase determinista, segunda fase aleatoria
   • Torneo Sesgado no aplicable a primera fase aleatoria
   • Actualmente solo límites aproximados heredados de rand-rand y det-det
3. Restricción de Espacio Métrico:
   • Algunos límites inferiores requieren métrica general (camino más corto de grafo)
   • Los límites en espacio euclidiano podrían ser más bajos
4. Consideraciones Prácticas:
   • No considera comportamiento estratégico (no compatible con incentivos)
   • No considera complejidad de comunicación
   • No considera complejidad computacional

Direcciones Futuras

1. Mecanismo det-rand:
   • Desarrollar nuevas herramientas de análisis
   • Posiblemente requiere técnicas diferentes al Torneo Sesgado
2. Cerrar Brechas Restantes:
   • avg-avg de det-det
   • avg-avg de rand-rand (caso no simétrico)
3. Espacios Métricos Especiales:
   • Métrica lineal: ciertos objetivos aún no resueltos
   • Euclidiano: posiblemente límites más bajos
   • Métrica de árbol: complejidad intermedia
4. Configuraciones Extendidas:
   • Elección de comités (múltiples ganadores)
   • Información cardinal (acceso a distancias reales)
   • Votación estratégica (mecanismos compatibles con incentivos)
5. Computación y Comunicación:
   • Implementación de algoritmos eficientes
   • Límites inferiores de complejidad de comunicación
   • Configuraciones en línea/streaming

Evaluación Profunda

Fortalezas

1. Profundidad Teórica:
   • 9 de 12 límites estrictos, demostrando comprensión profunda del problema
   • Técnicas de prueba diversas y sofisticadas (Torneo Sesgado, análisis de doble suma, argumentos probabilísticos)
2. Sistematicidad:
   • Cubre 3 tipos de mecanismo × 4 objetivos = 12 problemas
   • Marco unificado y notación clara
   • Comparación clara de resultados (Tabla 2)
3. Innovación Metodológica:
   • Torneo Sesgado: Captura elegantemente la estructura de reglas deterministas
   • Utilización debilitada de eficiencia de Pareto: Desacopla dependencias entre fases
   • Posible valor independiente
4. Calidad de Escritura:
   • Estructura clara, progresión de simple a complejo
   • Explicaciones intuitivas suficientes e ilustraciones
   • Detalles de prueba completos
5. Completitud:
   • Múltiples espacios métricos (general, lineal, euclidiano)
   • Instancias simétricas y no simétricas
   • Resultados secundarios en votación centralizada

Deficiencias

1. Vacío det-rand:
   • El artículo reconoce esto como problema abierto principal
   • Las herramientas actuales no son aplicables, requiere nuevos métodos
2. Ciertas Brechas No Cerradas:
   • det-det de avg-avg: 7, 11 aún bastante grande
   • Aunque los autores han mejorado significativamente, no completamente resuelto
3. Utilidad Práctica Limitada:
   • Resultados puramente teóricos, sin verificación experimental
   • No considera restricciones de sistemas de votación reales (estrategia, computación)
   • Análisis de peor caso posiblemente demasiado pesimista
4. Dependencia del Espacio Métrico:
   • Algunos límites inferiores requieren métricas de grafo complejas
   • Los espacios métricos en aplicaciones reales podrían ser más estructurados
5. Complejidad del Mecanismo:
   • Plurality Matching computacionalmente complejo (problema de emparejamiento)
   • Sistemas reales podrían preferir reglas más simples

Impacto

1. Contribución Teórica:
   • Resuelve casi completamente el problema de distorsión en votación distribuida
   • Establece resultados de referencia en el campo
   • Torneo Sesgado posiblemente inspire investigación en otros problemas
2. Investigación Posterior:
   • Investigación de mecanismo det-rand
   • Versiones distribuidas de otros problemas de elección social
   • Extensiones con aspectos estratégicos y computacionales
3. Valor Práctico:
   • Proporciona orientación teórica para diseño de sistemas de votación distribuida
   • Cuantifica garantías de desempeño de diferentes mecanismos
   • Pero aún distante de despliegue real
4. Reproducibilidad:
   • Trabajo puramente teórico, pruebas verificables
   • Instancias de construcción explícitas, fáciles de verificar
   • Sin código o experimentos, pero no afecta reproducibilidad

Escenarios Aplicables

1. Investigación Teórica:
   • Teoría de elección social
   • Teoría de juegos algorítmica
   • Algoritmos de aproximación
2. Diseño de Sistemas:
   • Sistemas de votación federales
   • Toma de decisiones organizacional multinivel
   • Protocolos de consenso distribuido
3. Enseñanza:
   • Estudios de caso en teoría de distorsión
   • Aplicaciones de algoritmos aleatorizados
   • Técnicas de optimización combinatoria
4. Escenarios No Aplicables:
   • Sistemas electorales reales que requieren compatibilidad de incentivos
   • Sistemas en línea con restricciones computacionales
   • Espacios de preferencia no métricos

Referencias Clave

1. Anshelevich et al. (2022): "The distortion of distributed metric social choice" - Predecesor directo de este artículo
2. Gkatzelis et al. (2020): "Resolving the optimal metric distortion conjecture" - Límite estricto 3 para votación centralizada
3. Filos-Ratsikas et al. (2020): "The distortion of distributed voting" - Trabajo pionero en votación distribuida
4. Charikar et al. (2024): "Breaking the metric voting distortion barrier" - Avances recientes en votación aleatoria centralizada
5. Voudouris (2023): "Tight distortion bounds for distributed metric voting on a line" - Resolución completa para métrica lineal

Evaluación General: Este es un artículo teórico de alta calidad que resuelve casi completamente el problema de distorsión en votación distribuida, introduce nuevas herramientas de análisis (Torneo Sesgado), y establece 9 límites estrictos y 3 casi estrictos. Aunque el mecanismo det-rand permanece sin resolver y ciertas brechas persisten, la sistematicidad, profundidad técnica e innovación metodológica del artículo lo convierten en una contribución importante al campo. Para investigadores teóricos, es lectura obligatoria; para profesionales, proporciona referencias valiosas de garantías de desempeño.