18.11.10

1594.- El lado oscuro de las matematicas - CdM VIII

Si ayer no me iniciaron juicio académico para echarme de la universidad, tuve mucha suerte. Y es que en la clase demostré tres resultaditos pesados:

  • Demostré que con el matrimonio gay pueden no formarse parejas estables.

  • Dí un algoritmo (machista) para conseguir pareja.

  • Probé que la única consitución -o sistema electoral- justo es la dictadura.


  • 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:

  • haya un dictador;

  • haya un candidato proscripto;

  • se puede votar tácticamente para perjudicar candidatos.


  • 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.

    14 comentarios:

    wraitlito dijo...

    Se me ocurren dos cuestiones relacionadas:
    ¿Por qué no encontré profes como tú cuando estudiaba? o bien ¿por qué, si los encontré, no los reconocí y aproveché?
    XD
    Saludos

    Juan Martínez-Tébar Giménez dijo...

    Je, je je muy buena y terrorífica entrada.
    Gracias por tu participación

    JuanPablo dijo...

    gracias Juan!

    wraitlito, estamos muy lejos! igual estoy seguro que por allá hay otros mucho mejores. En La Laguna se me ocurren varios...

    Amio Cajander dijo...

    es lo que tienen las matematicas cuya crudeza no es afectadas por convenios sociales.

    Asi las cosas deberías estudiar la estabilidad de los matrimonios entre matémáticos XD

    JuanPablo dijo...

    :) las parejas entre matemáticos andan bastante bien, por lo menos las que conozco (sean gays o no)

    married without children dijo...

    hoy justo durante el almuerzo estabamos 5 matematicos discutiendo sobre cuales serian los axiomas para tener una pareja "abierta" y no fracasar en el intento. No llegamos a mucho, pero conseguimos una teoria del "indice de impacto" impactante. Ya aparecera' publicada por alli...

    JuanPablo dijo...

    eso ha de estar incluído dentro de la teoría de hedonic games (se forman subgrupos de la población, y cada uno 'gana' según quiénes están en su grupo).

    Si considerás el grupo de los que no te importa que tu pareja interactúe, y a su vez es maximal y cerrado con el mismo criterio para los demás jugadores que están en pareja, debería ser estable si no hay nadie afuera que tu pareja quiera y que a su vez él esté dispuesto a cambiarse de grupo para estar con tu pareja.

    pablotossi dijo...

    genial! para la posteridad.... y para el nobel :P

    Diego dijo...

    Quizás el camino para redimirte sea dar otros teoremas, se me ocurren el de Aumann ("mutually respectful, honest and rational debaters cannot disagree on any factual matter once they know each other's opinions") y el de Milgrom y Stokey sobre la irracionalidad del comercio especulativo.

    JuanPablo dijo...

    jajaja! gracias, pablo!

    JuanPablo dijo...

    Diego, tenés razón. Son dos grandes sugerencias! El de Aumann lo puse en la lista de posibles temas para final (you can't agree to disagree). El de Milgrom no lo tenía, en general esquivé los que requieren cierta base económica, de hecho no hice ninguno de los modelos de formación de precios más básicos (aunque dejé los distintos duopolios como tema de final, porque no son tan complicados).

    Igual, la clase de ayer volví al redil con el valor de Shapley, y espero dar la semana que viene el modelo de Nash para NTU, y algo completamente diferente de juegos diferenciales :)

    Alberto dijo...

    tal vez te interese consultar un juego interactivo basado en el problema del matrimonio estable http://ow.ly/3ft7x

    Anónimo dijo...

    Buena entrada. Ahora mismo estoy estudiando a Arrow (estudio economía).

    Rojo Merlin dijo...

    Hola, me gusta esta entrada, espero que no te importe si algún día utilizo esta información para escribir un cuento de los mios.
    Saludos.