Carlos N. Bouza
Universidad de La Habana

Sira M. Allende
Universidad de La Habana

Este Working Paper se encuentra recogido en DOAJ - Directory of Open Access Journals
http://www.doaj.org/

Abstract         The study of a game could be modelled assuming that only some hands are watched. Then the tree game must be estimated making use of sampling information. It happens the same when we get information about the behaviour of the decisions taken by individual sampled by a tree of theory decision. By considering a probabilistic measurement of cross-section samples we might get an estimatation of the associated tree. This is the problem analysed on this working paper. Some experimental results obtained by using the Recocido Simulado illustrate the procedure. The role at the study of economic and trading models is discussed. Resumen         El estudio de un juego puede ser modelado asumiendo que solo algunas partidas son observadas. Entonces el árbol del juego debe ser estimado utilizando información muestral. Similarmente ocurre al obtener información sobre el comportamiento de las decisiones tomadas por individuos muestreados sobre un árbol de decisión teórico. Al considerar una medida de probabilidad que caracterice el comportamiento de redes aleatorias se puede obtener un estimado del árbol asociado. Este problema es el analizado en este trabajo. Algunos resultados experimentales obtenidos usando Recocido Simulado ilustran el procedimiento. Su papel en el estudio de modelos económicos y de mercadeo es discutido.

1.- Introducción En muchos problemas que son modelados por grafos su estructura es la de un árbol. Al jugar los decisores (jugadores) deben evaluar que estrategias les son más convenientes tras observar algunas partidas . Es decir, que con la información que obtienen determinan un subjuego. Una hipótesis comunmente asumida en la Teoría de Juegos es que se está observando el mismo juego en forma repetida. El problema práctico es más complicado pues generalmente el decisor cuando no sabe si realmente está observando resultados de distintos juegos. Esto puede ser motivado por cambios en las condiciones en que se desarrollan las jugadas, como ocurre en la economía, o en las reglas mismas como sucede en el mercado informal. Entonces el enfoque a utilizar debe basarse en un modelo y caracterizar un juego que no sea muy diferente de aquellos que generaron las observaciones. Denominémosle `juego central´ para utilizar el símil del concepto de `parámetro de tendencia central´que se define en la estadística. Este juego estará caracterizado por un árbol que juega el papel de parámetro de centralidad. Este puede ser estimado asi como una medida del error asociado. En la teoría se establece que un juego siempre puede ser descrito utilizando su Forma Extensiva, ver Hart (1992). Esta forma es apropiada para describir detalladamente juegos estratégicos, ver Oiko-Nomia (1997). Esta forma nos da una descripción detallada del juego fijando exactamente los movimientos, selecciones, movidas y resultados en cada etapa. Un árbol describe la forma extensiva. La teoría usual asume que cada jugador posee habilidades para tomar tomar sus decisiones y que razona logicamente. Por ello todos los jugadores son considerados racionales. En la práctica esto puede ser bien diferente. En una cierta fase los jugadores observan las resultados del juego para aprender, establecer lo que consideran es la estructura del juego y fijar sus propios procedimientos decisionales. Para ello hace inducciones sobre el comportamiento futuro del juego elaborando sus propias reglas de decisión . Así es que ellos observan resultados del juego, subjuegos, y valoran que estrategias les son convenientes. Ellos necesitarán tener un ábol que tipifique la muestra observada. Este árbol de juego debe caracterizar todos los subjuegos observados por el jugador. Usándole evaluará la conveniencia de su estrategia. Similarmente ocurre en los estudios de mercado los que utilizan con gran frecuencia los árboles de decisión. Estos se han ido convirtiendo en un herramienta muy útil para la clasificación y la valoración de como conforman los clientes sus decisiones. En particular la llamada Mineria de Datos (Data Mining), ver Berry-Linoff (1997), le ha dado una gran popularidad dadas por las posibilidades que brinda y la fácil comprensión de sus resultados en investigaciones de mercado. Esto en gran parte está dado por el hecho de que el árbol de decisión determina directamente las reglas de decisión. Note que un médico, al evaluar los síntomas del paciente se mueve en un árbol donde las respuestas de este y los análisis clínicos le van guiando hacia un diagnóstico. El problema usual en estudios de mercado es similar: el investigador construye un cuestionario y los respondentes dan sus respuestas secuencialmente lo que permite hacer un establecer como las preferencias y valoraciones de un tipo de consumidor que le llevan a preferir una acción final (estructura de su canasta) a otra. También el respondente se mueve de nodo en nodo hasta llegar a un nodo terminal, trazando un camino . El interés del gerente le puede llevar a utilizar simplemente los datos de que posee para establecer con que frecuencia los clientes toman una decisión caracterizada por un nodo terminal del árbol. Este es un análisis estadístico del problema. Sin embargo un análisis del árbol de decisión a partir de las muestras permite valorar como es que llegan los clientes a tomar sus decisiones finales. Nuevamente, a partir de observar varios árboles se desea establecer un estimado del `árbol central´. Este trabajo se dedica a estudiar un procedimiento que permite abordar este tipo de problema. En la Sección 2 se discuten los elementos necesarios de la Teoría de Juegos y con ellos los relacionados con la Teoría de Decisión. El problema probabilístico es el tema de la tercera sección en la que se establece como hacer una estimacion del ´árbol central´. Su determinación es posible utilizando un algoritmo de Búsqueda Estocástica. Se propone un algoritmo de Recocido Simulado. Algunos ejemplos son discutidos en la Sección 4. 2.- Elementos de Teoría de Juegos y los Árboles de Decisión Es bien sabido que a cada juego puede asociarse un Juego en Forma Estratégica y que de esta podemos derivar un Juego en Forma Extensiva (JFE) y viceversa. Hart (1992) desarrolla una amplia discusión sobre esta importante relación. La importancia de los JFE para caracterizar el comportamiento de un juego es resaltado en Oiko-Noimia (1997). El enfoque usual de la Teoría de Juegos parte de asumir que la estructura del juego es conocida por todos los jugadores y que estos actúan racionalmente. Kaneko y Kimura (1993) llamaron a estos juegos ´deductivos´ porque las decisiones provienen de un proceso racional. Ellos utilizan su información para deducir que estrategias parecen ser más adecuadas. En estos juegos diferentes interacciones pueden ser representadas. En general son utilizadas una de las tres siguientes formas par representar un juego : -La forma extensiva (FE). -La forma estratégica (FS) -La forma característica (FC) La FE de un juego es una descripción explicíta de este. Cada jugador hace movimientos, toma acciones, de acuerdo a reglas preestablecidas y llega a una cierta situación. Un grafo permite describir el juego. Sus nodos representan las situaciones y las aristas las acciones. En algunos nodos el jugador debe hacer una movida, tomar una acción, y en otros no. Estos últimos son los llamados nodos terminales. El grafo correspondiente es un árbol. En un juego n-personal tenemos un conjunto de jugadores I={1,2,...,n}, un árbol con raíz T y una particición del conjunto de nodos no terminales A0, A1,...,An. El conjunto de nodos Ai se asocia al jugador i de I . A0 representa los nodos de la naturaleza. Ella hace sus movimientos aleatoriamente. Cuando se llega a un nodo terminal el juego termina y un vector n-dimensional de números reales es deteminado. Su coordenada i-ésima es el pago que recibe el jugador i. Entonces la descripción en FE de está dada por: donde A representa el conjunto de situaciones, O a la sucesión en que estas aparecen, (A,O) es el árbol del juego, Por otra parte A* es el conjunto de acciones y la función O* relaciona cada acción con un nodo del árbol. La partición (A1 ,..., An), especifica que jugador se mueve en los nodos correspondientes, U es el conjunto de los conjuntos de información que contienen los nodos de decisión que cada jugador identifica. A(u) es el conjunto de información para un u de U y contiene las posibles selecciones del jugador i al llegar a u. La función g es la que permite determinar el vector de pagos en cada nodo terminal. El marco de la Teoría de Juegos permite estructurar el estudio de distintos problemas sociales. El jugador i determina sus estrategias y/o acciones utilizando la partición de los nodos no terminales de , Ai0 , Ai1 ,..., Ain , que constituye su patrón de información. Este observa algunas realizaciones del juego y del análisis de estos resultados proyecta una política decisional. Como el jugador no puede analizar exhaustivamente el juego las observaciones que hace le permiten conformar una visión de las interacciones existentes en problemas como los económicos, los de las relaciones dentro de un grupo social determinado, etc. En particular el jugador puede estar interesado en evaluar la conveniencia de cooperar con ciertos grupos. Él observará algunas realizaciones del juego para valorar las utilidades de las empresas antes de fijar que acciones comprar. De hecho él no ha observado todas las posibles realizaciones del juego sino solo un subjuego y por tanto lo que puede construir es un subárbol. Aunque el jugador tenga como aspiración conocer como se comporta el juego solo puede observar algunos subjuegos. Su deseo será establecer un subárbol que sea suficientemente representativo del juego en el sentido de que los subjuegos más frecuentemente observados generen árboles similares a este. Tal es el caso cuando va a comprar unos bonos. El observa el mercado durante un tiempo. Las condiciones en que se desarrolla la compra-venta varían, aunque las reglas sean fijas. Tras observar el mercado por un cierto periodo de tiempo determina árboles que quiere caracterizar. En otros casos como los presentes en mercados emergentes o informales las reglas cambian y no son de conocimiento anticipado del jugador (comprador). Tal es el caso en el mercado negro donde las transacciones dependen de factores muy variables como son los riesgos de obtener la mercancia. En estos problemas de naturaleza económica los supuestos, temores y aspiraciones de los agentes (jugadores) tienen una gran influencia en las decisiones. En estas condiciones las hipótesis básicas de los modelos usuales llevan a que el juego observado solo pueda ser estudiado, no conocido, a partir de observar su comportamiento y construir un grafo para analizarle. Buscar un "árbol central" permite que el jugador establezca algunas normativas verosímiles para el fenómeno estudiado. Las estrategias de comportamiento que establezca deben ser adecuadas en un sentido probabilístico. Clásicamente se considera la existencia de racionalidad en los decisores. Por ello se supone que buscan maximizar sus ganancias utilizando algún conocimiento apriorístico. La teoría asociada puede ser denominada Teoría Deductiva de Juegos de acuerdo a la clasificación propuesta por Kaneko y Kimura (1997). Ella parte de que los jugadores juegan a partir de sus deduccciones. El proceso de razonamiento será correcto solo si la hipótesis de racionalidad es válida. Sin embargo cuando se desea aprender que ocurre, como en los casos en que influyen interacciones sociales, estas no son aceptables. Por ello el observador lo que puede es evaluar resultados determinando los árboles generados. El investigador lo que desea es inferir sobre el mecanismo que genera los juegos observados. El desenvolvimiento de una sociedad puede ser caracterizado al analizar la correspondiente sucesión de árboles . Tal es el caso en estudios sobre la transformación de comportamientos y deseos en problemas de mercadeo. Este es un problema que está recibiendo una creciente atención que ha estimulado el desarrollo de estudios sobre los llamados Juegos Bayesianos . En ellos se busca fijar un equilibrio respecto a ciertas aspiraciones de los jugadores. Vea, para una introducción a estos temas Selten (1991) y para una discusión más profunda Oiko-Moima (1998). Este tipo de juego son de la clase llamada Juegos Adaptativos de Aprendizaje Evolutivo. Otra mirada a la Teoría de Juegos lleva al análisis del proceso inductivo de la toma de decisión. Kaneko y Kimura (1992) consideraron los casos en que los jugadores no tienen suieciente conocimiento apriorístico para hacer deducciones. Entonces, a partir de las observaciones que haga de una serie de jugadas selecciona una estrategia usando una representación de las relaciones sociales. Estos son de los denominados Juegos Inductivos. Note en que todos los casos podemos suponer que el decisor suple su desconocimiento del fenómeno con observaciones aleatorias del mismo. Estas son las partidas. En cada partida un camino es fijado y al terminar su observación se determina un subárbol aleatorio formado por estos recorridos. En una muestra varios subárboles son obtenidos. El interés es establecer un subárbol que sea verosimílmente parecido a los observados. Consideremos el estudio de un árbol de decisión que representa las respuestas a diversas preguntas. Las respuestas establecen un movimiento entre nodos en dos niveles. Al llegar al final del cuestionario, un nodo final, el entrevistado ha trazado un camino y puede ser clasificado en una cierta categoria. Esto es ha cobrado gran importancia en estudios de mercado, vea Berry y Linoff (1997). Cada camino establece de hecho una regla de decision. El deseo del investigador de mercado generalmente es establecer que reglas son más frecuentemente utilizadas aunque en ocasiones lo importante sea detectar comportamientos poco frecuentes. Conociéndo las reglas que utilizan los clientes se puede particularizar la oferta y dirigir, por ejemplo, las publicidad al nicho de mercado caracterizado por ciertas reglas. Un problema clásico es el de establecer cuáles son los caminos más frecuentes. Así el gerente del supermercado puede detectar que "ver el partido de fútbol, quedarse el fin de semana en casa, comprar cervezas" es muy popular a partir de una cierta edad. La propaganda televisiva de las empresas cerveceras puede establecer las líneas de sus anuncios en esta línea, el gerente puede hacer ofertas de paquetes que abaraten el precio de cervezas pero incluyendo la compra de en un paquete con pasabocas, etc. En la práctica el especialista al hacer la investigación de las operaciones analiza el problema y construye un árbol teórico donde están todas los recorridos posibles. Para conocer el comportamiento real de la población toma una muestra y evalúa a los seleccionados. Algunos de los posibles caminos serán más populares. La evaluación de la frecuencia con que se arriba a los nodos finales permite hacer un análisis estadístico de la frecuencia. A veces el interés es detectar comportamiento, camino utilizado, más que la decisión final. Por ejemplo al dueño de un restaurante le puede interesar precisamente el comportamiento de los comensales posibles y no sñólo su selección final. Estos seleccionan con mucha frecuencia un cierto restaurante pero al competidor le interesa el proceso seguido, camino, para seleccionarle. Esto es lo que permitirá establecer en que sentido debe mejorar la oferta para incrementar su clientela. En la práctica al hacer estas investigaciones habrá varios árboles generados por las muestras observadas. Nuevamente nos interesa determinar un árbol que sea ´representativo´ de los observados para estudiarle. Por tanto nuevamente el determinar un árbol "verosímil" será de utilidad para el estudio. 3.- Computación de un Àrbol Máximo Verosímil. Denotemos por el conjunto de todos los árboles posibles. Consideremos que el grafo sin aristas pertenece a este conjunto así como el grafo completo. Un muestra de m árboles s es seleccionada de . Asumimos que ellos son generados por un mecanismo aleatorio. Las relaciones entre pares de árboles pueden ser medidos por una métrica Asumamos que el mecanismo que genera los árboles observados es caracterizado por una medida de probabilidad µ y que utilizándola podemos computar la probabilidad de observar un cierto árbol t cuando el verdadero árbol es t°. Banks y Carley (1994) analizaron diversos procedimientos para derivar aproximaciones convenientes para los modelos estocásticos que generan redes sociales. En su trabajo utilizaron los resultados de Mallows(1957), para derivar una medida de probabilidad definida sobre el conjunto de permutaciones. Utilizándola tenemos que Nos provee de un adecuado modelo probabilístico. Tomemos a t° como el árbol que representa a un parámetro de tendencia central, y como una medida de escala, que nos permite definir a K() como una constante normalizadora, independiente d t° . D es una métrica cualquiera. Por facilidades de cálculo utilizaremos la métrica es el estimador Máximo Verosímil (MV) del árbol de tendencia central. El problema está en su computación. Aún para valores moderados de n y m el tiempo de cómputo necesario puede ser grande. El uso de un Algoritmo de Búsqueda Estocástica provee de una solución adecuada utilizando tiempos razonables de cálculo. Entre las heurísticas la de Recocido Simulado es una de las más eficientes. Vea Pflug (1996) y Vidal [1993] para una discusión de los aspectos prinipales de la teoría y comportamiento práctico de estos algoritmos. Una descripción del algoritmos de Recocido Simulado que utilizamos para determinar t* es la siguiente: Algoritmo de Recocido Simulado par generar el Árbol Máximo Verosímil Inicializar Computar el grafo unión Para h=1 hasta Lk Seleccionar aleatoriamente un i{1,...,n} y un p{1,...,m} mediante una Uniforme. Recalcular cambiando ai0 por aih en t0 Computar Fijar Lk t*=t0 END Los parámetros que deben fijarse son: - El parámetro de enfriamiento . Experiencias prácticas recomiendan utilizar como valor a B Máx{|(t´)-(t´´)|} : para todo par de árboles observados t´y t´´} /log k B es una cota superior del número de pasos necesarios para obtener un minimizador global. El requerido análisis estadístico requiere del cómputo de un estimador MV de un parámetro de escala. Este es la función de t*: Entonces cada decisor puede evaluar sus estrategias y aspiraciones utilizando t* como lo hace con la media o la mediana en los problemas estadísticos clásicos. Algunos ejemplos permiten ilustrar como estas ideas funcionan en la práctica modelando problemas usuales. Ejemplo 1: El jugador analiza el vector de pagos [g1 (*),...,gn ( *)], donde * es un nodo terminal del árbol MV antes de tomar una decisión. Para ello considera varios juegos y analiza una muestra de árboles de juego para computar t*. Sea el conjunto de los nodos de este juego : t*(). Si el agente estuviera evaluando formar parte de una coalición una decisión racional es unirse a S si Ejemplo 2. Un jugador determina su distribución a priori Fi . La evaluará computando en * el conjunto de posibles perfiles . Entonces si hi es el verdadero tipo de jugador i y el jugador obtiene Podemos decir que * es una estimación del equilibrio Bayesiano siempre que En general el jugador está interesado en la evaluación de una función Suponiendo que esta es una aplicación del conjunto de todos los juegos en un intervalo abierto de , como t* es un estimador MV, entonces, como resultado directo del Teorema 5.11 en Zacks (1971), (t*) también es un estimador MV. Siguiendo esta línea de razonamiento el jugador puede hacer inferencias sobre la función característica (S) de un juego con pagos marginales. 4.- Algunos Ejemplos. El algoritmo fue utilizado para evaluar algunos juegos simples. Estos nos dan una idea de su funcionamiento. Utilizamos m=3, K=5 y =0,1 en la simulación y como parámetros del algoritmo de Recocido Simulado. La descripción de cada juego, el árbol teórico, los subárboles observados y el árbol MV son dadas a continuación. La FE, los resultados de la simulación y el árbol MV se brindan en las figuras correspondientes. Ejemplo 4.1. Cada jugador lanza una moneda. En este caso I={1,2}, raíz=a y ={a}. Ejemplo 4.2. Tomemos el juego descrito por I={1,2,3}, raíz=a, A11={a}, A12={e,f}, A21={b,c}, A31={g}. Ejemplo 4.3 (Kuhn, 1953). El juego consiste de dos jugadores. El jugador 1 es una pareja, Alice y Bill. El otro es otra persona llamada Zeno. Se seleccionan dos cartas aleatoriamente por ambos jugadores. Una está marcada con una H ( High) y la otra con una L (Low). El jugador con H recibe $1 del contrincante. El ganador puede decidir no continuar o seguirlo haciendo. Si el juego continua Bill, sin conocer el resultado recomienda sin deben cambiarse las cartas de Alice y Zeno o no. Nuevamente el ganador obtiene $1. Ejemplo 4.4. (Shubik, 1981). Considere un mercado duoplista simple donde la selección se debe hacer entre tres niveles de producción simultáneamente. Los niveles de producción determinan los resultados del mercado y los pagos. Ejemplo 4.5 (Festival Game, Kaneko-Shimura, 1992.). Sea el conjunto de jugadores I={ 1,2,...,5} , particionado en dos grupos. Los miembros dentro de cad auno son ´homogéneos´ pero los grupos son muy diferentes. Cada jugador selecciona un sitio del festival. Ellos analizan la composición grupal de este y toma una decisión (actitud) respecto al lugar: considera amistoso o no el ambiente. Sean los grupos G1={1,2,3} y G2= {4,5}. 5.- Conclusiones El uso de la información obtenida en muchos problemas de decisión pueden ser modelables mediante árboles. La observación de varias realizaciones requiere de hacer inferencias utilizando información incompleta. Si las observaciones se consideran provenientes de una muestra aleatoria es posible hacer inferencias al computar un árbol MV. Si no lo fuese los métodos descritos permiten obtener un árbol para hacer un análisis descriptivo. El algoritmo propuesto es de fácil implementación usando paquetes como MatLab. Reconocimientos: Una versión preliminar de este trabajo fue expuesta en la conferencia `Approximation and Optimization in the Caribbean´ celebrado en Pointe-a-Pitre, Guadalupe en 1999. Su culminación se efectuó mientras uno de los autores hacía una estancia en la Humboldt Universität zu Berlin soportada por una Beca otorgada por el DAAD. References Berry, M. J. A., & Linoff, G. (1997). Data Mining Techniques. J. Wiley. Banks, D., & Carley, K. (1994). Metric inference for social networks. J. of Classification, 11,121-149. Guilboa, I., & Schemeider, D. (1995). Case-based decision theory. Quart. J. of Economics, 605-639. Hart, S. (1992). Games in extensive and strategic forms. In "Handbook of Game Theory with Economic Applications", Vol I, [R.J.Aumann and S. Hart , eds] 19-40, N. Holland, Amsterdam. Kaneko, M., & Shimura, T. (1992). Conventions, social prejudices and discrimination: a festival game with merrymakers. Games and Economic Behavior. 4, 511-527. Kuhn, H. W. (1952). Extensive games and the problem of information. In "Contributions to the Theory of Games", Vol II. Annals of Mathematical Studies 28, (H.W. Kuhn, and A. W. Tucker, eds), University Press, 193-216. Mallows, C. (1957). Non null ranking models I. Biometrika 44, 114-130. Oiko-Nomia. (1997). Games with incomplete information. CERSEM, Universi\´te Paris I. Oiko-Nomia. (1998). Games in extensive form. CERSEM, Universi\´te Paris I. Pflug, G. Ch. (1996). Optimization of Stochastic Models. The interface between Simulation and Optimization. Kluwer Academic. Publishers. Boston. Selten, R. (1991). Evolution, learning and economical behavior. Games and Economic Behavior, 3, 3-24. Shubik. (1981). Game theory models and methods in political economic. In "Handbook of Mathematical Economics", Vol I. (K.J. Arrow and M.D. Intrilligator, Eds.) N. Holland, Amsterdam. Vidal, R.V.V. (1993). Applied Simulation Annealing. Lectures Notes in Economics and Math. Systems, 396, Springer, Berlin. Zacks, S. (1971). The Theory of Statistical Inference. Wiley, N. York. About the Authors Sira M. Allende y Carlos N. Bouza Departamento de Matemática Aplicada Facultad de Matemática y Computación Universidad de La Habana. San Lázaro y L. Habana CP 10 400. Cuba E-mail: sira@matcom.uh.cu y bouza@matcom.uh.cu

DOCUMENTOS DE TRABAJO EN ANÁLISIS ECONÓMICO (EAWP)
Derechos reservados 2002. El permiso para reproducir algún artículo está garantizado si Documentos de Trabajo en Análisis Económico lo acredita, las copias no son vendidas y es en acto de mayor difusión del documento.

Editor: Fernando González-Laxe. (Universidade da Coruña)
Director: Venancio Salcines. (Universidade da Coruña)
Subdirector: Andrés Blancas. Instituto de Investigaciones Económicas (UNAM)
Editor Asociado para America Latina: Luis Miguel Galindo. Facultad de Ecomomía (UNAM)