Teoría De Juegos

INTRODUCCION

Este articulo traza la propuesta hecha para el proyecto de grado titulado: “Utilización De La Computación Evolutiva y la Teoría de Juegos Para la Automatización en Sistemas de Soporte a la Negociación”. Los problemas de negociación son por excelencia no algorítmicos y las conclusiones a este tipo de problemas se obtienen luego de un proceso dispendioso y por ende sus resultados difíciles de evaluar, es así, como el modelamiento y soporte al problema de la negociación propone un reto muy interesante a los campos de Ciencia de la Decisión, la Investigación de Operaciones y la Inteligencia Artificial.

La propuesta presentada aquí se enmarca dentro de la denominada: Democracia Electrónica [1], en la cual se pretende implantar un proceso democrático participativo que persigue un acuerdo entre grupos de personas con conflicto de intereses en asuntos concernientes a la sociedad, lo cual hace necesario plantear modelos de negociación bajo los cuales se interactúe para encontrar la solución mas óptima, el soporte que se da a dicho proceso está habilitado por internet. Posteriormente a la experiencias de Portoalegre, hay por ejemplo en Europa diversas municipalidades que permiten a sus ciudadanos participar (parcialmente) en la ejecución de los prepuestos municipales, a estos también se les denomina presupuestos participatorios. Nuestra intención procura utilizar análisis de decisión y de apoyo a la decisión de grupos, desplegado sobre la web, con miras a involucrar al público en las decisiones que les afecta, es así como vemos en Internet una oportunidad de acortar la brecha entre quienes rigen y quienes son regidos.

El problema surge debido a que dichos modelos por lo general se basan en negociaciones multicriterio, es decir, con múltiples variables y por tal razón se recae en un proceso complejo, en el cual el espacio de búsqueda de la solución mas optima es extenso, demandando mucho tiempo e incluso convirtiéndose en un proceso muy tedioso.

ENFOQUE DE LA TEORIA DE JUEGOS

Los agentes racionales son capaces de llegar a acuerdos con un mecanismo de negociación de la teoría de juegos aún sin comunicación, esto ocurre cuando los agentes de forma aislada escogen el punto que ellos consideran es el equilibrio [2][3]. Sin embargo, surgen problemas con los mecanismos de negociación en la teoría de juegos sin comunicación, el primero es que en situaciones parecidas a la del dilema del prisionero los agentes no escogerán el mejor resultado basados en la suposición de racionalidad [4][5]. En segundo lugar aquellos juegos en los cuales no existen puntos de equilibrios, encontraremos ciclos infinitos de razonamiento, aunque estos juegos utilizan el concepto de estrategias mixtas para solucionarse esta no es la mejor opción [5][6]. En tercer lugar cuando encontramos más de un equilibrio es difícil seleccionar el mejor, ya que cada agente puede tender a puntos diferentes según sus objetivos particulares [6].

En el trabajo de S.H. Wu, V.W. Soo [7], se propuso la primera acción de comunicación dentro de la convencional teoría de juegos, pedir garantía, para escapar de situaciones como la del dilema del prisionero. Para los casos en donde no existen equilibrios o hay múltiples equilibrios se propuso la segunda acción de comunicación, pagar compensación. Además, estas acciones de comunicación exigen la existencia de un agente independiente del dominio de negociación, denominado agente TTP (Trusted Third Party, tercera parte confiable) o agente mediador [6].

Luego en [8] se trataron juegos con información incompleta siguiendo la misma filosofía de las acciones de comunicación de garantía y compensación, las cuales convertían un juego difícil en un juego simple. El equilibrio alcanzado por medio de las acciones de comunicación se denomina equilibrio NFD (No Fear of Deviation, sin temor de desviación).

ENFOQUE COEVOLUTIVO

El punto inicial de la metodología co-evolutiva para la negociación es la disponibilidad de un conjunto de estrategias iniciales, las cuales son posteriormente manipuladas para encontrar una solución optimizada para un problema específico. Esto involucra el desarrollo de una función de utilidad para evaluar estrategias, así cada estrategia tendrá asignada un valor único. La función de utilidad usará este valor para determinar el grado de su utilidad como una solución. La generación de una estrategia optimizada o solución involucra la selección de la mejor solución, incluyendo los padres y la creación de descendientes a través de la mutación y el cruzamiento. La próxima generación es seleccionada por medio de un proceso de competencia o torneo. Las soluciones más débiles son removidas desde la población y reemplazadas por las mejores soluciones. Un sistema co-evolutivo será implementado para soportar negociación entre múltiples agentes que puedan manejar varios asuntos. Bajo este esquema, el sistema provee una estrategia general desde la que genera aleatoriamente un número de estrategias específicas que construirán la población inicial. Cada

...