<strong>Algoritmo de aceptación diferida matricial</strong><a id="back_fn2" class="xref_id"></a><a href="#fn2" class="xref_href"><sup><strong>*</strong></sup></a>
Resumen:

En este artículo damos una versión matricial del algoritmo de aceptación diferida para el modelo de asignación (matching) uno a uno. El algoritmo va modificando la matriz de preferencia de los agentes. Cuando el algoritmo se detiene se muestra que coincide con una asignación estable óptima de los agentes.

Abstract:

In this paper we give matrix version of the deferred-acceptance algorithm for the matching model one to one. The new algorithm modifies the matrix of the agents preference. When the algorithm stops, it is shown that coincides with an agent optimal-stable matching.

Palabras clave:
    • modelo de asignación uno a uno;
    • asignación estable;
    • algoritmo de aceptación diferida;
    • matriz de preferencia.
Clasificación JEL:
    • C78;
    • D71;
    • D78.

Introducción

En este artículo se da una versión matricial del algoritmo de aceptación diferida para el modelo de asignación (matching) uno a uno.

Este modelo se usa para estudiar problemas de asignación bilateral, es decir cuando los agentes se dividen en dos conjuntos disjuntos, el conjunto de empresas y el conjunto de trabajadores. El problema consiste en asignar a cada empresa un trabajador. Este problema de asignación se puede generalizar si se le permite a cada empresa con tratar a un conjunto de trabajadores y a cada trabajador trabajar para varias empresas. Este modelo se lo conoce como modelo de asignación muchos a muchos; también hay un modelo intermedio de asignación, conocido como muchos a uno. La generalización de los resultados en general no son inmediatas.

Cada empresa tiene preferencias respecto a los potenciales trabajadores y simétricamente los trabajadores tienen preferencias respecto a las empresas para las cuales quisieran trabajar. Una solución de este problema de asignación es una asignación, que establece que compañero le toca a cada agente. Una asignación es estable si a cada agente le toca un compañero aceptable y si no existe un par de agentes empresa-trabajador que ambos prefieran asociarse mejorando en sus preferencias al compañero que le tocaba en la solución propuesta. Gale y Shapley (1962) mostraron que en el modelo de asignación uno a uno el conjunto de asignaciones estables es no vacío. Roth y Sotomayor (1990) y Gusfield e Irving (1986) son una importante referencia para estudiar los modelos de asignación. El conjunto de asignaciones estables está bien estructurado ya que contiene dos asignaciones: la óptima de las empresas (denotada por μF) y la óptima de los trabajadores (denotada por μW). Las asignaciones μF y μW son consideradas unánimemente por todas las empresas como la mejor y la peor entre todas las asignaciones estables; simétricamente μW y μF son consideradas por los trabajadores como la mejor y la peor de las asignaciones estables. Blair (1988) mostró que el conjunto de asignaciones estables tiene estructura de latís.

Los algoritmos han desempeñado un papel central en la bibliografía de la asignación. El algoritmo NIMP (Programa de médicos internos nacionales) de 1951, y posteriores modificaciones NRMP (Programa de médicos residentes nacionales) de 1979, 1987 1999 se usan para asignar a hospitales médicos residentes en los Estados Unidos. El algoritmo de aceptación diferida de Gale y Shapley se usa en otros programas de asignación de distintas especialidades de la salud a hospitales. Además del algoritmo de aceptación diferida de Gale y Shapley, Adachi (2000) usó técnicas de punto fijo para construir asignaciones estables. Fleiner (2001) y Echenique y Oviedo (2004) extendieron de punto fijo al modelo de asignación muchos a uno para construir asignaciones estables.

McVitie y Wilson (1971) e Irving y Leather (1986) definieron un algoritmo para computar el conjunto de todas las asignaciones estables en el modelo de asignación uno a uno. Martínez, Massó, Neme y Oviedo (2004) extendieron el algoritmo al modelo de asignación muchos a muchos.

El algoritmo que presentamos aquí es una versión del algoritmo de aceptación diferida en forma matricial. Para esto construimos dos matrices, MF y MW. La primera contiene en cada fila la infor mación del orden de preferencias de las empresas, asignándole un 1 al trabajador más preferido, 2 al siguiente en su orden de preferencia y así continua; la segunda matriz, contiene en forma simétrica en cada columna la información del orden de preferencias de los trabajadores, asigna un 1 a la empresa más preferida, 2 a la que sigue y así continúa. El algoritmo va modificando la matriz MF: primero ubica todos los 1, es decir, cada empresa ubica al trabajador más preferido; si en alguna columna hay más de un 1, ese trabajador cálcula, usando MW, el mínimo, o sea, el trabajador elige la oferta más preferida. Redefinimos la matriz MF asignándole ∞ a la fila (empresa) donde hay un 1 y columna (trabajador) que no es mínimo, es decir, para el trabajador esa empresa no es la más preferida. En los otros elementos de la fila le restamos 1, es decir, el trabajador que era segundo, en el orden de preferencia original, ahora tendrá un 1, es decir, es el trabajador más preferido; el tercero en el orden de preferencias original ahora será el 2, y así continúa. Se ubican nuevamente los 1 de la matriz modificada MF y se repite el proceso anterior. El algoritmo se detiene cuando no podemos modificar más M F. Ubicando los 1 de MF tenemos qué trabajador (si es que hay uno) le toca a cada empresa. Mostramos que esta asignación coincide con la óptima μF de las empresas.

Esta artículo esta organizado como sigue. En la sección I damos las definiciones y notaciones preliminares. La sección II contiene el algoritmo y el resultado principal que muestra que cuando el algoritmo se detiene, los 1 de MF nos dan la asignación estable óptima μF de las empresas.

I. Definiciones básicas

Hay dos conjuntos finitos y disjuntos de agentes F y W, F = { f1, f2, ... , fn } es el conjunto de empresas y W ={w1, w2, ... , wp} es el conjunto de trabajadores. Cada agente gFW tiene una relación de preferencias P(g) estricta, transitiva y completa respecto a los agentes del otro conjunto unido a él; por ejemplo:

dice que la empresa f tiene a w1 como el trabajador más preferido, luego sigue en orden w3 , w5 , f, w4 y w2. Los trabajadores w son tales que wP( f ) f se dice que son aceptables. fP( f )w4 significa que este trabajador no es aceptable para la empresa f. Tenemos que los trabajadores w1, w3 y w5, son aceptables para la empresa f, mientras que w4 y w2 son inaceptables para f. Para expresar el orden anterior de manera concisa, debido a que los agentes no están obligados a contratar o ser contratados por un agente no aceptable, denotaremos en el orden de preferencias sólo a los agentes aceptables, es decir, el orden anterior se denota por:

Un perfil de preferencias es de (n + p) -upla de relaciones de preferencias y lo representamos por P = (P( f1), ... P( fn), P(w1), ... P(wp)). R denota el orden débil asociado a P.

Un modelo de asignación uno a uno se denota por (F , W, P).

Definición 1. Una asignación μ es una aplicación uno a uno de FW en FW , en que para todo fF y wW se cumple que:

  • i) μ( f ) ≠ f implica μ( f ) ∈ W,

  • ii) μ(w) ≠ w implica μ(w) ∈ F ,

  • iii) w = μ( f ) si y sólo si f = μ( w).

Una asignación representada por

en este caso μ(f1) = w2 , μ( f2 ) = w4 , μ( f3 ) = w1, μ( f4 ) = w3 y μ( w5 ) = w5. La asignación μ es individualmente racional si para todo agente gFW

es decir que la asignación le asigna a cada agente un compañero aceptable. El par de agentes (f , w) bloquea a la asignación μ si μ( f ) ≠ w y

esto muestra que tanto f como w quieren romper la asignación μ para formar una nueva asignación emparejándose entre ellos.

Las asignaciones individualmente racionales que sobrevivan a bloqueos por pares de agentes, desempeñan un papel fundamental en los modelos de asignación, ya que no podrán modificarse, porque en caso de hacerlo algún o algunos de los agentes intervinientes quedarán con un compañero menos preferido que los que le asignaba la asignación original, formalmente:

Definición 2. Una asignación m es estable si es individualmente racional y no es bloqueado por ningún par de agentes.

Sea P un perfil de preferencias, y S(P) denota el conjunto de asignaciones estables.

El ejemplo siguiente muestra las definiciones dadas hasta aquí:

Ejemplo 1. Sea el siguiente modelo de asignación (F, W, P), en que F ={ f1, f2 , f3 , f4}, W ={w1, w2 , w3},

Consideremos las asignaciones siguientes

La asignación μ1 no es individualmente racional, porque w1 P(w1) f4 = μ1 (w1). μ2 es individualmente racional pero es inestable ya que ( f1, w2 ) es un par bloqueante. μ3 es una asignación estable.

El orden de preferencia P(g) de un agente, se puede extender para que pueda comparar las asignaciones. Sea gFW, decimos que

Decimos que

y

De manera análoga se define μP(W )μ’ y μR(W) μ’. En el ejemplo anterior tenemos que μ3 P(F) μ2.

Gale y Shapley (1962) mostraron que el conjunto de asignaciones estables es distinto del vacío. También mostraron que existe la asignación estable μFW) que es la mejor a las asignaciones estables para las empresas (trabajadores). Además el óptimo de las asignaciones estables para una parte del mercado es el peor para otra parte, es decir que cada μ ∈ S(P) se cumple que

El algoritmo de aceptación diferida definido por Gale y Shapley (1962) construye μF o μW , dependiendo quien hace las ofertas. En cualquier paso del algoritmo, en el cual las empresas hacen las ofertas, una empresa se propone al mejor trabajador de su orden de preferencia que no la ha rechazado aún, mientras que un trabajador acepta, provisionalmente, a la mejor empresa aceptable que le hizo una oferta (si la hubiera) unido con la empresa provisionalmente aceptada en un paso anterior. El algoritmo se detiene en cualquier paso en el cual todas las ofertas son aceptadas; la asignación provisional que se forma con las propuestas aceptadas se torna definitiva. El resultado del algoritmo es la asignación estable μF. Simétricamente si los trabajadores hacen las ofertas el resultado del algoritmo es la asignación estable μW.

Ejemplo 1 (continuación). Tenemos que μF = μ3 y

II. Algoritmo de aceptación diferida matricial

Este algoritmo usa notación matricial. Las filas de la matriz representan a las empresas y las columnas a los trabajadores, así que fijaremos un orden para los agentes. Cuando no haya problemas denotamos con i la fila de la matriz que representa a la empresa fi ; simétricamente la columna j representa al trabajador wj. Dado el modelo de asignación (F, W, P), definimos las siguientes matrices de preferencias MF y MW , sean fiF y wjW

y

Tenemos que el trabajador w j es aceptable para la empresa fi , si m i j F < y que la empresa fi es aceptable para el trabajador wj , cuando m i j W < . La empresa fi y el trabajador wj son mutuamente aceptables cuando m i j F   m i j W < .

Ejemplo 2. Construyamos de las matrices de preferencias MF y MW para F ={f1, f2, f3, f4, f5}, W ={w1, w2, w3, w4} y los ordenes de preferencia

Como w1 P(f1) f1 y |{wj’: wj’ P(f1) w1}| = | | = 0 = k, entonces m 11 F = 1 , similarmente, m 12 F = 2 pues w2 R( f1 ) f1 y |{wj’: wj’ P( f1 ) w2}| = |{w1}| = k =1, y m 13 F = 3 pues w3 R( f1 ) f1 y |{wj’: wj’ P( f1 ) w3}| = |{w1 , w2}| = k = 2. Notemos que m 53 F = pues f5 P(f5) w3. Obtenemos las siguientes matrices de preferencias

Algoritmo. Entrada: MF,0 = MF , y MW matrices de preferencias de los agentes. Salida: Matriz de a lo más un uno por columna.

i) Si para cada j, | { m i j F , t :   m i j F , t = 1 } | ≤ 1, paro // se ha determinado la matriz.

ii) Si no, defino1

Defino t +1 : = t. Regresa a 1.

El algoritmo trabaja de la siguiente manera. Dada la matriz de preferencias de las empresas MF,⋅ , cuenta cuantos 1 tiene en cada columna, si para toda trabajador wj hay a lo más un 1, el algoritmo se detiene, pues se encontró la matriz de salida. Si esto no ocurre se construye una nueva matriz de preferencias para las empresas, de la siguiente manera: sea el trabajador wj , tal que existe una única empresa fi , con m i j F , t = 1 , entonces la fija i, de MF,t+1 no se modifica, es decir, M i , F , t + 1 = M i , F , t . Si para el trabajador wj existen al menos dos empresas fi y fi' , tales que m i j F , t = m i ' j F , t = 1 , sin perdida de generalidad supongamos que m i j W = m i n { m l j W : m l j F , t = 1 } , entonces en este caso la fila i' de MF,t+1 no se modifica, es decir, M i , F , t + 1 = M i , F , t , mientras que la fila i' se modificará por M i ' j F , t + 1 = (notemos que para cada t' ≥ t +1 m i ' j F , t ' = ) y m i ' j ' F , t + 1 = m i ' j ' F , t - 1 para todo wj'wj . Luego hace t +1 = t, y vuelve a 1, a contar cuantos 1 tiene por columna.

Si el algoritmo no para es porque existe wj , tal que | { m i j F , t + 1 : m i j F , t + 1 = 1 } | >1, entonces pasamos a 2, en el que se modificarán ciertas filas en donde la columna wj sea tal que m i ' j W m i n { m l j W : m l j F , t = 1 } . Note que en modificación cambia un 1 por un ∞. Por finitud de las entradas el algoritmo debe parar, es decir existe t - tal para cada j se cumple que:

Supongamos que el algoritmo se detiene en t - , entonces definimos una aplicación μ - de FW en fW por:

Notemos que μ - (fi ) = fi es cuan do en la fila i de M F , t - todos los elementos son ∞, pues si hubiese un elemento menor que ∞ debe existir un trabajador wj' tal que m i j ' F , t - = 1 , ya que por construcción de MF,t+1 el algoritmo le resta 1 en cada posición de la fila o se cambia un 1 por ∞.

Por otra parte, μ - (wj ) = wj , cuando la columna j de M F , t - , no posee ningún 1, es decir el trabajador wj no recibió ninguna propuesta de las empresas aceptables para él.

El ejemplo siguiente muestra el algoritmo para el ejemplo 2.

Ejemplo 2 (continuación). Datos MF, 0 = MF y MW.

i) El algoritmo no para ya que en la columna 1 y 4 hay más de un 1, y ii) dada MF,0 y MW , construimos MF,1

notemos que las filas 3, 4, y 5 se modifican ya que

luego m 34 F , 1 = , y para j'≠ 4, m 34 F , 1 = m 34 F , 1 - 1 . También (1) implica que para todo j =1, 2, 3, 4, m 2 , j F , 1 = m 2 , j F , 0 . Como

la fila 1 de la matriz MF,1 , no se modifica mientras que si lo hacen las filas 4 y 5.

Hacemos t = 1: i) el algoritmo no para ya que en la columna 4 hay dos 1, y ii) dada MF,1 y MW, construimos MF,2

nótese que se modifica la fila 2 ya que

Hacemos t = 2: i) el algoritmo no para ya que la columna 2 tiene dos 1, y ii) dada MF,2 y MW , construimos MF, 3

Hacemos t = 3: i) el algoritmo no para ya que la columna 4 tiene dos 1, y ii) dada MF,3 y MW , construimos MF,4

Hacemos t = 4: el algoritmo se detiene, ya en cada columna hay a lo más un 1. Tenemos que t - = 4.

La asignación que se obtiene a partir de MF,4, es:

Presentamos ahora el resultado principal

Teorema 1. μ - es una asignación estable y μ - = µF

Demostración: Supongamos que el algoritmo para en la t - . Mostremos que μ - es una asignación. De la definición de μ - , se cumple que si μ - (f ) ≠ f, entonces μ - (f) ∈ W y μ - (w) ≠ w, entonces μ - (w) ∈ F. También se cumple que si m i j F , t - = 1 , implica que μ - (fi ) = wj y μ - ( wj ) = fi , por tanto es una asignación.

Veamos que μ - es individualmente racional. Supongamos que μ - (fi ) = wj, entonces m i j F , t - = 1 y m i j W < , por tanto por la definición de MW tenemos que fi P(wj ) wj , el algoritmo implica que si m i j F , t - = 1 , entonces m i j F , 0 = m i j F < y por la definición de MF , wj P(fi) fi.

Mostraremos que μ - no es bloqueado por ningún par de agentes. Supongamos que existe un par de agentes ( fi , wj ) ∈ F × W tal que μ - (fi ) ≠ wj y

es decir que m i j F < m i j ' F , y como m i j ' F , t - = 1 , entonces m i j ' F , t - = , por tanto existe t ^ tal que m i j ' F , t ^ = 1 , por el algoritmo tenemos que

entonces m i ' j W < m i j W (nótese que μ - (wj ) = fi' ), por tanto fi' P( wj ) fi , es decir que ( fi , wj ) no puede bloquear a μ - .

Veamos que μ - = µF . Como μ - S(P) tenemos que µF R(F) μ - R(F) µW. Supongamos que µF μ - , sin pérdida de generalidad sean f1, ... , f i - , tales que µF ( fi ) ≠ μ - ( fi ). Podemos suponer que existen w1, ... , w i - tales que

Para cada i =1, ... , i - , sean ti , li tales que

Tanto ti como li existen, ya que al aplicar el algoritmo se cumple que m i ,   i + 1 F , t - = 1 ,   m i   i F < m i ,   i + 1 F , por tanto en algún paso ti existe li tal que las condiciones (3) son verdaderas. Supongamos que

entonces

notemos que

si ocurre que w1P( f l 1 ) w l 1 entonces ( f l 1 , w1) bloquerían a µF por tanto se cumple que

Supongamos que µF ( f l 1 ) = μ - ( f l 1 ). m l 1 1 F , t 1 = 1 , entonces w1 P( f l 1 ) μ - ( f l 1 ) = µF ( f l 1 ) y la condición (5) implica que ( f l 1 , w1) bloquean a µF . Luego, µF ( f l 1 ) ≠ μ - ( f l 1 ), es decir que µF ( f l 1 ) = w l 1 . Entonces tenemos que t l 1 satisface las condiciones (3), además t l 1 < t1, ya que por (6) tenemos que m l 1 l 1 F < m l 1 1 F . Esto contradice la elección minimal de t1. ▪

Notas al pie:
  • *

    Este artículo fue financiado en parte por UNSL, Proico 319502. Conicet PIP 6293. FONCYT-SECYT, PAV 120/2003. FONCYT, PICT 03-10814.

  • 1

    m i n   m l j ' W :   m l j ' F , t = 1 = si no existe l, j' tal que m l j' F , t = 1

Referencias bibliográficas
  • Adachi, H. (2000), “On a Characterization of Stable Matchings”, Economic Letters, 68, pp. 43.49.
  • Echenique, F., y J. Oviedo (2004), “Core Many-to-one Matchings by Fixed Point Methods”, Journal of Economic Theory 115, pp. 358-376.
  • Fleiner, T. (2003), “A Fixed-Point Approach to Stable Matchings and Some Applications”, Mathematics of Operations Research, 28, pp. 103.126.
  • Gale, D., y L. Shapley (1962), “College Admissions and the Stability of Marriage”, American Mathematical Monthly 69, pp. 9-15.
  • Gusfield, D., y R. Irving (1989), The Stable Marriage Problem: Structure and Algorithms, Cambridge, MIT Press.
  • Irving, R., y P. Leather (1986), “The Complexity of Counting Stable Marriages”, SIAM Journal of Computing 15, pp. 655-667.
  • Martínez, R., J. Massó, A. Neme y J. Oviedo (2004), “An Algorithm to Compute the Full Set of Many-to-Many Stable Matchings”, Mathematical Social Sciences, 47, pp. 187-210.
  • McVitie, D., y L. Wilson (1971), “The Stable Marriage Problem”, Communications of the ACM 14, pp. 486-493.
  • Roth, A., y M. Sotomayor (1990), Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge, Cambridge University Press [Econometrica Society Monographs núm. 18].
Historial:
  • » Publición impresa: 01/2008

Enlaces refback

  • No hay ningún enlace refback.


Revista El Trimestre Económico, volumen LXXXVI (2), número 342, abril-junio de 2019. Es una publicación trimestral que aparece en enero, abril, julio y octubre, editada por el Fondo de Cultura Económica, con domicilio en  Carretera Picacho Ajusco número 227, Col. Bosques del Pedregal, Delegación Tlalpan, C.P.  14738, Ciudad de México, teléfono (55) 5227 4672, ext. 1850, http://www.eltrimestreeconomico.com.mx/. Reserva de derechos al uso exclusivo  Número 04-2016-052612421000-203, ISSN 2448-718X. Ambos otorgados por el Instituto del Derecho de Autor.  Responsable de la última actualización de este número: Nuria Pliego Vinageras, Secretaria Técnica, Fecha de la última actualización:  28 de enero de 2019. La responsabilidad por lo expresado en los artículos, notas y reseñas es  estrictamente de sus autores; en consecuencia El Trimestre Económico, el Fondo de Cultura Económica y las instituciones a las que estén asociados los autores son ajenos a ella. Todos los derechos reservados. Se autoriza la reproducción total o parcial de los artículos  aquí presentados, siempre y cuando no se mutile y se incluya en todos los casos, junto con la ficha completa, el nombre del autor al que se cite y la  dirección electrónica de la revista; de otra forma, requerirá la autorización por escrito de El Trimestre Económico.