Code disponible pour des solutions informatiques aux algorithmes correspondants?

15

La question de la conception de la procédure d'appariement (entre les lycées et les étudiants, les stagiaires en médecine et les hôpitaux, les donneurs et les récepteurs rénaux, ...) a été largement étudiée par les économistes et a largement contribué à ce que Roth et Shapley reçoivent le prix Nobel en économie.

Je me demandais si vous connaissiez un code disponible gratuitement (idéalement dans un langage de relativement haut niveau) capable de calculer des solutions aux principaux problèmes d'appariement pour certains des algorithmes les plus célèbres proposés dans la littérature. Je pense à en écrire un, mais je préfère ne pas qu'il existe déjà.

Je suis principalement intéressé par un morceau de code pour calculer la solution de l' algorithme d' acceptation différée dans un problème de choix d'école , mais tout autre élément serait apprécié.

algorithms mechanism-design Martin Van der Linden
la source
Avez-vous examiné les packages R pour les algorithmes de correspondance? Voir ici par exemple ( article JSS ). Cela ne résout pas exactement votre exemple de problème, mais peut être un point de départ.
CompEcon
Une conférence pertinente (avec du code) sur le site Web de QuantEcon.
cc7768
Dans notre ReplicationWiki, vous pouvez trouver du matériel de réplication pour de nombreuses méthodes. Un aperçu des études empiriques qui ont utilisé l'appariement peut être trouvé ici . Vous pouvez également voir si des réplications sont déjà connues. Si vous ne voulez que des cas avec des données et du code et que vous voulez voir quel logiciel a été utilisé, vous pouvez utiliser le formulaire de recherche comme ici , il y a un exemple avec MATLAB et un avec R / ConG.
Jan Höffler
1
Dans le ReplicationWiki (sur lequel je travaille), vous pouvez trouver du matériel de réplication pour de nombreuses méthodes. Un aperçu des études empiriques qui ont utilisé l'appariement peut être trouvé ici . Vous pouvez également voir si des réplications sont déjà connues. Si vous ne voulez que des cas avec des données et du code et que vous voulez voir quel logiciel a été utilisé, vous pouvez utiliser le formulaire de recherche comme ici , il y a un exemple avec MATLAB et un avec R / ConG.
Jan Höffler

Réponses:

11

En répondant à un commentaire, je me suis rendu compte que j'avais une réponse qui valait la peine. R est devenu le "langage par défaut" pour de nombreuses statistiques de recherche informatique (pour un certain nombre de raisons; bel article du NYT ici ). Il est de haut niveau, gratuit et open-source, et possède une revue étroitement liée à la publication d'algorithmes statistiques. Les citations et l'examen par les pairs sont essentiels pour le monde universitaire, vous obtenez donc beaucoup de code bien décrit publié dans les archives R (CRAN) avec des descriptions publiées dans JStat. Cela déborde sur de nombreux blogs et des messages de code de démonstration rapides.

Autrement dit, il existe une énorme base de code créée par l'utilisateur pour R. Lorsque j'ai besoin de trouver un algorithme en ligne, je vais souvent d'abord regarder la base de code R massive. Une recherche rapide du code R a révélé ce qui suit:

D'un blogueur R , avec du code (voir le lien essentiel):

L'algorithme d'acceptation différée (DAA) remonte à Gale et Shapley (1962). Ils introduisent un algorithme assez simple qui trouve une correspondance stable, par exemple pour les admissions à l'université ou sur un marché matrimonial. ... Des variantes de cet algorithme sont utilisées dans les missions hospitalières aux États-Unis, où les médecins récemment diplômés soumettent leurs préférences aux hôpitaux, et les hôpitaux soumettent leurs préférences aux diplômés. ... Ici, je vais utiliser R pour faire une petite simulation de cela

À partir d'un référentiel github installable pour les marchés correspondants :

Le package R matchingMarketsest livré avec deux estimateurs:

  • stabit: Implémente un estimateur Bayes qui estime les préférences des agents et corrige la sélection des échantillons dans les marchés correspondants lorsque le processus de sélection est un jeu d'appariement unilatéral (c'est-à-dire la formation de groupes).

  • stabit2: Implémente l'estimateur de Bayes pour un jeu d'appariement bilatéral (c'est-à-dire les admissions à l' université et les problèmes de mariage stable ).

et trois algorithmes qui peuvent être utilisés pour simuler des données correspondantes:

  • hri: Modèle de contrainte pour le problème hôpital / résidents. Recherche tous les appariements stables sur les marchés d'appariement bilatéraux. Mis en œuvre à la fois pour le problème du mariage stable (jumelage un à un) et le problème de l' hôpital / des résidents , alias le problème des admissions au collège (jumelage plusieurs à un).

  • sri: Modèle de contrainte pour le problème des colocataires stables. Recherche tous les appariements stables dans le problème des colocataires (marché d'appariement unilatéral).

  • ttc: Algorithme Top-Trading-Cycles. Trouve des appariements stables dans le problème du marché du logement .

Fonctionne hriet sripermet des listes de préférences incomplètes (certains agents trouvent certains agents inacceptables) et des instances déséquilibrées (nombre inégal d'agents des deux côtés).

J'espère que l'un d'eux peut vous aider. Le second en particulier semble extrêmement utile, surtout s'il fournit un estimateur empirique.

CompEcon
la source
1

Je sais que c'est un peu obsolète, mais il y a un nouveau package disponible sur CRAN maintenant appelé 'matchingR' qui je pense est beaucoup plus rapide que le package recommandé ci-dessus. Vous pouvez l'installer avec

install.packages('matchingR')

De plus, voici un lien vers la source .

NickJ
la source