Gale-Shapley-Folgeliteratur und allgemeine Fragen

Der Gale-Shapley-Algorithmus ist eine Methode zum Matchmaking zwischen zwei verschiedenen Einheiten von Menschen. Es garantiert, dass jeder einzelne Spieler übereinstimmt und dass die Spiele stabil sind.

Welche Art von Literatur wurde daraus aufgebaut? Wie verändert sich die soziale Wohlfahrt, wenn die beiden Einheiten nicht die gleiche Anzahl von Personen in sich haben, so dass nicht jeder übereinstimmen kann? Gibt es schnellere Möglichkeiten, Personen miteinander abzugleichen (geringere Laufzeit?). Und vor allem, welche Anwendungen hat der Gale-Shapley-Algorithmus in der Wirtschaft?

Es scheint ein sehr seltsames spieltheoretisches Modell zu sein, nur weil es beim Lesen des Beweises für die Gültigkeit des Algorithmus nicht so aussieht, als sei das Problem "diskret". Das heißt, die Optimierung, wer mit wem übereinstimmt, und das Finden eines Pareto-effizienten Ergebnisses können nicht durch Maximierung einer kontinuierlichen Funktion gelöst werden. (Ist die Gale-Shapley-Zuweisung Pareto als Nebenfrage effizient?)

Bearbeiten Ich wollte im zweiten Absatz sagen: "Es scheint, als ob das Problem" diskret "ist. Also entschuldige ich mich dort.

Wie verändert sich die soziale Wohlfahrt, wenn die beiden Einheiten nicht die gleiche Anzahl von Personen in sich haben, so dass nicht jeder übereinstimmen kann?

Der Algorithmus funktioniert in diesem Fall einwandfrei. Die wichtige Annahme ist immer noch, dass der zugrunde liegende Graph zweiteilig ist (und dass Präferenzen transitiv sind). Wenn wir zulassen, dass Mitglieder eines bestimmten Typs sich gegenseitig Vorschläge machen, verlieren wir die Konvergenz. Angenommen, wir haben drei Spieler:$A, B, C$. Wir haben$A$Vorlieben als $(B, C, A)$;; $B$Vorlieben als $(C, A, B)$;; und$C$Vorlieben als $(A, B, C)$. Damit$A$ schlägt vor $B$, die akzeptiert. Dann$B$ schlägt vor $C$, die akzeptiert. Dies ist unübertroffen$A$. Nächster,$C$ schlägt vor $A$, die akzeptiert. Dies ist unübertroffen$B$. Wir wiederholen dann.

Gibt es schnellere Möglichkeiten, Personen miteinander abzugleichen (geringere Laufzeit?)

Gale-Shapley hat eine Laufzeitkomplexität von $\Theta(n^{2})$. In der Graphentheorie werden die meisten zweigliedrigen Matching-Algorithmen verwendet$\Omega(|E| \sqrt{|V|})$Zeit. Im schlimmsten Fall,$|E| = |V|^{2}/4$. Ich würde mich also nicht viel besser darauf verlassen.

Darüber hinaus ist dies kein Problem, das sich gut für einen Divide and Conquer-Ansatz eignet. Es ist wirklich ein gieriges Problem. Möglicherweise können Sie die erwartete Laufzeit verringern, indem Sie eine zufällige Reihenfolge für das Vorschlagen auswählen. Die Analyse wäre jedoch involviert.

Es scheint ein sehr seltsames spieltheoretisches Modell zu sein, nur weil es beim Lesen des Beweises für die Gültigkeit des Algorithmus nicht so aussieht, als sei das Problem "diskret". Das heißt, die Optimierung, wer mit wem übereinstimmt, und das Finden eines Pareto-effizienten Ergebnisses können nicht durch Maximierung einer kontinuierlichen Funktion gelöst werden.

Eigentlich ist es ein diskretes Modell. In traditionelleren Bereichen der Wirtschaft haben wir kontinuierliche Variablen. Lineare Programmierung ist also sinnvoll. Wir könnten tatsächlich ein ganzzahlig-lineares Programm für das Problem der stabilen Ehe formulieren, wenn wir es aus einer graphentheoretischen Perspektive betrachten. Übereinstimmende Probleme können in der Sprache der Flüsse formuliert werden. Und wir können Flussprobleme als LPs schreiben. Die Strömungsbeschränkungen bilden ein konvexes Polytop. Wenn der Graph zweiteilig ist, sind die Eckpunkte des Polytops die Übereinstimmungen. Der Trick dabei ist, dass wir zusätzliche Einschränkungen hinzufügen müssen, um sicherzustellen, dass wir die richtige Übereinstimmung erhalten (da die Übereinstimmung mit dem Gale-Shapley-Algorithmus unabhängig von der Reihenfolge, in der die Männer vorschlagen, eindeutig ist).

Selbst wenn wir uns die Mühe machen, das lineare Programm zu formulieren, ist die Lösung einer LP für dieses Problem von Hand oder von einem Computer weniger effizient als die Verwendung des Algorithmus.

(Ist die Gale-Shapley-Zuweisung Pareto als Nebenfrage effizient?)

Das vom Gale-Shapely-Algorithmus erzeugte Matching befindet sich im Kern. Eine Anrechnung, die zum Kern gehört, erfüllt die Eigenschaft, dass keine Koalition ihre ursprünglichen Stiftungen kollidieren und die Ergebnisse ihrer Mitglieder verbessern kann. Eine Imputation ist paretooptimal, wenn keine Gruppe von Agenten ihre Ergebnisse verbessern kann, ohne dass das Ergebnis eines anderen Spielers ungünstiger ist. Die Kernzuweisungen sind also paretooptimal.

Weitere Informationen zu Gale-Shapley finden Sie in meinem Blog: https://michaellevet.wordpress.com/2015/05/22/algorithmic-game-theory-stable-marriage-problem/