Teoría de Colas

Cotidianamente, hay muchas situaciones en las que lamentablemente se tiene que perder el tiempo haciendo cola para poder ser atendido. Situaciones tales como hacer cola en un peaje para efectuar el pago correspondiente, hacer cola en un supermercado para cancelar en caja por los productos deseados; en una computadora, un programa tiene que esperar para efectuar su labor, porque el procesador está atendiendo otras tareas; en internet, no se puede acceder a una página web, porque el servidor está atendiendo peticiones de otros usuarios, y entonces hay que esperar hasta que se reduzca la cantidad de peticiones; en un negocio de lavado de carros, la carga de trabajo y la cantidad de recursos atendiendo, determinan en cuánto tiempo te podrán atender. La pregunta es ¿por qué ocurren las colas? Ocurren porque la demanda del servicio supera la capacidad de atención de quienes brindan dicho servicio (para decirlo de modo simple, por ahora). Se dice que en promedio las personas pasan cinco años de sus vidas haciendo colas.

El hecho de hacer colas no ha aparecido de súbito en los tiempos modernos debido a la conglomeración de personas en las ciudades, para nada. Toda la vida han existido colas; frente a esto, cada civilización le buscó soluciones empíricas y medianamente efectivas para atenuar la problemática que afrontaban. De hecho, inclusive se puede afirmar que las personas están casi acostumbradas a hacer cola para recibir atención. Felizmente han surgido estudiosos decididos a enfrentar este problema de manera científica.

La teoría de colas o, como se conoció en un principio, Teletráfico en ingeniería de Telecomunicaciones (A.K. Erlang, 1909), lanza su primera publicación llamada La teoría de probabilidades y las conversaciones Telefónicas. Erlang, por aquel entonces era empleado de una compañía telefónica y tenía asignada la tarea de recomendar el número de líneas de atención, tomando en cuenta la frecuencia y duración de las llamadas. Si bien es cierto que éste fue el comienzo del estudio de la teoría de colas, no fue sino hasta los años 50 que empezaron a difundirse gran cantidad de trabajos relacionados a Teoría de colas en diversos campos.

La teoría de colas, a través de modelos, permite representar comportamientos en los cuales el factor común es el tráfico que se genera, y presenta los aspectos que originan que se generen estas colas y la manera de afrontarlas. Hay características que cumplen todos los sistemas de colas, empezando con (a) El patrón de llegada, el cual en la vida real es aleatoria, es decir, a la cola no llegan clientes cada x tiempo exacto, a veces llegan solos, a veces en grupo, hay que tomar en cuenta también que algunos clientes se cansarán de esperar en la cola y terminarán retirándose, lo cual añade más variables a tener en cuenta al realizar el cálculo de servidores. (b) El número de personas en la cola, para este caso se toma en cuenta el estilo con el cual se ordenan las colas: en la mayoría de casos la atención se realizará tomando en cuenta el orden de llegada, es decir, se atiende a quien llega primero, en otros casos, se formarán varias colas dando preferencia a ciertos clientes, basándose en criterios tomados en cuenta. (c) El número de personas que están siendo atendidas. (d) El tiempo que se invierte esperando en la cola. (e) El tiempo que se invierte siendo atendidos. (f) La capacidad del sistema, toma en cuenta la posibilidad de desbordamiento de las colas por exceso de clientes aglomerados esperando su turno de ser atendidos. (g) El número de servidores, la capacidad de múltiples servidores ante una única cola es una característica importante, éstos tienen demostrado mejor rendimiento antes que aquellos sistemas donde se hacen múltiples colas, cada uno con su propio servidor, lo cual da la posibilidad de tiempos flojos de algunos servidores, mientras que colapsos en otros.

Independientemente de lo optimizado y bien elaborado que pueda estar, un sistema de colas puede ser tan complejo como lo requiera el servicio, puede funcionar mediante una sola etapa o puede ser multietapas, es decir, puede necesitar pasar por varias colas para completar el servicio. El pago de peaje es un sistema de una etapa: se hace la cola para pagar, no hay más. Caso diferente es el servicio de lavado de autos: es un sistema de múltiples etapas: se hace una cola inicial para pagar por adelantado el servicio, luego viene la cola para el aspirado del carro, luego la cola para el ansiado lavado del carro, finalmente hay que dirigirse a otra cola para el secado.

¿Cómo sabemos si en un negocio los clientes están siendo bien atendidos? ¿Cómo se mide el rendimiento de un sistema? Básicamente se deben establecer métricas para detectar la calidad del sistema o, en todo caso, diseñar un nuevo sistema que cumpla los requisitos para ser óptimo. El costo de implantar un nuevo sistema debería permitir la recuperación de dicha inversión, mediante el servicio que se brinda. Para lograr esto, es necesario que se analicen fuertemente y se obtenga información de tres tipos principalmente: ¿Cuánto es el tiempo de espera de los clientes? ¿Cuál es la cantidad de clientes esperando? ¿Cuál es el tiempo ocioso de quienes atienden?

Para responder estas preguntas, es necesario recopilar información. La forma de recopilar esta información es importante, antes que registrar información cada cierto período de tiempo, es recomendable capturarla mediante eventos que se suscitan en el momento, es decir, se registra la información cada vez que ocurre. Por ejemplo, registrar cada cuánto tiempo llega un cliente y cuánto tiempo tardan en atender a este cliente. La mayoría de modelos aceptan que el tiempo entre llegada de clientes sigue el flujo de una distribución de Poisson. También se acepta que el flujo de atención de los clientes, cuando quienes atienden están ocupados, sigue una distribución de Poisson y el tiempo que dura la atención, sigue una distribución exponencial.

Sin embargo, debemos precisar que no siempre se solucionan los procesos con distribuciones de Poisson o exponenciales, algunos procesos funcionan mejor con otras distribuciones. Para trabajar con la distribución adecuada, es requisito conocer a plenitud cada una de ellas, lo cual nos abre un abanico de oportunidades y de aprovechamiento; asimismo, igual de importante es conocer el procedimiento para determinar cuál es la distribución que se ajusta a cada situación.

Empecemos conociendo la notación de Kendall, que permite reconocer características de un modelo simplemente analizando las letras que la conforman. La estructura general es la siguiente: A/B/X/Y/Z/V; donde A representa la distribución de llegadas y puede tomar los valores: M, para distribuciones exponenciales; D, para distribuciones determinísticas y G, para llegadas generales; B refiere a la distribución de servicio, y puede tener las mismas distribuciones que A; X representa la cantidad de servidores; Y representa el número máximo de clientes que puede soportar el sistema, si es infinita no es necesario mencionarla; Z es la disciplina, de igual forma se omitirá si es FIFO.

A continuación se hará un repaso por los diferentes modelos de colas simples: (a) El modelo de cola simple, también conocido como M/M/1, este esquema trabaja bajo un único servidor y tanto la tasa de llegada como la de servicio siguen la distribución de Poisson. (b) El modelo de colas en paralelo o M/M/C, es el esquema bajo el cual más de un servidor atiende a los clientes con la misma calidad. (c) Modelo de cola con servidores en paralelo y límite de capacidad o M/M/c/K, útil para los casos en los que no se puede atender a todos los clientes. En la nomenclatura, el límite de atención es representado por K. (d) El modelo de Erlang o M/M/C/C, esta distribución atiende casos en los que la cola de clientes debe coincidir con el número de servidores, en otras palabras: nunca debe existir cola en la atención. Funciona independientemente de la distribución usada en el servicio. (e) Modelo de cola sin límite de servidores o M/M/∞, especialmente útil para situaciones en las que el número de servidores no tenga que tener un límite, por ejemplo en los casos en que los clientes acceden a internet. (f) Modelo de colas con límite en la fuente, para casos en los que la cola tiene un número finito de clientes. (g) Modelo de colas con impaciencia, para los casos en los cuales los clientes se integran a la cola sólo si ésta no está saturada, o si les alcanza el tiempo para esperar. (h) Colas que no siguen el modelo de Poisson o Exponencial o G/G/c, para casos por ejemplo del modelo M/G/1, donde los clientes aún llegan con una distribución de Poisson, pero son atendidos mediante un proceso más general.

Finalmente, se han analizado modelos para representar cualquier situación que involucre hacer cola. Con estos modelos, es posible determinar la capacidad de servicio que necesita un sistema para atender eficazmente a sus clientes. Como es de esperarse, no es una tarea fácil, pero es más barato simular un sistema que hacer cambios en el sistema sin saber si solucionará los problemas. Los resultados que brinda la teoría de colas se aplican en todos los ámbitos, sea transportes, telecomunicaciones, negocios de diversas índoles, comercio, industria, etc. Por ejemplo en el trabajo final se demostró la utilidad de aplicar la teoría de colas a un negocio de lavado de carros, el cual inicialmente, al poseer sólo 6 servidores en la sección de secado de carros, originaba que se congestione el negocio, y los tiempos de atención rápidos que se ganaban en las primeras etapas, se pierdan por el retraso en el secado.

Al incrementar en tres servidores más se demuestra la eficiencia que esto arroja, al lograr una utilización de mano de obra superior de 89.16%, lo cual antes era de 73.04%, lográndose una mejor atención y un mejor aprovechamiento de los recursos que participaban en el proceso de lavado de carros.

Equilibrio de Nash

¿Alguna vez, antes de tomar una decisión, ha analizado si saldrá airoso ante la incierta respuesta de un contrincante? De repente sí, lo cierto es que siempre se debiera proceder analizando posibles respuestas. Inclusive los juegos simples que conocemos, demuestran que detrás existe toda una estrategia basada en las decisiones de los demás hagan y que influirá en el desenlace de la competencia. Pero esta lucha de estrategias se repite en la vida real, en situaciones económicas, donde ya no es un juego, lo cual la hace importante para el análisis económico.

Están los juegos cooperativos, donde los jugadores pueden comunicarse entre ellos, negociar los resultados y que las ganancias se repartan entre los jugadores. También destacan los juegos no cooperativos, donde se prohíbe negociar entre jugadores, en este grupo tenemos el juego «el dilema del prisionero», donde las estrategias deben decidirse dependiendo de la elección del otro jugador.

El «dilema del prisionero», consiste en la situación de dos delincuentes con una pena de 10 años de cárcel. Sólo se les puede inculpar de un delito menor, cuyo castigo es de 2 años de cárcel. Se les ofrece la alternativa de reducir su pena si acusan al otro. Para esto, ellos no pueden comunicarse entre sí. Las alternativas de decisión de los presos son: acusar o permanecer en silencio, y los posibles resultados son 4, en base a lo que decidan. Una de las opciones es traicionar, la cual pareciera la alternativa más gananciosa.

El dilema del prisionero inclusive permite evaluar el comportamiento de empresas rivales en un mercado de oligopolio, ya que los resultados de cada una dependerán de lo que hagan las demás, resultando un choque de estrategias. Ya desde hace mucho, los economistas empezaron a elaborar modelos para estudiar el juego de estrategias. Estos estudios brindaban una buena lectura de la realidad, evaluando casos como cuando unas pocas empresas dominan un mercado o cuando varios países tienen que establecer acuerdos sobre política comercial o cuando en el mercado de trabajo las partes tienen que negociar los salarios. En estos casos la teoría de juegos es la precisa para entender estas realidades.

Si analizamos un mercado oligopólico, donde los resultados que obtiene cada una dependen no sólo de su comportamiento sino del comportamiento de las demás. El problema para las empresas, por tanto, implica una elección estratégica que tenga en cuenta el posible comportamiento de las demás. El funcionamiento de estos mercados puede ser modelado con la teoría de juegos.

Nash, muy joven todavía, pudo encontrar una solución al problema de negociación entre dos agentes asumiendo que la utilidad es no transferible, mientras que, como hemos apuntado, antes se asumía que la utilidad era transferible.

Su mayor aportación fue el desarrollo de una definición de equilibrio general en todos los juegos de horizonte finito para un número cualquiera de jugadores. Este concepto de equilibrio, es lo que hoy en día se conoce como Equilibrio de Nash, por la que obtuvo el Premio Nobel.

Para dar esta definición, Nash tomó los juegos en forma normal y modeló un proceso de negociación entre personas como un juego simple, donde cada agente elige su estrategia óptima. Es así que propuso dos interpretaciones para entender la definición de su equilibrio: una, basada en la racionalidad de los participantes y la otra, en el comportamiento estadístico de poblaciones. La primera interpretación establece que cada jugador puede calcular los pagos esperados de cada una de las posibles estrategias de sus contrincantes y ver cuál es la estrategia óptima de los otros jugadores. Si todos los agentes hacen lo mismo, todos esperan el mismo equilibrio de Nash y ninguno tiene incentivos a desviarse y jugar otra estrategia distinta.

Además de aportar un nuevo concepto de equilibrio en los juegos de negociación en forma normal, Nash demostró, aplicando el teorema del punto fijo de Kakutani, que todos los juegos con un número finito de jugadores y un espacio de estrategias finito para cada jugador,

tienen al menos un equilibrio de Nash en estrategias mixtas, resultado conocido como el Teorema de Nash.

Nash también aportó un buen número de ejemplos económicos interesantes de problemas de teoría de juegos, en un trabajo publicado en 1951 en Annals of Mathematics, bajo el nombre de «Noncooperative Games», y que recoge buena parte de su tesis doctoral. En este trabajo, Nash incluye un juego con múltiples equilibrios, (como el de la batalla de los sexos), otro juego con un equilibrio que es Pareto ineficiente (como el dilema del prisionero), y un juego con un equilibrio inestable.

Dos aspectos que sobresalen en este trabajo y que Nash hace notar son que elimina dos restricciones que se imponían en la literatura previa: la utilidad transferible y que los juegos fueran de suma cero. Nash, en su último trabajo establece una aplicación donde transforma un proceso de negociación entre dos personas en un juego simple de demandas simultáneas. La principal aportación de este estudio es que Nash es capaz de transformar un juego cooperativo, con múltiples equilibrios de Nash, en otro no cooperativo, donde el autor da un argumento que determina un único equilibrio estable.

La argumentación que dio Nash en esta aplicación anticiparía un poco lo que serían los refinamientos del equilibrio de Nash (el equilibrio perfecto en subjuegos, el equilibrio correlacionado, etc.), que se desarrollarían más tarde, como respuesta al problema de que algunos juegos tienen varios equilibrios de Nash, y es difícil predecir el resultado del juego. Nash marcó un antes y un después en la teoría de juegos. Este autor utilizó su teoría en juegos no cooperativos bajo supuestos de información completa, un entorno estático y basándose en la forma normal de Von Neumann. Los estudios posteriores a Nash tomaron como punto de referencia su concepto de equilibrio y su metodología, pero introduciendo nuevas condiciones en los problemas que se plantean.

La primera desviación del marco genérico que creó Nash, fue la que surgió al considerar juegos dinámicos, es decir juegos que se repiten un número finito o infinito de veces, manteniendo el resto de condiciones, es decir, agentes plenamente racionales e información completa. A la hora de estudiar este tipo de juegos dinámicos aparecieron las limitaciones de la forma normal de Von Newman, lo que llevó a un estudio más profundo

de la forma extensiva, llevada a cabo por Kuhn en sus trabajos de 1950 y 1953. Aunque los juegos de decisiones sucesivas pueden representarse bajo la forma normal, los aspectos dinámicos del juego resultan más fáciles de analizar si se representan en forma extensiva.

Son ejemplos clásicos de juegos dinámicos el modelo de Stackelberg (1934) o el modelo de negociación de Rubinstein (1982). El problema de algunos juegos dinámicos es que incorporan muchos equilibrios de Nash, alguno de los cuales se basa en promesas o amenazas no creíbles, que resultan irracionales cuando se analizan en forma extensiva. Reinhard Selten (1965) analizó este problema y, como respuesta, desarrolló el primer refinamiento del concepto del equilibrio de Nash: el equilibrio de Nash perfecto en subjuegos. Este concepto de equilibrio permite obtener los equilibrios de Nash, para juegos tanto en forma normal como en forma extensiva, que pasan la prueba de la credibilidad.

La segunda desviación del marco teórico de Nash, fue desarrollada por Harsanyi (1967, 1968), quien consideró juegos de información incompleta, o lo que es lo mismo, juegos donde existen asimetrías de información entre los jugadores, y que pueden ser considerados en un marco estático o dinámico. A este tipo de juegos de información imperfecta, se les denomina «juegos bayesianos» y se caracterizan porque al menos un agente no conoce la función de pagos de los otros agentes.

Para resolver este problema, Harsanyi estableció que el agente que no conoce las ganancias de otro agente, tiene ciertas expectativas de que ese agente sea de un tipo u otro/s. De esta forma, dicho agente asigna probabilidades a cada uno de los posibles tipos de contrincante, caracterizados por las funciones de ganancias esperadas. Harsanyi

fue capaz de dar respuesta a estos juegos en un entorno estático, refinando de nuevo el equilibrio de Nash, y definiendo el concepto de equilibrio bayesiano de Nash. Un claro ejemplo de un juego bayesiano estático es el tipo de juegos que se producen en las subastas de sobre cerrado. En este tipo de subastas los agentes conocen sus propias valoraciones de los bienes, pero no conocen las de los demás. De esta forma cuando escriben su apuesta en el sobre cerrado, es decir, cuando tiene lugar el juego, ningún agente sabe cuáles son las valoraciones del bien de los otros.

Como hemos dicho, los juegos bayesianos pueden ser estáticos y dinámicos. Para resolver los juegos bayesianos en un entorno dinámico se refinó el concepto de equilibrio bayesiano, desarrollándose el concepto de equilibrio bayesiano de Nash perfecto en subjuegos, y estableciendo una similitud equivalente a la del equilibrio de Nash perfecto en subjuegos para juegos estáticos con información completa. David Kreps y Robert

Wilson (1982) aportaron el aspecto crucial del equilibrio bayesiano perfecto en subjuegos: formalmente el equilibrio no solo viene caracterizado por una estrategia para cada jugador, sino también se incluyen unas creencias para cada jugador en cada conjunto de información en el que el jugador tenga que jugar. Estos dos autores definieron el equilibrio secuencial, un concepto de equilibrio equivalente al equilibrio bayesiano perfecto en muchas aplicaciones económicas, pero en algunas otras es un concepto más restrictivo.

Precisamente, los ejemplos económicos más interesantes tienen lugar para juegos bayesianos que se desarrollan en un entorno dinámico y se aplican fundamentalmente en los juegos de señalización. Los juegos de señalización sirven para describir problemas económicos reales y su literatura comienza con el modelo de Spence (1973) que se produce entre un trabajador y un empresario. El trabajador tiene una información privada sobre su productividad, que el empresario desconoce, con lo cual es necesario que el trabajador emita una señal que, en este caso será la educación, para indicar su tipo. Según la señal emitida,

el empresario elige una determinada acción, que será el nivel salarial pagado al trabajador.

Es indudable la importancia del equilibrio de Nash en los últimos tiempos y es que estamos ante un instrumento muy útil a la hora de predecir el comportamiento de los agentes. Otros dicen que el equilibrio de Nash en concreto y, en general, el marco metodológico de la teoría de juegos, debería utilizarse como herramienta para evaluar teorías en todas las ciencias sociales.