Neidfreie Mietaufteilung verständlich erklärt

Mehrere Betriebe teilen sich eine Halle mit ungleich begehrten Flächen und eine feste Miete. Teilt man die Miete gleich, wäre mancher lieber auf der Fläche des Nachbarn. Die Seite zeigt, wie Preise aussehen, bei denen das nicht passiert, und was sie kosten. Ein Programm zum Ausprobieren (die Demo) gehört dazu.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Halle, mehrere Betriebe, eine Miete

Stellen Sie sich vor, mehrere Betriebe mieten gemeinsam eine Lagerhalle. Die Halle ist in ebenso viele Flächen geteilt, wie es Betriebe gibt, und jeder Betrieb bekommt genau eine. Die Flächen sind nicht gleich viel wert: Eine liegt direkt am Tor, eine hat eine Rampe, eine liegt hinten in der Ecke. Zusammen zahlen alle eine feste Gesamtmiete. Zu klären ist, wer welche Fläche bekommt und was jeder dafür zahlt.

Der naheliegende Vorschlag: Alle zahlen gleich viel, die Gesamtmiete geteilt durch die Zahl der Flächen. Aber wer in der Ecke landet und genauso viel zahlt wie der Nachbar am Tor, schaut zum Tor hinüber und denkt: Zu diesem Preis hätte ich diese Fläche lieber. Dieses Gefühl heißt Neid. Das Ziel ist Neidfreiheit: Kein Betrieb würde eine fremde Fläche zu deren Preis lieber nehmen als seine eigene zu ihrem Preis.

Was eine Fläche dem Betrieb wert ist

Damit man Neid überhaupt messen kann, sagt jeder Betrieb, was ihm jede Fläche wert ist, in Euro (seine Wertangaben). Dabei darf er nur die Gesamtmiete verteilen: Gibt er einer Fläche mehr, bleibt für die anderen weniger. Er kann also nicht überall „viel“ sagen. Was ein Betrieb von einer Fläche hat, ist ihr Wert für ihn minus ihr Preis. Das ist sein Nutzen. Neid heißt dann: Mit einer anderen Fläche zu deren Preis hätte er mehr Nutzen als jetzt.

Warum gleiche Preise Neid erzeugen können

Wären alle Flächen für jeden Betrieb gleich viel wert, könnte man die Miete gleich teilen, und es gäbe nichts zu beneiden. Sind die Flächen verschieden begehrt, zahlen der Betrieb am Tor und der in der Ecke trotzdem gleich viel. Hält der Betrieb in der Ecke das Tor für wertvoller als seine Ecke, ist er neidisch: Der am Tor hat für denselben Preis die bessere Fläche.

Die Demo erzeugt die Wertangaben nach Zufall, in drei Mustern: Entweder bewertet jeder Betrieb die Flächen unabhängig von den anderen, oder alle Betriebe haben ähnliche Vorlieben, oder eine Fläche ist für alle besonders begehrt. Diese Zufallsbeispiele sind der Maßstab für alles Folgende. In ihnen ist die gleich geteilte Miete bei mehr Betrieben seltener neidfrei als bei weniger.

Zu einer passenden Zuteilung gab es Preise ohne Neid

Die gute Nachricht: In allen Zufallsbeispielen, die die Demo durchgerechnet hat, gab es zu einer passenden Zuteilung Preise, bei denen kein Betrieb neidisch ist. Man geht in zwei Schritten vor. Erst legt man fest, wer welche Fläche bekommt. Jeder Betrieb gibt seiner zugeteilten Fläche einen Wert; diese Werte zählt man zusammen, und die Summe soll so groß wie möglich sein. Dann setzt man die Preise für alle Flächen. Die Summe allein genügt nicht, die Preise sind ein eigener zweiter Schritt.

Warum die Summe so groß sein muss, zeigt ein Beispiel mit zwei Betrieben, die über Kreuz liegen: Der Betrieb mit dem Tor schätzt die Ecke höher als das Tor, der Betrieb in der Ecke das Tor höher als die Ecke. Die Preise bleiben an den Flächen; wer die Fläche des anderen nimmt, zahlt deren Preis. Tauschen die beiden, zahlen sie zusammen dasselbe wie vorher, haben aber zusammen mehr von ihren Flächen. Mindestens einer hätte danach mehr Nutzen als vorher und war also vorher neidisch, gleichgültig, wie die Preise standen. Dieselbe Überlegung gilt für Tausch im Kreis unter mehreren Betrieben. Bekommt jeder Betrieb genau eine Fläche, gibt es neidfreie Preise deshalb nur bei einer Zuteilung mit der größtmöglichen Summe.

Zu dieser Zuteilung kann es mehrere Möglichkeiten geben, die Preise für alle Flächen neidfrei zu setzen. Welche man nimmt, ist eine Auswahlregel und keine Frage der Neidfreiheit mehr. Die Demo vergleicht zwei Regeln. Die eine sorgt dafür, dass der am schlechtesten gestellte Betrieb möglichst viel Nutzen hat (größter Mindestnutzen). Die andere wählt Preise, bei denen der Abstand zwischen teuerster und billigster Fläche, die Preisspanne, möglichst klein ist.

Der Haken: negative Preise

Die Regel mit dem größten Mindestnutzen wählt in der Demo teils einen Preis unter null: Wer diese Fläche nimmt, bekommt Geld dazu, und die anderen zahlen entsprechend mehr. Verbietet man Preise unter null, sind weniger Preise erlaubt. Dann kann der am schlechtesten gestellte Betrieb weniger Nutzen herausholen, und bei ähnlichen Vorlieben blieben in einem Teil der Zufallsbeispiele gar keine neidfreien Preise übrig.

Wie häufig ein Preis unter null vorkommt, hängt vom Muster ab. Bei ähnlichen Vorlieben wählte die Regel mit dem größten Mindestnutzen ihn in gut der Hälfte der Zufallsbeispiele, bei einer Fläche, die alle besonders wollen, in keinem. Die Regel mit der kleinsten Preisspanne wählt ihn in diesen Beispielen seltener, lässt aber den am schlechtesten gestellten Betrieb mit weniger Nutzen zurück.

Wie weit tragen diese Aussagen?

Alles in der Demo ist erzeugt: Die Wertangaben sind Zufallszahlen, jeder Betrieb nimmt genau eine Fläche, und alle geben ihre Werte ehrlich an. Die Aussagen gelten für diese Annahmen, nicht für einen bestimmten echten Betrieb.

Woran Sie es im eigenen Betrieb erkennen: Plätze, Räume oder Flächen werden zum gleichen Preis verteilt, obwohl sie verschieden begehrt sind, und jemand fragt, warum er nicht den anderen Platz zu dessen Preis haben kann. Die Gegenprobe: Lassen Sie jeden Beteiligten eine feste Summe, etwa die Gesamtmiete, auf die Plätze verteilen, so wie in der Demo, und fragen Sie, ob er bei den heutigen Preisen seinen eigenen Platz behalten würde. Bei einem Nein passen Sie die Preise an oder ändern die Zuteilung, bis niemand mehr tauschen möchte.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst Modell und Methodik der Demo zusammen; die vollständige Formulierung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Instanz: \(n\) Mieter, \(n\) Flächen, Gesamtmiete \(R\) = 1 000 €. Die Bewertungen \(v_{ij}\) sind ganze Zahlen \(\ge 0\); jede Zeile summiert sich auf \(R\) (der Mieter verteilt die Miete nach seiner Zahlungsbereitschaft auf die Flächen). Drei Geschmacksmodelle: unabhängig (Zufallszahl hoch \(k\) je Fläche), ähnlich (gemeinsames Gewicht je Fläche mit 0,7 bis 1,3 Streuung je Mieter) und Premiumfläche (flache Gewichte, eine Fläche mit dem Faktor 2 + \(k\)). \(k\) ist die Ungleichheit (1 bis 7).
• Aufteilung: eine Zuordnung \(\sigma\) und Preise \(p_j\) mit Summe \(R\). Neid ist, was eine andere Fläche zu ihrem Preis mehr Nutzen brächte; neidfrei heißt kein Neid.
• Zuordnung: die mit der größten Summe der Bewertungen, gerechnet mit scipy.optimize.linear_sum_assignment (löst dasselbe wie die Ungarische Methode). Nur zu einer solchen Zuordnung gibt es neidfreie Preise, und zu jeder gibt es dieselben.
• Fünf Preisregeln: Gleich (\(R/n\) je Fläche), Mittel (Durchschnitt der Bewertungen je Fläche), Neidfrei (Maximin) (lineare Optimierung: größter kleinster Nutzen, danach unter dem Optimum die kleinste Preisspanne; die zweite Stufe ist eine eigene Festlegung, damit die Preise reproduzierbar sind), Ab 0 (dasselbe mit \(p \ge 0\); ist das System unlösbar, steht „nicht möglich“) und Kleinste Spanne (die geringste Differenz zwischen teuerster und billigster Fläche unter allen neidfreien Preisen).
• Messreihen: feste Programme, je Zelle 300 Instanzen mit den Zufalls-Seeds 100000 bis 100299. Ein unabhängiges Orakel in den Tests rechnet die Zuordnung durch Aufzählung aller Permutationen und die Preise exakt mit Brüchen über alle Ecken des Preisvielecks.

Die Formeln

Bewertungen \(v_{ij} \ge 0\) mit \(\sum_j v_{ij} = R\) für jeden Mieter \(i\); eine Aufteilung ist eine Zuordnung \(\sigma\) (Mieter \(i\) bekommt Fläche \(\sigma(i)\)) und Preise \(p_j\) mit \(\sum_j p_j = R\). Der Nutzen von Mieter \(i\) ist

\[u_i = v_{i\sigma(i)} - p_{\sigma(i)}\]

Neidfrei ist eine Aufteilung, wenn kein Mieter eine andere Fläche zu deren Preis vorzieht, für alle \(i, j\):

\[v_{i\sigma(i)} - p_{\sigma(i)} \ge v_{ij} - p_j\]

also

\[p_{\sigma(i)} - p_j \le v_{i\sigma(i)} - v_{ij}\]

Das ist ein lineares System. Es hat eine Lösung genau dann, wenn \(\sigma\) die Summe \(\sum_i v_{i\sigma(i)}\) maximiert, und dann gilt dasselbe für jede maximierende Zuordnung (Dualität der Zuordnungsaufgabe). Neidfreie Preise für die Gesamtmiete \(R\) gab es in allen gemessenen Instanzen; nach der Literatur gibt es sie immer, mit erlaubten negativen Preisen, und die Eichung „Zeile summiert auf \(R\)“ ist dafür nicht nötig (so steht es in der Demo, aus dem Gedächtnis). Nur der Ausschluss negativer Preise machte sie manchmal unmöglich.

Maximin maximiert \(t\) unter der Nebenbedingung

\[t \le v_{i\sigma(i)} - p_{\sigma(i)}\]

sowie Neidfreiheit und \(\sum_j p_j = R\). Danach folgt unter dem Optimum \(t^*\) die kleinste Spanne

\[\min \bigl(\max_j p_j - \min_j p_j\bigr)\]

Die Regel „Kleinste Spanne“ ist dasselbe ohne die Bedingung an \(t\).

Befunde

Alle Zahlen stammen aus der README der Demo (jede steht in deren Tests, tests/test_claims.py). Sie gelten für die festen Messreihen: Gesamtmiete 1 000 €, je Zelle 300 Instanzen, 4 Mieter und Ungleichheit 2, soweit nichts anderes steht; die Reihen nach Mieterzahl und Ungleichheit rechnen mit unabhängigen Geschmäckern. Anteile und Mediane einer festen Stichprobe: Die Zufallszahlen eines numpy-Generators sind nicht über Versionen stabil, die Tests prüfen darum Bänder (±8 Prozentpunkte bei Anteilen, ±12 % bei Medianen); Nullen und Aussagen „in jeder Instanz“ sind in den festen Läufen exakt.

Frage	Befund
Stimmt der Kern?	Zuordnung gleich der Aufzählung aller Permutationen (80 Instanzen, 3 bis 6 Mieter); jede optimale Zuordnung liefert denselben Maximin-Wert (40 Instanzen); Neidfreiheit gleich der Definition (120 Instanzen, 3 bis 7 Mieter) und Neid gleich der Definition (120 Instanzen); Maximin, Maximin ab 0 und kleinste Spanne gleich einer exakten Rechnung mit Brüchen über alle Ecken des Preisvielecks (je 36 Instanzen mit drei Mietern, dazu vier Instanzen mit vier Mietern).
Wie selten ist die gleiche Aufteilung neidfrei?	Bei 4 Mietern in 10 % der Instanzen (unabhängig), 0 % (ähnlich) und 0 % (Premiumfläche); mit 3, 4, 5, 6, 7 Mietern 23, 10, 3, 2, 1 %. Der größte Neid beträgt im Median 188 € (unabhängig), 491 € (ähnlich) und 438 € (Premiumfläche); mit der Ungleichheit 1 bis 6 wächst er von 89 € auf 538 €.
Und das Mittel der Bewertungen?	Neidfrei bei 31 % (unabhängig), 5 % (ähnlich) und 19 % (Premiumfläche); größter Neid im Median 43 € (unabhängig). Es ist näher an neidfrei als die gleiche Aufteilung, aber keine Lösung.
Gibt es neidfreie Preise?	Ja, in allen 3 600 verschiedenen Instanzen der drei Reihen (Maximin und kleinste Spanne, Neid 0 €). Mit der Forderung „Preise ab 0“ nicht immer: nicht möglich in 1 % (unabhängig), 19 % (ähnlich) und 0 % (Premiumfläche); mit 3 bis 7 Mietern in 0, 1, 4, 6, 5 %; mit der Ungleichheit 1 bis 6 in 0, 1, 5, 6, 9, 9 %.
Wie oft enthält die gewählte neidfreie Aufteilung einen negativen Preis?	Maximin: 35 % (unabhängig), 51 % (ähnlich), 0 % (Premiumfläche); mit 3 bis 7 Mietern 23, 35, 45, 48, 49 %; mit der Ungleichheit 1 bis 6 4, 35, 61, 75, 80, 84 %. Die kleinste Spanne hat sie seltener (12 %, 37 %, 0 %). Nötig sind negative Preise nur, wenn „Preise ab 0“ nicht möglich ist (1 %, 19 %, 0 %).
Was bringt der größte Mindestnutzen gegenüber gleicher Aufteilung?	Der kleinste Nutzen steigt im Median um 187 € (unabhängig), 250 € (ähnlich) und 139 € (Premiumfläche), in praktisch jeder Instanz (in jeder Zelle mindestens 99 %); mit 3 bis 7 Mietern um 216, 187, 177, 145, 123 €; mit der Ungleichheit 1 bis 6 um 99 € bis 415 €.
Was kostet „Preise ab 0“?	Der Mindestnutzen sinkt im Median bei der Ungleichheit 2 von 198 € auf 170 €, bei der Ungleichheit 6 von 322 € auf 104 €; die Preisspanne sinkt bei der Ungleichheit 6 von 831 € auf 548 €.
Und die kleinste Preisspanne?	Spanne im Median 202 € statt 452 € (Maximin), aber ein Mindestnutzen von nur 89 € statt 198 €. Er liegt in 8 % der Instanzen (Ungleichheit 2) unter dem der gleichen Aufteilung und ist in weiteren 10 % gleich (dort ist die gleiche Aufteilung schon neidfrei). Neidfrei ist nicht dasselbe wie hoher Mindestnutzen.
Wie breit sind die Preise?	Die Spanne der Maximin-Preise wächst mit der Ungleichheit von 235 € auf 831 € (Median) und schrumpft mit der Mieterzahl (457 € bei 3, 314 € bei 7 Mietern).

Grenzen

• Ehrliche Bewertungen: Wer weiß, wie gerechnet wird, kann seine Bewertungen verschieben und so einen niedrigeren Preis erreichen; die Demo geht von wahren Angaben aus. Wie viel ein Mieter durch falsche Angaben gewinnen könnte, ist nicht gemessen.
• Die Auswahl unter den neidfreien Preisen ist eine Wertung: Der größte Mindestnutzen ist die Auswahl von Spliddit (nach den Abstracts; die Quellen sind nicht im Original gelesen). Die zweite Stufe (kleinste Preisspanne unter dem Optimum) und die Regel „Kleinste Spanne“ sind eigene Festlegungen. Die Preise der Regel „Kleinste Spanne“ sind nicht immer eindeutig; Messreihen und Tests prüfen den Wert, nicht den Preisvektor.
• Die Zahlen hängen vom Erzeuger der Bewertungen ab: Der Anteil negativer Preise beim Maximin reicht von 0 % (Premiumfläche) bis 51 % (ähnlich) bei sonst gleichen Einstellungen und, nach der Ungleichheit, von 4 bis 84 %. Echte Betriebe sind nicht gemessen.
• Jeder Mieter nimmt genau eine Fläche, Flächen sind nicht teilbar, und es gibt ebenso viele Flächen wie Mieter. Die Bewertungen sind in Euro, jede Zeile summiert sich auf die Gesamtmiete; mit anderer Eichung wären Preise und Nutzen andere.
• Löser: Die Preise kommen aus dem Simplex-Löser HiGHS; die Tests vergleichen die Werte mit der exakten Rechnung mit Brüchen.
• „Immer“ heißt: in allen gemessenen Instanzen. Dass neidfreie Preise mit erlaubten negativen Preisen immer existieren, ist nach der Demo ein bekannter Satz der Zuordnungsspiele (aus dem Gedächtnis); hier bestätigt, nicht bewiesen. Eine Stichprobe von 300 Instanzen je Zelle: kleine Unterschiede sind kein Befund.
• Nicht enthalten: mehr Flächen als Mieter, mehrere Flächen je Mieter, Teilbarkeit; Mindest- und Höchstpreise je Fläche („Preise ab 0“ ist der einfachste Fall davon); Auktionsverfahren und Preisanpassung in Runden (gerechnet werden nur die Gleichgewichtspreise); weitere Auswahlregeln unter den neidfreien Preisen (etwa Leximin).

Quellen

• Goldman, J., Procaccia, A. D.: Spliddit. ACM SIGecom Exchanges, 2014 (Auswahl des größten Mindestnutzens).
• Gal, Y., Mash, M., Procaccia, A. D., Zick, Y.: Which Is the Fairest (Rent Division) of Them All? Journal of the ACM, 2017. Laut Expander der Demo ist unter allen neidfreien Aufteilungen Maximin in der Nutzerstudie die fairste.
• Su, F. E.: Rental Harmony, 1999.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/mietaufteilung-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen. Die Angaben stehen im Expander der Demo (mit dem Vermerk „aus Abstracts, nicht im Original geprüft“); die README nennt nur Spliddit und die Abstracts. Nicht aus der README stammt die Überlegung im Einsteigerteil, warum nur eine Zuteilung mit der größten Summe der Wertangaben neidfrei sein kann (Tausch zweier Betriebe); sie folgt aus dem Rechnen mit Nutzen und Preisen und ist keine Messung.