Shapley y Roth

Si solamente se pudieran mencionar dos publicaciones, se podría decir que la labor que ha generado los Nobel de Economía de 2012 (Shapley y Roth) comienza en 1962, con un artículo que publica L. S. Shapley con D. Gale (ya fallecido) en The American Mathematical Montly, y termina más de dos décadas más tarde, en 1984, cuando Alvin E. Roth publica un artículo en el Journal of Political Economy. Sobre la base de dichos dos artículos, a continuación se trata de mostrar que Shapley y Roth reciben el Nobel por un juego (porque aplican la teoría de juegos) respecto al diseño (porque en algunos casos las cosas no funcionan sin diseñar un procedimiento, el algoritmo) de mercados (porque hay que ajustar, por ejemplo, médicos con plazas de hospitales en el tema de los MIR) sin que el precio (la clave básica de los mercados) se pueda utilizar para el logro de tal fin. De ahí que reciban el Nobel por el juego de diseñar mercados sin precios.

SHAPLEY Y ROTH: EL JUEGO DE DISEÑAR MERCADOS SIN RPECIOS.

Por Cándido Pañeda, catedrático de Economía Aplicada de la Universidad de Oviedo

Shapley
El artículo de Gale y Shapley se titula “La admisión en los colegios y la estabilidad del matrimonio” y su objetivo es asignar recursos (plazas en los colegios, pareja en un matrimonio) de una forma “estable” y “óptima”.

La “estabilidad” la definen negativamente: sería la ausencia de “inestabilidad”, que, a su vez y en el caso de los colegios, se define como aquella asignación en la que “… hay dos solicitantes a y b que se asignan, respectivamente, a los colegios A y B, aunque b prefiera A respecto a B y A prefiera b respecto a a”. Esto es, cuando hay inestabilidad, lo que se recibe no es lo que se prefiere y, lógicamente, en ese caso la gente no está contenta y se mueve, con lo que la situación es inestable.

Como ya se ha señalado, el segundo objetivo que pretenden lograr en dicha asignación es que sea “óptima”. Y una asignación (que ya es estable) será “óptima” si, siguiendo con el caso de los colegios, “cada solicitante está, como mínimo, tan bien en ella como en cualquier otra asignación estable” (dicho de otra manera, no se puede estar mejor –lo cual no significa que uno esté contento).

A continuación, nos centraremos en el caso más sencillo (el del matrimonio) y veremos la pregunta que se hacían en dicho artículo Gale y Shapley: ¿para cualquier patrón de preferencias, es posible encontrar un conjunto estable de matrimonios? El problema lo resuelven en clave de teoría de juegos y con los datos expuestos en el cuadro adjunto.

ABC
a1,32,23,1
b3,11,32,2
c2,23,11,3

En el eje horizontal están las mujeres (A, B y C) y en el eje vertical están los hombres (a, b y c). Los dos números incluidos en cada una de las celdas del cuadro indican las preferencias de los hombres (el primero) y de las mujeres (el segundo). Así, “1, 3” en el cruce de aA significa que el hombre a sitúa a la mujer A en la primera posición y que la mujer A sitúa al hombre a en la tercera posición. Hay seis posibles conjuntos de matrimonios, pero sólo tres son estables. Uno de los estables es el que le da a cada hombre su primera elección (a se casa con A, b con B y c con C). Es importante resaltar el hecho de que dichos matrimonios son estables, a pesar de que las mujeres se casan con su peor elección (el tercero que elegirían). Otro de los estables es el contrario del anterior: en este caso la persona que elige es la mujer y, de nuevo, opta por su primera elección. El resultado es que A se casa con b, B con c y C con a), que también es estable, pero muy diferente del anterior, ya que en este caso son los hombres los que se casan con su peor elección. La tercera y última posibilidad es que cada persona (hombre o mujer) opte por su segunda elección (el resultado sería también estable y llevaría a que a se casara con B, b se casara con C y c se casara con A).

El teorema que obtienen Gale y Shapley de este análisis es que existe siempre un conjunto estable de matrimonios. Para demostrarlo, exponen el procedimiento iterativo que han utilizado para lograr dicho resultado. Este se basa en la aceptación diferida e incluye en este caso dos pasos (para no complicar la exposición, se expone el caso de las propuestas realizadas por uno de los dos intervinientes, concretamente, el hombre):

Primero, Cada hombre propone a su mujer favorita. Si la mujer elegida recibe más de una propuesta, elije a su hombre favorito y rechaza a los demás, pero deja en suspenso (difiere en definitiva) la comunicación de la aceptación del hombre elegido.

Segundo, Los hombres que han sido rechazados proponen ahora a la mujer correspondiente a su segunda elección. De nuevo, las mujeres propuestas elijen a su hombre favorito y rechazan a los demás, pero difieren la comunicación de la aceptación del hombre elegido.

Gale y Shapley terminan su artículo señalando que son conscientes de que “al plantear las hipótesis especiales necesarias para analizar el problema matemáticamente, se han ido muy lejos del problema original… Sin embargo, pensamos que algunas de las ideas introducidas aquí podrían aplicarse útilmente a ciertas fases del problema de admisión”. Pues bien, veinte años más tarde de su publicación no parecía que fuera a “aplicarse útilmente”, pero en eso llegó Alvin E. Roth, el otro premiado con el Nobel de Economía de este año.

Roth
El artículo seleccionado de Roth (“La evolución del mercado de trabajo para los médicos internos y residentes: un estudio del caso en clave de teoría de juegos”) se publica, como ya se ha señalado, en 1984. El artículo se inicia con el marco institucional de los MIR en Estados Unidos, país en el que en el momento en el que inicia su relato había menos solicitantes que plazas. Este desajuste llevó a que los hospitales compitieran entre sí por los internos, entre otras formas, realizando los acuerdos con los solicitantes muy pronto, para adelantarse a los hospitales competidores. Ello llevó al peor de los mundos posibles: “esto fue visto como costoso e ineficiente, tanto por los hospitales, que tenían que nombrar internos sin conocer sus calificaciones finales, como por los estudiantes y las facultades de medicina, que se encontraban con que gran parte del último año de la carrera estaba perturbado por el proceso de buscar nombramientos deseables”. Todo esto ya estaba pasando, como mínimo, en los años 20 y el desfase entre la fecha de selección y de entrada de los MIR aumentó posteriormente (en 1944 el nombramiento se realizaba dos años antes de que empezara el internado), con lo que el problema del desfase entre el nombramiento y la incorporación a la plaza se agravó todavía más. A las alturas de 1950, estaba claro que el problema no se resolvía acortando dicho desfase y de ahí que se plantearan cambiar hacia un sistema más centralizado: se mantuvieron los intercambios de información entre los solicitantes y los hospitales (que, en todo caso, no negociaban las cuestiones relacionadas con los salarios, con lo que los precios –en este caso del trabajo- no realizaban su labor en dicho ajuste), pero posteriormente (y esta era la novedad) “los estudiantes clasificarían en orden de preferencia los programas de los hospitales a los que realizaban la solicitud y, de manera similar, los hospitales clasificarían a sus solicitantes, y todas las partes someterían sus clasificaciones a una oficina central, que utilizaría dicha información para vincular a los estudiantes con los hospitales y para informar a las partes del resultado”. Este procedimiento se puso en marcha en 1951 y se afinó en 1953, en lo que se denominó el “algoritmo NIMP” (de National Intern Matching Program”, Programa Nacional de Ajuste de Internos). Pues bien, “el plan de ajuste basado en el algoritmo NIMP se continúa usando hasta la fecha” (esto es lo que señala Roth en su artículo, que, como ya se ha señalado, se publica en 1984). Esto era muy importante, pues “esta longevidad y los muy elevados niveles de participación (voluntaria) que el sistema ha generado son particularmente sorprendentes si se tienen en cuenta las agitaciones existentes en este mercado en los años inmediatamente previos al establecimiento del NIMP”. Es decir, hubo un antes (de ineficiencia e inestabilidad) y un después (de más eficiencia y total estabilidad) tras el diseño del mercado de los MIR vía el Programa de Ajuste de Internos.

Roth estudia el caso de los MIR en detalle y en la página 11 de su artículo nos da la sorpresa: “Estos resultados respecto a la existencia fueron señalados por primera vez por Gale y Shapley (1962), quienes no eran conscientes del procedimiento del NIMP, que había estado funcionando durante diez años. Para probar sus resultados respecto a la existencia, desarrollaron un algoritmo que es considerablemente más sencillo que el algoritmo del NIMP pero que resulta ser equivalente, esto es, para un determinado perfil de preferencias estrictas, los dos algoritmos producen los mismos resultados estables”. En definitiva, sin que nadie (ni los gestores de los hospitales ni Gale y Shapley) lo supiera, resulta que Gale y Shapley tenían razón: “algunas de las ideas introducidas aquí podrían aplicarse útilmente a ciertas fases del problema de admisión”. La gracia está en que el algoritmo que plantearon teóricamente Gale y Shapley en 1962 ya se había estado aplicando (sin ningún tipo de teoría, en un proceso de búsqueda práctica de la estabilidad) desde 1951-1953 y que nadie se enteró de dicha “aplicación útil” hasta que Roth la resaltó en su artículo de 1984.

LNE, domingo, 11 de noviembre de 2012.

¿Te ha resultado interesante? ¡Compártelo!