📈 economics

The Distribution of Envy in Matching Markets

Diese Arbeit untersucht die Verteilung von Neid in zufälligen Zuordnungsmärkten unter dem Deferred-Acceptance-Algorithmus, leitet exakte Ausdrücke und asymptotische Schranken für die Anzahl der ungeliebten bzw. neidfreien Akteure ab und vergleicht diese Ergebnisse mit der Random Serial Dictatorship, wobei sich zeigt, dass der Anteil der unverbesserlich zufriedenen Akteure im Markt verschwindet.

Ursprüngliche Autoren: Josué Ortega, Gabriel Ziegler, R. Pablo Arribillaga, Geng Zhao

Veröffentlicht 2026-03-25

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Josué Ortega, Gabriel Ziegler, R. Pablo Arribillaga, Geng Zhao

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Schulwahl-Spiel: Wer ist wirklich zufrieden?

Stellen Sie sich vor, es gibt eine riesige Schule mit n Plätzen und n Schüler. Jeder Schüler hat eine Liste mit seinen Lieblingsplätzen (von 1 bis n), und jede Schule hat eine Liste, wer sie am liebsten aufnehmen würde (ihre Prioritäten).

Das Ziel ist es, jeden Schüler einem Platz zuzuweisen. Dafür gibt es einen sehr beliebten Algorithmus namens Deferred Acceptance (DA). Man könnte ihn sich wie ein mehrstufiges Bewerbungsspiel vorstellen:

Jeder Schüler bewirbt sich bei seiner Nummer-1-Wahl.
Die Schulen halten sich vorläufig den besten Bewerber fest und lehnen die anderen ab.
Die Abgewiesenen bewerben sich bei ihrer Nummer-2-Wahl.
Das Spiel geht so lange weiter, bis jeder einen Platz hat.

Die Forscher aus diesem Papier stellen sich nun eine ganz einfache, aber tiefgründige Frage: Wie gerecht ist dieses Ergebnis eigentlich?

Sie schauen sich zwei Arten von „Neid" an:

Der „Glückliche" (Niemand beneidet ihn): Ein Schüler, dessen Schule so beliebt ist, dass niemand anders lieber dort wäre als er. Er ist der „König" seiner Schule.
Der „Zufriedene" (Er beneidet niemanden): Ein Schüler, der genau den Platz bekommen hat, den er am allerliebsten wollte. Er ist mit seinem Los komplett glücklich.

Die überraschenden Ergebnisse

Die Forscher haben berechnet, wie viele Schüler in diesen Kategorien landen, wenn die Vorlieben völlig zufällig sind (wie beim Ziehen von Losen).

1. Die „Glücklichen" (Niemand beneidet sie)

Stellen Sie sich vor, die Schulen sind wie Karten in einem Kartenspiel, das man sammelt (ein sogenanntes „Coupon-Collector"-Problem).

Die Analogie: Wenn Sie versuchen, ein komplettes Album mit 10.000 verschiedenen Karten zu sammeln, wie viele Karten haben Sie am Ende, von denen Sie nur eine einzige besitzen, während alle anderen Karten mehrfach in Ihrem Album sind?
Das Ergebnis: Die Forscher haben herausgefunden, dass die Anzahl der Schulen, die nur von einem Schüler „begehrt" werden (und daher niemanden beneidet), extrem klein ist.
Die Zahl: Sie wächst nur sehr langsam mit der Größe der Schule. Bei 10.000 Schülern gibt es im Durchschnitt weniger als 10 solche „unangefochtenen" Schüler.
Bedeutung: Fast jeder Schüler wird von jemandem beneidet. Es gibt kaum „Könige", die absolut sicher sind.

2. Die „Zufriedenen" (Sie beneiden niemanden)

Das sind die Schüler, die ihren absoluten Traumplatz bekommen haben.

Die Analogie: Stellen Sie sich vor, Sie werfen eine Münze. Die Wahrscheinlichkeit, dass Sie Ihren Traumplatz bekommen, ist wie eine sehr seltene Münze, die nur selten Kopf zeigt.
Das Ergebnis: Auch hier ist die Zahl klein, aber deutlich größer als bei den „Glücklichen". Bei 10.000 Schülern sind es etwa 1.100.
Bedeutung: Nur etwa 10 % der Schüler bekommen ihren Wunschkurs. Der Rest muss sich mit dem „Besten der Restlichen" zufriedengeben.

Der große Vergleich: DA vs. Das „Losverfahren" (RSD)

Um zu verstehen, ob das Ergebnis des DA-Algorithmus besonders schlecht oder besonders gut ist, vergleichen die Forscher ihn mit einem ganz anderen System: dem Zufalls-Losverfahren (RSD).

Wie RSD funktioniert: Man zieht alle Schüler zufällig in eine Reihenfolge. Der erste darf sich seinen absoluten Lieblingsplatz aussuchen. Der zweite nimmt sich den besten verbleibenden, und so weiter.

Das überraschende Fazit:

Beim Zufalls-Losverfahren (RSD): Die Hälfte aller Schüler bekommt ihren Traumplatz! (Das ist riesig).
Beim DA-Algorithmus: Nur etwa 10 % bekommen ihren Traumplatz. (Das ist viel schlechter).

Aber hier kommt der wahre „Aha-Moment":
Obwohl DA viel schlechter darin ist, Traumplätze zu vergeben, ist die Anzahl der Schüler, die niemanden beneidet (die „Glücklichen" von oben), in beiden Systemen exakt gleich!

In beiden Systemen gibt es im Durchschnitt nur etwa logarithmisch wenige Schüler (bei 10.000 Schülern also nur ca. 10), die so einen guten Platz haben, dass sie von niemandem beneidet werden.

Was bedeutet das für uns?

Die Forscher sagen im Grunde:
„Schaut mal, das System DA ist nicht perfekt. Es lässt viele Schüler auf ihren Traumplatz warten. Aber das ist nicht unbedingt ein Fehler des Systems, sondern eine Eigenschaft von großen, zufälligen Märkten."

Die „Unverbesserlichen": Die wenigen Schüler, die entweder ihren Traumplatz haben oder von niemandem beneidet werden, sind sozusagen „unantastbar". Man kann sie nicht noch besser stellen, ohne jemand anderen zu verletzen.
Die traurige Wahrheit: Diese Gruppe von „Unverbesserlichen" wird im Verhältnis zur Gesamtzahl der Schüler immer kleiner, je größer die Schule wird. In einer riesigen Welt ist es also extrem unwahrscheinlich, dass man jemanden trifft, der wirklich nichts zu beanstanden hat.

Zusammenfassend:
Das Papier zeigt uns, dass in großen, chaotischen Märkten (wie Schulwahlen) fast jeder Schüler ein wenig Neid in sich trägt oder von jemandem beneidet wird. Dass es nur sehr wenige „perfekte" Fälle gibt, liegt nicht daran, dass der Algorithmus DA schlecht ist, sondern daran, dass es in großen Gruppen mathematisch einfach unmöglich ist, dass alle zufrieden sind. Und selbst ein einfaches Losverfahren kann nicht verhindern, dass fast alle von jemandem beneidet werden – das ist einfach die Natur des Spiels.

Titel: Die Verteilung von Neid in Zuordnungsmärkten (The Distribution of Envy in Matching Markets)

Autoren: Josué Ortega, Gabriel Ziegler, R. Pablo Arribillaga, Geng Zhao
Veröffentlicht: März 2026 (arXiv)

1. Problemstellung und Motivation

Das Paper untersucht die Verteilung von „Neid" (Envy) in zufälligen Zwei-Seiten-Märkten (z. B. Schulwahl), die dem Deferred Acceptance (DA)-Algorithmus unterliegen. Während in der Stabilitätstheorie das Fehlen von begründetem Neid (justified envy) als definierendes Merkmal stabiler Matchings gilt, fragt die Arbeit nach dem Fehlen von jeglichem Neid, unabhängig von seiner Begründung.

Die Analyse konzentriert sich auf zwei spezifische Gruppen von Agenten (Schülern):

Schüler, die niemanden beneidet: Dies entspricht Schülern, die einer untergeforderten Schule (under-demanded school) zugewiesen wurden.
Schüler, die niemanden beneiden: Dies entspricht Schülern, die ihre absolut erste Präferenz (Top-Choice) erhalten haben.

Die Quantifizierung dieser Gruppen ist aus drei Gründen wichtig:

Pareto-Effizienz: DA ist nicht immer Pareto-effizient. Das Verständnis der Neidverteilung hilft, den Spielraum für Pareto-Verbesserungen zu bestimmen.
Wohlfahrtsmessung: Schüler, die ihre Top-Präferenz erhalten, sind ein direktes Maß für die Zufriedenheit, das oft von politischen Entscheidungsträgern verwendet wird.
Unverbesserbarkeit: Schüler, die entweder niemanden beneiden oder von niemandem beneidet werden, sind „unverbesserbar" (unimprovable). Sie können durch keinen Tausch von der DA-Lösung aus besser gestellt werden. Die Größe dieser Mengen liefert eine untere Schranke für die Anzahl aller unverbesserbaren Schüler.

2. Methodik und Modell

Das Modell betrachtet einen zufälligen Schulwahlmarkt mit $n$ Schülern und $n$ Schulen (jeweils mit einer Quote von 1).

Präferenzen: Alle Präferenzen und Prioritäten werden unabhängig und gleichverteilt zufällig gezogen (i.i.d.).
Algorithmus: Der Standard-DA-Algorithmus wird verwendet.
Analytische Werkzeuge: Die Autoren nutzen Methoden der angewandten Wahrscheinlichkeitstheorie, insbesondere den Zusammenhang zwischen der sequenziellen Implementierung von DA (nach McVitie und Wilson) und dem Coupon-Collector-Problem (Sammeln von Coupons).

Schlüsseltechnische Ansätze:

Sequenzielle DA-Implementierung: Anstatt das Matching als Ganzes zu betrachten, wird DA als sequenzieller Prozess modelliert, bei dem Schüler nacheinander Vorschläge machen.
Prinzip der verzögerten Entscheidungen (Principle of Deferred Decisions): Die Präferenzen der Schüler werden „on the fly" generiert. Jeder Schüler hat eine hypothetische unendliche Sequenz von zufälligen Schulzügen. Ein Vorschlag wird nur an die erste noch nicht versuchte Schule in dieser Sequenz gesendet.
Kopplung mit dem Coupon-Collector-Problem:
- Ein Schul wird als „untergefordert" (under-demanded) bezeichnet, wenn sie genau einen Vorschlag erhält.
- Die Autoren zeigen, dass die Anzahl der untergeforderten Schulen exakt der Anzahl der „Singletons" (einmal gesammelte Coupon-Typen) im klassischen Coupon-Collector-Problem zum Zeitpunkt des Stoppens (wenn alle Coupons gesammelt sind) entspricht.

3. Hauptbeiträge und Ergebnisse

A. Schüler, die niemanden beneidet (Unenvied Students)

Die Autoren leiten einen exakten Ausdruck für die erwartete Anzahl von Schülern her, die niemanden beneidet ($NEn$).

Ergebnis (Proposition 1): Die erwartete Anzahl ist exakt die $n$ -te harmonische Zahl:
$NEn = H_n = \sum_{k=1}^{n} \frac{1}{k}$
Asymptotik: Da $H_n \approx \ln n + \gamma$ , wächst diese Anzahl nur logarithmisch mit der Marktgröße $n$ .
Implikation: Der Anteil dieser Schüler geht gegen Null ( $NEn/n \to 0$ ). In einem Markt mit $n=10.000$ sind weniger als 10 Schüler von niemandem beneidet.
Besonderheit: Dies ist ein exaktes Ergebnis für jedes endliche $n$ , nicht nur asymptotisch.

B. Schüler, die niemanden beneiden (Students who Envy Nobody)

Hier wird die erwartete Anzahl von Schülern berechnet, die ihre Top-Präferenz erhalten ( $EN_n$ ).

Methodik: Die Verteilung des Ranges (Rang der erhaltenen Schule in der Präferenzliste) wird approximiert. Da ein typischer Schüler etwa $H_n$ Vorschläge macht und jede Schule etwa $H_n$ Vorschläge erhält, ist die Wahrscheinlichkeit einer Annahme pro Versuch asymptotisch $1/H_n$ .
Verteilung: Die Rangverteilung folgt asymptotisch einer geometrischen Verteilung mit Parameter $1/H_n$ .
Ergebnis (Proposition 2 & Korollar 1): Für große $n$ gilt:
$EN_n \approx \frac{n}{H_n}$
Implikation: Obwohl auch dieser Anteil gegen Null geht ( $1/\ln n$ ), ist die absolute Anzahl deutlich höher als bei den unenvied students. Bei $n=10.000$ sind dies ca. 1.100 Schüler.

C. Vergleich mit Random Serial Dictatorship (RSD)

Die Ergebnisse werden mit dem Random Serial Dictatorship (RSD) verglichen, einem anderen bekannten Zuordnungsmechanismus.

Top-Choice-Anteil: RSD weist eine konstante Fraktion ( $\approx n/2$ ) der Schüler ihrer Top-Präferenz zu, während DA dies nur für $\approx n/\ln n$ tut. DA ist hier also deutlich schlechter.
Unenvied-Anteil (Überraschendes Ergebnis): Die erwartete Anzahl der Schüler, die niemanden beneidet, ist unter RSD exakt gleich wie unter DA:
$NEn^{RSD} = H_n$
Bedeutung: Dies zeigt, dass die Anzahl der unenvied students eine fundamentale Eigenschaft von zufälligen Märkten ist und nicht von einem spezifischen Mechanismus abhängt.

4. Zusammenfassung der Ergebnisse (Tabelle 1 im Paper)

Mechanismus	Schüler, die niemanden beneiden (Top-Choice)	Schüler, die von niemandem beneidet werden
Deferred Acceptance (DA)	$\approx n / H_n$	$H_n$
Random Serial Dictatorship (RSD)	$(n+1)/2$	$H_n$

5. Signifikanz und Diskussion

Fundamentale Eigenschaft von Märkten: Die Tatsache, dass sowohl DA als auch RSD (und durch Äquivalenz auch TTC) exakt $H_n$ unenvied students produzieren, deutet darauf hin, dass dies eine inhärente Eigenschaft zufälliger Zuordnungsmärkte ist und nicht auf ein Versagen des DA-Algorithmus zurückzuführen ist.
Seltenheit von Unverbesserbarkeit: Da sowohl die Menge der unenvied als auch die der envy-free Schüler einen verschwindenden Anteil des Marktes ausmachen, ist der Anteil der Schüler, die durch Tausch verbessert werden können, asymptotisch fast 100%.
Skalierungseffekte: Während die absolute Anzahl der unenvied students mit $\ln n$ wächst, ist der relative Anteil $H_n/n$ für realistische Marktgrößen extrem klein (z. B. < 0,1 % bei $n=10.000$ ).
Offene Fragen: Die Autoren verweisen auf zukünftige Forschung zu korrelierten Präferenzen, Many-to-One-Märkten und der Frage, ob diese $H_n$ -Ergebnisse auf andere Mechanismen übertragbar sind.

Fazit: Das Paper liefert präzise, teils exakte, teils asymptotische Formeln für die Verteilung von Neid in DA-Märkten. Es widerlegt die intuitive Annahme, dass DA eine signifikante Anzahl von „zufriedenen" (unverbesserbaren) Schülern hinterlässt, und zeigt stattdessen, dass fast alle Schüler im Nachhinein potenziell durch Tausch verbessert werden könnten, wobei die Anzahl der unverbesserbaren Schüler logarithmisch klein bleibt.