**SVRAI** **Diseño de Mecanismos** En este capítulo estudiaremos el problema del **diseño de mecanismos**, que consiste en desarrollar protocolos de interacción entre agentes que tengan en cuenta explícitamente el hecho de que los agentes pueden tener intereses propios. Discutimos el _principio de revelación_ y la familia de _mecanismos de Groves-Clarke_, que nos permiten construir protocolos exitosos en una amplia variedad de problemas prácticos. # Agentes con intereses propios !!!side:1 Un agente futbolista, por ejemplo, nunca violaría un protocolo que asigna roles a sus compañeros de equipo porque esto podría perjudicar potencialmente el rendimiento de su equipo. En los capítulos anteriores hemos estudiado principalmente sistemas multiagente formados por agentes cooperativos. El hecho de que los agentes trabajen cooperativamente por un objetivo común nos permitió desarrollar algoritmos, como los de coordinación, en los que se supone que los agentes son sinceros entre sí y se comportan según las instrucciones $^1$. !!!side:2 Por ejemplo, agentes que actúan en nombre de algún propietario que quiere maximizar su propio beneficio. Un ejemplo típico es un agente de software que participa en una subasta electrónica en Internet. En muchas aplicaciones prácticas, sin embargo, tenemos que tratar con agentes interesados en sí mismos $^2$. Desarrollar un algoritmo o protocolo para un sistema de este tipo es una tarea mucho más difícil que en el caso cooperativo: * En primer lugar, tenemos que motivar a un agente para que participe en el protocolo, lo que a priori puede no ser el caso. * En segundo lugar, tenemos que tener en cuenta el hecho de que un agente puede intentar manipular el protocolo en su propio interés, dando lugar a resultados subóptimos. Esto último incluye la posibilidad de que el agente mienta, si es necesario. El desarrollo de protocolos que sean estables (no manipulables) e individualmente racionales para los agentes (ningún agente sale perjudicado por participar) es el tema del **Diseño de Mecanismos** o **Teoría de la Implementación**. Como veremos a continuación, una forma habitual de abordar los dos problemas anteriores es ofrecer pagos a los agentes a cambio de sus servicios. # El problema del diseño de mecanismos Hemos utilizado anteriormente el modelo de Juegos Estratégicos para describir una situación en la que un grupo de agentes interactúan entre sí. Las primitivas de un juego de este tipo son los conjuntos de acciones $A_i$ y las funciones de retribución $u_i(a)$ de los agentes, para $i = 1, \dots, n$, donde $u_i(a)$ refleja la preferencia del agente $i$ por la acción conjunta $a$. Además, para cualquier perfil de funciones de retribución, un concepto de solución (por ejemplo, el equilibrio de Nash) permite hacer predicciones sobre el conjunto de resultados que pueden producirse cuando se participa en el juego. Nuestro punto de vista en aquel momento era el de un observador externo que quiere conocer el resultado de un juego, pero que no puede afectar a este resultado de ninguna manera. En el **diseño de mecanismos** vamos un paso más allá. Asumimos un conjunto $\mathcal{O}$ de posibles resultados sobre los que los agentes tienen preferencias. Nuestra tarea consiste en diseñar un juego que, al ser jugado por los agentes, produzca un resultado deseado a partir de $\mathcal{O}$. En este marco utilizamos un juego como herramienta para alcanzar los objetivos de diseño. Un resultado puede ser prácticamente cualquier cosa, por ejemplo, la asignación de un recurso a un agente. La principal dificultad en el diseño de mecanismos es que a menudo no se conocen de antemano las preferencias de los agentes. Más formalmente, en cada estado del mundo suponemos que cada agente $i$ recibe cierta información privada $θ_i ∈ \Theta_i$, llamada **tipo del agente**, que no se revela a los demás agentes ni a nosotros (el diseñador del mecanismo). Podemos ver un perfil $θ = (θ_i)$ de tipos de agente como un estado del mundo, y en cada estado $θ$ el agente $i$ considera posibles todos los estados en los que su tipo es $θ_i$. Además, suponemos que el tipo de un agente especifica completamente las preferencias de este agente sobre el conjunto de resultados $o ∈ \mathcal{O}$. En particular, cada agente $i$ tiene una **función de valoración** $ν_i(o, θ_i)$, que está parametrizada en $θ_i$, tal que el agente $i$ en el tipo $θ_i$ prefiere el resultado $o$ a $o'$ si y sólo si $ν_i(o, θ_i) > ν_i(o', θ_i)$. Supondremos que en cada estado $θ$ conocemos la función de valoración de cada agente $i$ (pero no su tipo), y este hecho es de conocimiento común entre todos los agentes. En un problema de diseño de mecanismos tenemos una **función de elección social** $f(θ)$ que, para cada perfil $θ = (θ_i)$ de tipos de agentes, produce un resultado deseado $o = f(θ)$. Podemos pensar en $f$ como un algoritmo que resuelve un problema de optimización: dadas $n$ entradas $θ = (θ_i)$, la función $f$ calcula un resultado $o$ que maximiza una función sobre el conjunto de valoraciones de los agentes. Un caso típico, que examinaremos con más detalle en la sección 7.4, es seleccionar el resultado que maximiza la suma de las valoraciones de los agentes dados sus tipos: \begin{equation} \label{7.1} f(θ) = \arg \max_{o\in \mathcal{O}} \sum_{i=1}^n ν_i(o, θ_i) \end{equation} Una función de elección social de este tipo se denomina **asignativamente eficiente**. Implementar una función de elección social sería fácil si tuviéramos plena observabilidad del estado $θ$. Entonces podríamos utilizar $θ$ en la Eq. [7.1] y calcular el resultado óptimo deseado (suponiendo, por supuesto, que tenemos un algoritmo manejable para hacerlo). Sin embargo, como hemos visto antes, $θ_i$ sólo se revela al agente $i$. Una opción sería pedir a cada agente que nos dijera su tipo, pero no hay garantía de que un agente informe de su verdadero tipo porque ya no estamos en un problema colaborativo. Recordemos que cada agente $i$ forma sus propias preferencias sobre los resultados, dadas por su función de valoración $ν_i(o, θ_i)$ con $θ_i$ su tipo verdadero. Si informando de un tipo falso $\tilde{θ}i \neq θ_i$ un agente $i$ pudiera recibir una recompensa mayor que informando del tipo verdadero $θ_i$, entonces este agente puede considerar mentir. Como mencionamos en la introducción, en el diseño de mecanismos nuestro punto de partida es que los agentes tienen interés propio. Visto desde una perspectiva computacional, podemos caracterizar el diseño de mecanismos como sigue: !!!def:Definición El diseño de mecanismos es el desarrollo de algoritmos eficientes para problemas de optimización en los que algunos de los parámetros de la función objetivo están bajo el control de agentes que tienen preferencias diferentes por soluciones diferentes. El reto es, por tanto, diseñar mecanismos que dirijan a los agentes hacia la selección de la $o = f(θ)$ deseada por ellos mismos, para cualquier perfil de sus tipos. Sin embargo, primero tenemos que motivar a los agentes para que participen en un mecanismo de este tipo. Para ello, definimos una **función de pago** $p(o)$ que asocia a cada resultado $o$ un perfil $p(o) = (p_i(o))$ de pagos, de forma que el agente $i$ recibe el pago $p_i(o)$ cuando se produce $o$. La función de valoración junto con la función de pago definen la función de pago de un agente (suponemos que los pagos y las valoraciones se expresan en las mismas unidades): \begin{equation} \label{7.2} u_i(o, θ_i) = ν_i(o, θ_i) + p_i(o) \end{equation} Un mecanismo que implementa una función de elección social $f(θ)$ en la que ningún agente sale perjudicado por participar, es decir, $u_i(f(θ), θ_i) ≥ 0$ para todo $i$ y todo $θ$, se denomina individualmente racional. Nos centramos aquí en mecanismos sencillos en forma de juego estratégico $\mathcal{M} = (A_i, g, p)$ donde: * $A_i$ es un conjunto de acciones disponibles para el agente $i$, * $g(a) = o$ es una función de resultado que asigna una acción conjunta $a$ a un resultado $o ∈ \mathcal{O}$, y * $p = p(o)$ es una función de pago que controla las preferencias de los agentes a través de la Eq. [7.2]. Cuando los agentes juegan el juego $\mathcal{M}$, esperamos que elijan una acción conjunta $a^∗(θ) = (a_i^*(θ_i))$ de acuerdo con algún concepto de solución, donde la acción $a^∗(θ_i)$ de un agente $i$ dependerá típicamente de su tipo $θ_i$. Esta acción conjunta se asigna a través de $g$ a un resultado $g(a^∗(θ))$ que queremos que sea igual a $f(θ)$. Como concepto de solución consideraremos lo siguiente: !!!def:Definición Una acción conjunta $a^∗ = (a_i^∗)$ es un equilibrio en acciones dominantes si para cada agente $i$ se cumple que \begin{equation} \label{7.3} u_i(a_{-i}, a^∗) ≥ u_i(a_{-i}, a_i) \end{equation} para todas las acciones conjuntas $(a_{-i}, a_i)$. Nuestra elección de tal concepto de solución está motivada por el hecho de que queremos diseñar un mecanismo en el que cada agente $i$ pueda calcular su acción óptima $a_i^∗$ sin tener que preocuparse de las acciones de los demás agentes. En términos de poder predictivo para las soluciones de un juego, un equilibrio $a^∗ = (a_i^∗)$ en acciones dominantes es más débil que un equilibrio de Nash y que un equilibrio calculado por eliminación iterada de acciones estrictamente dominadas (véase el capítulo 3). Sin embargo, en el contexto del diseño de mecanismos, la existencia de tal equilibrio garantiza que cada agente (racional) se adherirá a él, incluso si no tiene información sobre la elección de acción de los otros agentes. Esta solución de equilibrio también es muy atractiva desde el punto de vista computacional, porque un agente ya no necesita tener en cuenta las acciones de los demás agentes. En resumen, el problema del diseño de mecanismos puede definirse como sigue: !!!def: Definición (problema de diseño de mecanismos) Dado un conjunto de resultados $o ∈ \mathcal{O}$, un perfil de funciones de valoración $ν_i(o, θ_i)$ parametrizado por $θ_i$, y una función de elección social $f(θ)$, el **problema de diseño de mecanismos** plantea econtrar: * conjuntos de acciones apropiadas $A_i$, * una función de resultado $g(a) = o$, y * una función de pago $p(o)$, tal que para cualquier perfil $θ = (θ_i)$, y para funciones de pago $u_i(o, θ_i)$ definidas a través de la Eq. [7. 2], se cumple que $$g(a^∗(θ)) = f(θ)$$ donde $a^∗(θ) = (a_i^∗(θ_i))$ es una solución de equilibrio en acciones dominantes del juego estratégico $\mathcal{M} = (A_i, g, p)$. En este caso decimos que **el mecanismo $\mathcal{M}$ implementa la función de elección social $f$ en acciones dominantes**. !!!Ejemplo: Subasta de Segundo Precio Consideremos el siguiente problema de diseño de mecanismos (una subasta): Tenemos $n$ agentes y un bien (por ejemplo, un recurso en una red informática). Queremos asignar el artículo al agente que más lo valore, pero desconocemos las valoraciones reales de los agentes. En este ejemplo, el tipo $θ_i$ de un agente es su valoración, con $θ_i ∈ \mathbb{R}^+$, y un resultado $o ∈ \{1, \dots, n\}$ es el índice del agente al que se asigna el artículo. La función de valoración de un agente $i$ con tipo $i$ es $$ν_i(o, θ_i) = \begin{cases} θ_i & \text{si } o = i \\ 0 & \text{e.o.c} \end{cases}$$ La función de elección social es $f(θ_1, \dots, θ_n) = \arg \max_i \{θ_i\}$ (nótese que se trata de una versión simplificada de la Eq. [7.1]). Si no incluimos una función de pago, es decir $p_i(o) = 0$ para todo $i$, entonces un mecanismo $\mathcal{M}_1 = (A_i, g, 0)$ que implemente $f$ es siempre individualmente racional porque para un agente $i$ se tiene que $u_i(o, θ_i) = ν_i(o, θ_i) = θ_i ≥ 0$. Supongamos ahora que incorporamos una función de pago $p(o)$ tal que el agente que recibe el artículo debe pagar un impuesto (pago negativo) igual a la segunda valoración más alta, mientras que los demás agentes no tienen que pagar nada. En este caso, la función de pago de un agente $i$ con valoración $θ_i$ es igual a $$u_i(o, θ_i) = \begin{cases} θ_i - \max_{j\neq i} \{θ_j\} & \text{si } o = i \\ 0 & \text{e.o.c} \end{cases}$$ Un mecanismo $\mathcal{M}_2 = (A_i, g, p)$ con tal función de pago $p$ que implemente $f$ sigue siendo individualmente racional porque para el agente ganador $k$ se tiene que $$u_k(k, θ_k) = θ_k - \max_{j\neq k} \{θ_j\} = \max_j \{θ_j\} - \max_{j\neq k} \{θ_j\} ≥ 0$$ mientras que para los demás agentes $j \neq k$ se tiene que $u_j(k, θ_j ) = 0$. # El principio de revelación Si nos fijamos en la definición del problema de diseño de mecanismos, su resolución parece una tarea formidable. En principio, nuestras opciones de diseño pueden incluir todos los conjuntos de acciones posibles $A_i$, todas las funciones de resultados posibles $g$ y todos los tipos de pagos $p$ que podríamos proporcionar a los agentes. Buscar en el espacio de todos los $\mathcal{M} = (A_i, g, p)$ un mecanismo que implemente $f$ sería inviable. Afortunadamente, existe un teorema que nos dice que no necesitamos buscar en el espacio de todos los mecanismos posibles. !!!teorema:Proposición (Principio de revelación) Si una función de elección social $f$ es implementable en acciones dominantes por un mecanismo $\mathcal{M} = (A_i, g, p)$, entonces $f$ también es implementable en acciones dominantes por el mecanismo $\mathcal{M}' = (Θ_i, f, p)$ donde simplemente se pide a cada agente que informe de su tipo. Además, la acción dominante del agente $i$ en $\mathcal{M}'$ es informar de su verdadero tipo $θ_i$. !!!demo:Demostración Supongamos que decir la verdad no es una acción dominante en $\mathcal{M}'$. Entonces debe existir un perfil de tipos declarados $\tilde{θ} = (θ_i)$ para el que \begin{equation} \label{7.4} u_i(f(\tilde{θ}_{-i}, \tilde{θ}_i), θ_i) > u_i(f(\tilde{θ}_{-i}, θ_i), θ_i) \end{equation} Si $f$ es implementable por $\mathcal{M}$ en acciones dominantes, entonces $f(θ) = g(a^∗(θ))$ para todo $θ$, donde $a^∗(θ) = (a_i^∗(θ_i))$ es un equilibrio en acciones dominantes en $\mathcal{M}$. Por lo tanto, podemos reescribir la Eq. [7.4] como \begin{equation} \label{7.5} u_i(g(a_{-1}^∗(\tilde{θ}_{-i}), a_i^∗(\tilde{θ}_i)), θ_i) > u_i(g(a_{-i}^∗(\tilde{θ}_{-i}), a_i^∗(θ_i)), θ_i) \end{equation} lo que contradice el hecho de que $a_i^∗(θ_i)$ es una acción dominante en $\mathcal{M}$. Así pues, el perfil de tipos verdaderos $θ = (θ_i)$ debe ser un equilibrio en acciones dominantes en $\mathcal{M}'$, de lo que se deduce directamente que $\mathcal{M}'$ implementa $f$. Un mecanismo de la forma $\mathcal{M} = (Θ_i, f, p)$ en el que se pide a cada agente que informe de su tipo se denomina **mecanismo de revelación directa**. Un mecanismo de revelación directa en el que decir la verdad es la acción dominante para cada agente se denomina a **prueba de estrategia**. El principio de revelación es notable porque nos permite restringir nuestra atención únicamente a los mecanismos a prueba de estrategia. Una de sus consecuencias, por ejemplo, es que si no podemos implementar una función de elección social mediante un mecanismo a prueba de estrategia, entonces no hay forma de implementar esta función en acciones dominantes mediante ningún otro mecanismo general. El principio de revelación ha demostrado ser una potente herramienta teórica para establecer varios resultados de posibilidad e imposibilidad en el diseño de mecanismos (por ejemplo, [#Parkes2001]). !!!Ejemplo: Subasta de Puja Cerrada de Segundo Precio (Vickrey) Volvamos al ejemplo de la subasta y consideremos un mecanismo de revelación directa $\mathcal{M}_3(Θ_i, f, p)$ con $p$ como en $\mathcal{M}_2$. En otras palabras, se pide a cada agente que puje un precio, y el artículo se asigna al agente con la puja más alta, pero tiene que pagar la segunda puja más alta. Demostraremos que en el mecanismo $\mathcal{M}_3$ decir la verdad es una acción dominante para cada agente, es decir, cada agente debe pujar su valoración verdadera. Sea $b_i(θ_i)$ la puja del agente $i$ dado que su valoración verdadera es $θ_i$, y $b' = \max_{j\neq i} \{b_j(θ_j)\}$ la puja más alta entre todos los demás agentes. La retribución del agente $i$ es $$u_i(o, θ_i) = \begin{cases} θ_i - b' & \text{si } b_i(θ_i) > b' \\ 0 & \text{e.o.c} \end{cases}$$ Ignorando los empates, si $b' < θ_i$ entonces cualquier puja $b_i(θ_i) > b'$ es óptima (resulta en una retribución positiva $u_i(i, θ_i) = θ_i - b' > 0$). Si $b' > θ_i$, cualquier puja $b_i(θ_i) < b'$ es óptima (da lugar a una ganancia no negativa). Decir la verdadera oferta $b_i(θ_i) = θ_i$ es óptimo en ambos casos, y por lo tanto es una acción dominante en $\mathcal{M}_3$. # El mecanismo Groves-Clarke La subasta de pujas cerradas de segundo precio que vimos anteriormente implementa la función de elección social $f(θ_1, \dots, θ_n) = \arg \max_i \{θ_i\}$ que puede considerarse como un caso especial de la función de elección social asignativamente eficiente de la Eq. [7.1]. Volvamos ahora al caso más general. Supongamos un mecanismo directo en el que se pide a los agentes que informen de sus tipos, y basándose en sus informes $\tilde{θ} = (\tilde{θ}_i)$ el mecanismo calcula un resultado óptimo $f(\tilde{θ})$ que resuelve: \begin{equation} \label{7.6} f (\tilde{θ}) = \arg \max_{o\in \mathcal{O}} \sum_{i=1}^n ν_i(o, \tilde{θ}_i) \end{equation} En un mecanismo de Groves, la función de pago asociada al resultado $f(\tilde{θ})$ se define para cada agente como \begin{equation} \label{7.7} p_i(f(\tilde{θ})) = \sum_{j\neq i} ν_j(f(\tilde{θ}), \tilde{θ}_j) — h_i(\tilde{θ}_{—i}) \end{equation} para una función arbitraria $h_i(\tilde{θ}_{-i})$ que no depende del informe del agente $i$. En este caso, y para unos pagos dados por la Eq. [7.2], podemos demostrar lo siguiente (la prueba se deja como ejercicio): !!!teorema:Proposición Un mecanismo de Groves es un mecanismo a prueba de estrategias. Teniendo la libertad de elegir cualquier función $h_i(\tilde{θ}_{-i})$, el mecanismo de Clarke utiliza \begin{equation} \label{7.8} h_i(\tilde{θ}_{-i}) = \sum_{j\neq i} ν_j(f'(\tilde{θ}_{-i}), \tilde{θ}_j) \end{equation} donde $f'(\tilde{θ}_{-i})$ es una función de elección social asignativamente eficiente con el agente $i$ excluido: \begin{equation} \label{7.9} f'(θ) = \arg \max_{o\in \mathcal{O}} \sum_{j\neq i} ν_j(o, θ_j) \end{equation} En condiciones bastante generales, puede demostrarse que el mecanismo de Clarke es individualmente racional. Además, en algunas aplicaciones los pagos $p_i$ a los agentes son negativos, por lo que el mecanismo no necesita ser subvencionado externamente (sin embargo, el impuesto recaudado debe quemarse). !!!Ejemplo: Camino más corto Este es un ejemplo clásico con muchas aplicaciones, que se basa en el mecanismo de Groves-Clarke. Queremos calcular el camino más corto entre dos nodos fijos de un grafo. Cada arista $i$ del grafo tiene un coste (longitud) $θ_i ≥ 0$, y es operada por un agente (por ejemplo, una empresa de transportes) que preferiblemente se quedaría fuera del camino. No conocemos de antemano el coste de cada arista, y queremos diseñar un mecanismo directo en el que cada agente informe de su coste real. Traducido al lenguaje del diseño de mecanismos, un resultado $o$ es una lista ordenada de índices de agentes (las aristas que se incluyen en el camino más corto); el agente $i$ tiene tipo $θ_i$ (el coste de su arista), y función de valoración $$ν_i(o, θ_i) = \begin{cases} -θ_i & \text{si } i\in o \\ 0 & \text{e.o.c} \end{cases}$$ y la función de elección social $f(\tilde{θ})$ es un algoritmo (por ejemplo, Dijkstra) que resuelve Eq. [7.6] (calcula el camino más corto dados los costes comunicados). Un mecanismo de Clarke resuelve el problema anterior proporcionando pagos distintos de cero a todos los agentes $i$ que están incluidos en una solución de camino más corto. Estos pagos se calculan a partir de la Eq. [7.7] y la Eq. [7.8]: \begin{equation} \label{7.10} p_i(f(\tilde{θ})) = \sum_{j\neq i} ν_j(f(\tilde{θ}), \tilde{θ}_j) — \sum_{j\neq i} ν_j(f'(\tilde{θ}_{—i}), \tilde{θ}_j ) = \tilde{θ}_i — C + C' \end{equation} donde $C$ es el coste aditivo (longitud) de la solución del camino más corto, y $C'$ es la longitud de la solución del camino más corto después de eliminar la arista $i$ del grafo. A partir de Eq. [7.2] y Eq. [7.10], la recompensa del agente $i$ al decir la verdad es $u_i = -θ_i + θ_i - C + C'$, que siempre es no negativa, ya que eliminar una arista de un grafo nunca puede generar un camino más corto. Por lo tanto, es individualmente racional que un agente participe en este mecanismo, y como los mecanismos de Groves-Clarke son a prueba de estrategias, cada agente informará gustosamente de su verdadero coste. ## Notas y lecturas adicionales Nuestra exposición se basa en parte en [#Osborne1994] (cap. 10), [#Parkes2001] (cap. 2), [#Nisan1999] y [#Sandholm1999]. Los trabajos de Vickrey [#Vickrey1961], [#Clarke1971] y [#Groves1973] son fundamentales. El principio de revelación se debe a Gibbard [#Gibbard1973]. Nisan [#Nisan1999], Parkes [#Parkes2001] y Papadimitriou [#Papadimitriou2001] analizan los problemas computacionales del diseño de mecanismos. Este último escribe: _Todos los problemas de diseño [en informática] son ahora problemas de diseño de mecanismos_. (#) Bibliografía [#Clarke1971]: Clarke, E. H. (1971). Multipart pricing of public goods. Public choice, 11:17–33. [#Gibbard1973]: Gibbard, A. (1973). Manipulation of voting schemes: a general result. Econometrica, 41:587–601. [#Groves1973]: Groves, T. (1973). Incentives in teams. Econometrica, 41:617–631. [#Nisan1999]: Nisan, N. (1999). Algorithms for selfish agents. In Proc. 16th Symp. on Theoret. Aspects of Computer Science, Trier, Germany. [#Osborne1994]: Osborne, M. J. and Rubinstein, A. (1994). A Course in Game Theory. MIT Press. [#Papadimitriou2001]: Papadimitriou, C. H. (2001). Algorithms, games, and the Internet. In Proc. 33rd Ann. ACM Symp. on Theory of Computing, Crete, Greece. [#Parkes2001]: Parkes, D. C. (2001). Iterative Combinatorial Auctions: Achieving Economic and Computational Efficiency. PhD thesis, Computer and Information Science, University of Pennsylvania. [#Sandholm1999]: Sandholm, T. (1999). Distributed rational decision making. In Weiss, G., editor, Multiagent Systems: A Modern Introduction to Distributed Artificial Intelligence, pages 201–258. MIT Press. [#Vickrey1961]: Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8–37.