Diseño de mecanismos algorítmicos distribuidos

El equilibrio de Nash es la noción de equilibrio más utilizada en la teoría de juegos. Sin embargo, el equilibrio de Nash no contempla comportamientos erróneos o inesperados. Un protocolo que alcanza el equilibrio de Nash tiene garantizada su correcta ejecución ante agentes racionales, sin que ningún agente pueda mejorar su utilidad desviándose del protocolo. ^{[ 2 ]}

No existe un centro de confianza como en AMD . Por lo tanto, los agentes deben implementar los mecanismos por sí mismos. El supuesto de preferencia de solución requiere que cada agente prefiera cualquier resultado a ningún resultado: por lo tanto, los agentes no tienen incentivos para discrepar sobre un resultado o provocar el fallo del algoritmo. En otras palabras, como dijeron Afek et al., "los agentes no pueden ganar si el algoritmo falla". ^{[ 3 ]} En consecuencia, aunque los agentes tienen preferencias, no tienen incentivos para que el algoritmo falle.

Se considera que un mecanismo es veraz si los agentes no obtienen ningún beneficio al mentir sobre sus propios valores o los de otros agentes. Un buen ejemplo sería un algoritmo de elección de líder que selecciona un servidor de computación dentro de una red. El algoritmo especifica que los agentes deben enviar su potencia computacional total entre sí, tras lo cual se elige al agente más potente como líder para completar la tarea. En este algoritmo, los agentes pueden mentir sobre su verdadera potencia computacional porque corren el riesgo de que se les asignen tareas que consumen muchos recursos de CPU, lo que reducirá su capacidad para completar tareas locales. Esto se puede superar con la ayuda de mecanismos veraces que, sin ningún conocimiento previo de los datos y entradas existentes de cada agente, hacen que cada agente responda con veracidad a las solicitudes. ^{[ 4 ]}

Un mecanismo veraz muy conocido en la teoría de juegos es la subasta de Vickrey .

La elección de líder es un problema fundamental en la computación distribuida y existen numerosos protocolos para resolverlo. Se supone que los agentes del sistema son racionales y, por lo tanto, prefieren tener un líder a no tenerlo. Los agentes también pueden tener diferentes preferencias respecto a quién se convierte en líder (un agente puede preferir ser él mismo el líder). Los protocolos estándar pueden elegir líderes basándose en el ID más bajo o más alto de los agentes del sistema. Sin embargo, dado que los agentes tienen un incentivo para mentir sobre su ID con el fin de mejorar su utilidad, dichos protocolos resultan inútiles en el contexto del diseño de mecanismos algorítmicos. Ittai et al. han presentado un protocolo para la elección de líder en presencia de agentes racionales.

• En la ronda 1, cada agente i envía a todos su identificación;
• En la ronda 2, el agente i envía a cada agente j el conjunto de identificadores que ha recibido (incluido el suyo propio). Si los conjuntos recibidos por el agente i no son todos idénticos o si i no recibe un identificador de algún agente, entonces i establece su salida en Null y la elección del líder falla. En caso contrario, sea n la cardinalidad del conjunto de identificadores.
• El agente i elige un número aleatorio N _i en {0, ..., n−1} y lo envía a todos los demás agentes.
• Cada agente i calcula entonces Σ ⁿ _i=1 N _i (mod n) y, a continuación, elige como líder al agente con el N-ésimo ID más alto del conjunto. (Si algún agente j no envía un número aleatorio ia, entonces i establece su salida en Nulo).

Este protocolo elige correctamente a un líder mientras alcanza el equilibrio y es veraz ya que ningún agente puede beneficiarse mintiendo sobre su aporte. ^{[ 5 ]}