Aprendizaje descentralizado y no coordinado de emparejamientos estables: Un enfoque teórico de juegos

Consideramos el problema de aprender emparejamientos estables de manera completamente descentralizada y no coordinada. En este problema, hay n hombres y n mujeres, cada uno con preferencias sobre el otro lado. Se supone que las mujeres conocen sus preferencias sobre los hombres, pero los hombres no son conscientes de sus preferencias sobre las mujeres y solo las aprenden si proponen y logran emparejarse con mujeres. Un emparejamiento se llama estable si ningún hombre y mujer se prefieren el uno al otro sobre sus emparejamientos actuales. Cuando todas las preferencias son conocidas a priori, el célebre algoritmo de Aceptación Diferida propuesto por Gale y Shapley proporciona un algoritmo descentralizado y no coordinado para obtener un emparejamiento estable. Sin embargo, cuando las preferencias son desconocidas, desarrollar tal algoritmo enfrenta importantes desafíos debido a la falta de coordinación. Logramos este objetivo estableciendo una conexión entre emparejamientos estables y el aprendizaje de equilibrios de Nash (NE) en juegos no cooperativos. Primero, proporcionamos una formulación de juego de información completa para el problema de emparejamiento estable con preferencias conocidas, de tal manera que su conjunto de NE puros coincide con el conjunto de emparejamientos estables, mientras que sus NE mixtos pueden redondearse de manera descentralizada a un emparejamiento estable. Basándonos en tal formulación teórica de juegos, mostramos que para mercados jerárquicos, adoptar el algoritmo de aprendizaje de peso exponencial (EXP) para el juego de emparejamiento estable logra un arrepentimiento logarítmico con dependencia polinómica en el número de jugadores, respondiendo así a una pregunta planteada en la literatura anterior. Además, mostramos que el mismo algoritmo de aprendizaje EXP converge local y exponencialmente rápido a un emparejamiento estable en mercados de emparejamiento generales. Complementamos este resultado introduciendo otro algoritmo de aprendizaje descentralizado y no coordinado que converge globalmente a un emparejamiento estable con una probabilidad arbitrariamente alta, aprovechando la propiedad de debilidad acíclica del juego de emparejamiento estable.