¿Código disponible para soluciones informáticas para algoritmos coincidentes?

La cuestión de diseñar un procedimiento de correspondencia (entre escuelas secundarias y estudiantes, médicos internos y hospitales, donantes y receptores de riñones, ...) ha sido ampliamente estudiada por economistas y ha contribuido enormemente a que Roth y Shapley reciban el premio Nobel en economía.

Me preguntaba si conocía algún código disponible gratuitamente (idealmente en un lenguaje de nivel relativamente alto) capaz de calcular soluciones a los principales problemas de coincidencia para algunos de los algoritmos más famosos propuestos en la literatura. Estoy pensando en escribir uno, pero preferiría que ya no exista.

Estoy principalmente interesado en algún código para calcular la solución del algoritmo de aceptación diferida en un problema de elección de escuela , pero cualquier otra cosa sería apreciada.

Mientras respondía un comentario, me di cuenta de que tenía una respuesta que valía la pena. R se ha convertido en el "lenguaje predeterminado" para muchas estadísticas de investigación computacional (por varias razones; bonito artículo del NYT aquí ). Es de alto nivel, gratuito y de código abierto, y tiene una revista estrechamente relacionada para publicar algoritmos estadísticos. Las citas y la revisión por pares son clave para la academia, por lo que obtiene una gran cantidad de código bien descrito publicado en los archivos R (CRAN) con descripciones publicadas en JStat. Esto se extiende a muchos blogs y publicaciones de código de demostración rápida.

Es decir, hay una enorme base de código creada por el usuario para R. Cuando necesito encontrar un algoritmo en línea, a menudo primero busco la base de código R masiva. Una búsqueda rápida del código R arrojó lo siguiente:

De un blogger R , con código (ver el enlace principal):

El algoritmo de aceptación diferida (DAA) se remonta a Gale y Shapley (1962). Presentan un algoritmo bastante simple que encuentra una correspondencia estable, por ejemplo, para admisiones a la universidad o en un mercado matrimonial. ... Las variaciones de este algoritmo se utilizan en asignaciones de hospitales en los EE. UU., Por lo que los médicos recién graduados presentan preferencias sobre los hospitales, y los hospitales presentan preferencias sobre los graduados. ... Aquí voy a usar R para hacer una pequeña simulación de esto

Desde un repositorio de github instalable para mercados coincidentes :

El paquete R matchingMarketsviene con dos estimadores:

• stabit: Implementa un estimador de Bayes que estima las preferencias de los agentes y corrige la selección de muestras en los mercados de emparejamiento cuando el proceso de selección es un juego de emparejamiento unilateral (es decir, formación de grupos).

• stabit2: Implementa el estimador de Bayes para un juego de combinación de dos lados (es decir, las admisiones a la universidad y los problemas matrimoniales estables ).

y tres algoritmos que pueden usarse para simular datos coincidentes:

• hri: Modelo de restricción para el problema del hospital / residentes. Encuentra todos los emparejamientos estables en los mercados de emparejamiento de dos lados. Implementado tanto para el problema del matrimonio estable (emparejamiento uno a uno) como para el problema del hospital / residentes , también conocido como problema de admisión a la universidad (emparejamiento muchos a uno).

• sri: Modelo de restricción para el problema de compañeros de habitación estables. Encuentra todos los emparejamientos estables en el problema de compañeros de cuarto (mercado de emparejamiento unilateral).

• ttc: Algoritmo de los principales ciclos de negociación. Encuentra coincidencias estables en el problema del mercado inmobiliario .

Funciona hriy sripermite listas de preferencias incompletas (algunos agentes consideran que ciertos agentes son inaceptables) e instancias desequilibradas (número desigual de agentes en ambos lados).

Esperemos que uno de estos pueda ayudar. El segundo en particular parece extremadamente útil, particularmente si proporciona un estimador empírico.

Sé que esto está un poco desactualizado, pero hay un nuevo paquete disponible en CRAN ahora llamado 'matchingR' que creo que es mucho más rápido que el paquete recomendado anteriormente. Puedes instalarlo con

install.packages('matchingR')

Además, aquí hay un enlace a la fuente .