Game-Theoretic Analysis of Transaction Selection in DAG-Based Distributed Ledgers

Resumen Técnico: Análisis Teórico de Juegos sobre la Selección de Transacciones en Libros Mayor Distribuidos Basados en DAG

Enunciado del Problema
En las tecnologías de libro mayor distribuido (DLT) basadas en DAG, múltiples validadores proponen bloques concurrentemente para mejorar el rendimiento. Sin embargo, este paralelismo introduce el desafío de las colisiones de transacciones, donde múltiples validadores seleccionan la misma transacción, lo que genera ineficiencias ya que las inclusiones redundantes no aumentan la utilidad del sistema. Los sistemas actuales a menudo dependen de heurísticas ingenuas para la selección de transacciones, como la selección uniforme o proporcional, sin analizar rigurosamente si estas estrategias constituyen equilibrios de Nash (EN) bajo mecanismos específicos de asignación de tarifas. Además, la interacción entre los modelos de distribución de tarifas y los incentivos de los validadores en un entorno descentralizado y no cooperativo permanece poco examinada. Este artículo aborda esta brecha derivando los equilibrios de Nash mixtos simétricos para estrategias de selección de transacciones bajo dos mecanismos distintos de asignación de tarifas y evaluando su rendimiento frente a referencias ingenuas.

Metodología
Los autores modelan el proceso de selección de transacciones como un juego de una sola ronda (modelo miope) que involucra a $N$ validadores y un conjunto finito de $m$ transacciones con tarifas variables. Cada validador selecciona un subconjunto de $b$ transacciones para incluir en su bloque. El estudio se centra en dos mecanismos de asignación de tarifas:

1. Asignación Aleatoria de Tarifas (RFA): Si múltiples validadores incluyen una transacción, la tarifa se asigna aleatoriamente a exactamente uno de ellos. Este mecanismo es típico de los sistemas de Prueba de Trabajo (PoW) con orden total (por ejemplo, GHOSTDAG).
2. Reparto Colaborativo de Tarifas (CFS): Si al menos un validador incluye una transacción, la tarifa se distribuye equitativamente entre todos los $N$ validadores. Este mecanismo es más típico de protocolos similares a la Tolerancia a Fallos Bizantinos (BFT).

Los autores emplean un marco teórico de juegos para derivar equilibrios de Nash simétricos. Primero establecen un resultado teórico general (Teorema IV.1) que caracteriza el EN mediante una función estrictamente decreciente $f(p)$ que representa la participación esperada de recompensas. Reconociendo que invertir directamente $f(p)$ para RFA es computacionalmente intensivo, el artículo propone un enfoque eficiente basado en optimización utilizando las condiciones de Karush-Kuhn-Tucker (KKT). Esto transforma la derivación del equilibrio en un problema de optimización cóncava resoluble mediante descenso de gradiente proyectado.

El rendimiento de los equilibrios derivados se evalúa numéricamente frente a dos referencias ingenuas:

• Selección Aleatoria de Transacciones (RTS): Selección uniforme.
• Selección Proporcional de Transacciones (PTS): Probabilidad de selección proporcional a las tarifas de las transacciones.

Las métricas incluyen Rendimiento Efectivo de Transacciones (número esperado de transacciones únicas incluidas) y Rendimiento Efectivo de Tarifas (recompensas totales esperadas recolectadas). Las simulaciones utilizan una distribución de tarifas tipo Zipf para modelar estructuras de tarifas sesgadas.

Contribuciones Clave

1. Derivación de Equilibrios de Nash Simétricos: El artículo proporciona la primera derivación explícita de equilibrios de Nash mixtos simétricos para ambos modelos RFA y CFS en un juego de selección de transacciones de una sola ronda.
2. Método de Cálculo Eficiente: Los autores introducen un marco de optimización cóncava utilizando condiciones KKT para calcular estos equilibrios de manera eficiente, superando la intratabilidad computacional de los métodos de inversión directa, particularmente para el modelo RFA.
3. Análisis Comparativo de Rendimiento: Mediante simulaciones numéricas, el estudio demuestra que el EN del mecanismo de Reparto Colaborativo de Tarifas (CFS) logra consistentemente un mayor rendimiento de tarifas y recompensas en comparación con el EN de la Asignación Aleatoria de Tarifas (RFA), especialmente bajo distribuciones de tarifas sesgadas.
4. Evaluación de Estrategias Ingenuas: El análisis revela que, aunque el EN-CFS es óptimo para los ingresos por tarifas, la heurística de Selección Proporcional de Transacciones (PTS) a menudo supera al EN-RFA en términos de recompensas. En escenarios donde CFS no es factible (por ejemplo, sistemas PoW sin permiso), PTS sirve como una alternativa robusta que puede acercarse al rendimiento del equilibrio RFA.

Resultados
Las evaluaciones numéricas bajo parámetros variables (número de transacciones, tarifa máxima y sesgo de tarifas) arrojan las siguientes conclusiones:

• Rendimiento de Tarifas: El equilibrio CFS maximiza consistentemente el rendimiento de tarifas en todos los escenarios probados. La estrategia PTS también se desempeña bien, superando significativamente al equilibrio RFA. Por el contrario, el equilibrio RFA a menudo produce un rendimiento de tarifas inferior incluso a la estrategia uniforme (RTS).
• Rendimiento de Transacciones: Existe una compensación entre la maximización de tarifas y la diversidad de transacciones. La estrategia uniforme (RTS) logra el mayor rendimiento efectivo de transacciones al minimizar las colisiones mediante una distribución de probabilidad pareja. Sin embargo, esto conlleva el costo de un menor rendimiento de tarifas. El equilibrio CFS, aunque maximiza las tarifas, resulta en el menor rendimiento efectivo de transacciones porque los validadores se concentran en transacciones de alta tarifa, lo que genera tasas de colisión más altas para esos elementos específicos.
• Impacto del Sesgo: A medida que las distribuciones de tarifas se vuelven más sesgadas (mayor parámetro de Zipf), la brecha de rendimiento se amplía. CFS y PTS mantienen un rendimiento superior de tarifas, mientras que RFA lucha, destacando su ineficiencia para manejar estructuras de tarifas diversas.

Significado y Afirmaciones
El artículo afirma que sus hallazgos proporcionan información práctica para el diseño de mecanismos de selección de transacciones e incentivos en DLT basadas en DAG. Al caracterizar los equilibrios de Nash, los autores demuestran que las estrategias intuitivas (como la selección uniforme) no siempre son óptimas y que la elección del mecanismo de asignación de tarifas altera fundamentalmente el comportamiento de los validadores y el rendimiento del sistema.

Específicamente, el trabajo sugiere que:

• CFS es superior para ingresos: Si el objetivo principal es maximizar los ingresos por tarifas, CFS con su estrategia de equilibrio correspondiente es el mecanismo más efectivo.
• RFA tiene ineficiencias inherentes: El mecanismo RFA, común en sistemas PoW, conduce a equilibrios que pueden ser superados por heurísticas simples como la selección proporcional, lo que indica una desalineación entre los incentivos individuales y el bienestar colectivo en dichos diseños.
• Heurísticas Prácticas: Para protocolos donde CFS no es factible (por ejemplo, debido a la falta de un conjunto de validadores conocido en entornos sin permiso), la selección proporcional ofrece una heurística valiosa que aproxima el rendimiento de equilibrio de RFA sin requerir un cálculo de equilibrio complejo.

Los autores mantienen un alcance modesto, reconociendo que el estudio se limita a un modelo de una sola ronda con tarifas estáticas y latencias homogéneas. Señalan que extender este análisis a juegos secuenciales de múltiples rondas con tarifas dinámicas y condiciones de red heterogéneas sigue siendo un paso necesario para la aplicabilidad en el mundo real. El artículo no propone nuevas implementaciones de protocolos, sino que proporciona una base teórica y numérica para evaluar las estructuras de incentivos existentes y futuras.