Verfügbarer Code zur Berechnung von Lösungen für passende Algorithmen?

15

Die Frage der Gestaltung von Matching-Verfahren (zwischen Gymnasien und Schülern, Medizinpraktikanten und Krankenhäusern, Nierenspendern und -empfängern, ...) wurde von Wirtschaftswissenschaftlern eingehend untersucht und trug maßgeblich dazu bei, dass Roth und Shapley den Nobel-Gedenkpreis für Wirtschaftswissenschaften erhielten.

Ich habe mich gefragt, ob Sie über frei verfügbaren Code (idealerweise in einer höheren Sprache) Bescheid wissen, der in der Lage ist, Lösungen für die hauptsächlichen Übereinstimmungsprobleme für einige der bekanntesten in der Literatur vorgeschlagenen Algorithmen zu berechnen . Ich denke darüber nach, eine zu schreiben, aber ich möchte lieber nicht, dass es sie bereits gibt.

Ich bin hauptsächlich an einem Teil des Codes interessiert , um die Lösung für den verzögerten Akzeptanzalgorithmus in einem Schulwahlproblem zu berechnen , aber alles andere wäre wünschenswert.

algorithms mechanism-design Martin Van der Linden
quelle
Haben Sie in R-Paketen nach passenden Algorithmen gesucht? Siehe hier zum Beispiel ( JSS-Papier ). Dies geht nicht genau auf Ihr Beispielproblem ein, kann aber ein Ausgangspunkt sein.
CompEcon
Ein relevanter Vortrag (mit einigem Code) auf der QuantEcon-Website.
cc7768
In unserem ReplicationWiki finden Sie Replikationsmaterial für viele Methoden. Eine Übersicht über empirische Studien, die Matching verwendet haben, finden Sie hier . Sie können auch sehen, ob Replikationen bereits bekannt sind. Wenn Sie nur Fälle mit Daten und Code möchten und sehen möchten, welche Software verwendet wurde, können Sie das Suchformular wie hier verwenden . Es gibt ein Beispiel mit MATLAB und eines mit R / ConG.
Jan Höffler
1
Im ReplicationWiki (an dem ich arbeite) finden Sie Replikationsmaterial für viele Methoden. Eine Übersicht über empirische Studien, die Matching verwendet haben, finden Sie hier . Sie können auch sehen, ob Replikationen bereits bekannt sind. Wenn Sie nur Fälle mit Daten und Code möchten und sehen möchten, welche Software verwendet wurde, können Sie das Suchformular wie hier verwenden . Es gibt ein Beispiel mit MATLAB und eines mit R / ConG.
Jan Höffler

Antworten:

11

Bei der Beantwortung eines Kommentars wurde mir klar, dass ich eine Antwort erhalten habe, die sich nachträglich gelohnt hat. R ist die "Standardsprache" für viele Computerforschungsstatistiken geworden (aus mehreren Gründen; schöner NYT-Artikel hier ). Es ist kostenlos und quelloffen auf hohem Niveau und verfügt über ein eng verwandtes Journal für die Veröffentlichung statistischer Algorithmen. Zitate und Peer Review sind für die Wissenschaft von zentraler Bedeutung, daher erhalten Sie eine Menge gut beschriebener Codes, die mit Beschreibungen in JStat im R-Archiv (CRAN) veröffentlicht werden. Dies überträgt sich auf viele Blogs und kurze Demonstrations-Code-Posts.

Das heißt, es gibt eine enorme Codebasis, die von Benutzern für R erstellt wird. Wenn ich einen Algorithmus online suchen muss, schaue ich oft zuerst auf die massive R-Codebasis. Eine schnelle Suche nach R-Code ergab Folgendes:

Von einem R-Blogger mit Code (siehe Hauptlink):

Der Deferred Acceptance Algorithm (DAA) geht auf Gale and Shapley (1962) zurück. Sie führen einen ziemlich einfachen Algorithmus ein, der eine stabile Übereinstimmung findet, zum Beispiel für College-Zulassungen oder in einem Heiratsmarkt. ... Variationen dieses Algorithmus werden in Krankenhausaufgaben in den USA verwendet, wobei kürzlich abgeschlossene Ärzte Präferenzen gegenüber Krankenhäusern und Krankenhäuser Präferenzen gegenüber Absolventen abgeben. ... Hier benutze ich R, um dies ein wenig zu simulieren

Aus einem installierbaren Github-Repository für passende Märkte :

Das R-Paket enthält matchingMarketszwei Schätzer:

  • stabit: Implementiert einen Bayes-Schätzer, der die Präferenzen der Agenten schätzt und die Stichprobenauswahl in Matching-Märkten korrigiert, wenn der Auswahlprozess ein einseitiges Matching-Spiel ist (dh Gruppenbildung).

  • stabit2: Implementiert den Bayes-Schätzer für ein zweiseitiges Matching-Spiel (dh die College-Zulassungen und stabile Eheprobleme).

und drei Algorithmen, mit denen Matching-Daten simuliert werden können:

  • hri: Einschränkungsmodell für das Krankenhaus- / Bewohnerproblem. Findet alle stabilen Übereinstimmungen in zweiseitigen Übereinstimmungsmärkten. Implementiert sowohl für das stabile Eheproblem (Eins-zu-Eins-Matching) als auch für das Krankenhaus / Bewohner-Problem , auch College-Zulassungsproblem genannt (Viele-zu-Eins-Matching).

  • sri: Einschränkungsmodell für das Stallbewohnerproblem. Findet alle stabilen Übereinstimmungen im Mitbewohner-Problem (einseitiger Matching-Markt).

  • ttc: Top-Trading-Zyklen-Algorithmus. Findet stabile Übereinstimmungen im Wohnungsmarktproblem .

Funktionen hriund sriermöglichen unvollständige Präferenzlisten (einige Agenten finden bestimmte Agenten inakzeptabel) und unausgeglichene Instanzen (ungleiche Anzahl von Agenten auf beiden Seiten).

Hoffentlich kann einer von diesen helfen. Insbesondere die zweite scheint äußerst nützlich zu sein, insbesondere wenn sie einen empirischen Schätzer liefert.

CompEcon
quelle
1

Ich weiß, dass dies etwas veraltet ist, aber es gibt ein neues CRAN-Paket namens 'matchingR', das meiner Meinung nach viel schneller ist als das oben empfohlene Paket. Sie können es mit installieren

install.packages('matchingR')

Auch hier ist ein Link auf die Quelle .

NickJ
quelle