Bienvenidos al lado oscuro de las matemáticas...
Los dos primeros items se pueden ver en el clásico paper de Gale y Shapley, College Admissions and the Stability of Marriage, American Mathematical Monthly 69, 9-14, 1962 (de algunos links se puede bajar gratis).
El algoritmo resuelve el problema de los matrimonios estables: dados dos conjuntos, de Varones y Mujeres (de igual cardinal, pero no es problema), donde cada varón tiene una lista de las mujeres ordenadas según a cuál prefiere más (y cada mujer tiene una lista con los varones), existe una biyección tal que no queden v y m que prefieran estar en pareja entre sí antes que con sus respectivos compañeros. Una situación así llevaría a divorciar la pareja y por eso la asignación no sería estable.
Hay una variante maquiavélica, donde algunos de los V pueden mentir, no revelando sus preferencias verdaderas. Si hay un solo mentiroso, le va peor, pero si son varios, puede ser que algunos mejoren y el resto no quede peor!
Con el matrimonio gay, el problema se conoce como el roommate problem, pero no hay caso: puede no existir ninguna asignación estable. El mejor ejemplo se tiene con cuatro participantes a, b, c, y d y sus preferencias son las siguientes:
a los ordena: b > c > d
b los ordena: c > a > d
c los ordena: a > b > d
d los ordena: a > b > c
Armen dos parejas cualesquiera, y verán que el resultado no es estable. Por ejemplo, si agrupamos (a, d) y (b, c), tenemos que c preferiría estar con a antes que con su actual pareja b; y a preferiría estar con c antes que con su actual pareja d. Luego, tienden a divorciarse y formar la pareja (a,c)
Pero esta también tiene el mismo problema, como pueden verificar muy rápido.
Finalmente, el último resultado es el nunca bien ponderado Teorema de Arrow. La demostración que dí es prácticamente la de Geanakoplos (con ligeros cambios, se puede ver en la Wikipedia).
Como se dijo en 1972, cuando le dieron el Nobel:
En su tesis doctoral, publicada en 1951, Arrow planteó la siguiente cuestión. Supongamos que en una sociedad uno tiene un número de alternativas entre las que elegir, y que cada individuo de la sociedad ordena las alternativas en el orden que las prefiere. ¿Es posible, en ese caso, hallar una regla democrática y éticamente aceptable que produzca un ranking colectivo (o social) de las distintas alternativas? Arrow mostró que la respuesta es negativa. En principio, es imposible hallar una regla semejante.
Existen distintas extensiones de este teorema, entre ellas la de Nakamura, o la más impactante de Gibbard y Satterthwaite: ni siquiera se puede elegir un único ganador, entre los distintos candidatos, a menos que:
Según cómo siga la semana, tal vez demuestre aquí el Teorema de Arrow, pero tengo que resolver cómo hacer dibujitos, que con un par la demostración queda más clara.
Mi colaboración para el Carnaval de Matemáticas, esta vez a cargo de Los Matemáticos no son gente seria.
