Kooperation und Wettbewerb erklärt
Sobald mehrere Beteiligte mit eigenen Zielen im Spiel sind, reicht Optimieren nicht mehr: Was für den einen gut ist, ändert, was für die anderen gut ist. Die sieben Linien dieses Bereichs behandeln vier Seiten davon: Anreize und Strategien (was passiert, wenn jeder für sich entscheidet, und wann Kooperation trägt), Gegner und Turniere (direkter Wettbewerb und seine Organisation), Wertung und Ranking (was Ergebnisse über die Stärke aussagen) und Gemeinsam entscheiden (Abstimmen und Teilen).
Jede Linie hat eine eigene Seite mit einem Abhängigkeitsgraphen und ihren Demos. Die Themenfelder unten ordnen die Linien nach Verwandtschaft, der Beziehungsgraph am Ende zeigt, welche Linien sich Bausteine teilen.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Anreize und Strategien
Mehrere Entscheider mit eigenen Zielen: Gleichgewichte, wiederholte Begegnungen und die Frage, wie man Regeln so setzt, dass Eigennutz zum gewünschten Ergebnis führt.
Multi-Agenten-Koordination
Aufträge ohne zentrale Instanz verteilen: von Contract Net über Verhandlung, DCOP und Multi-Agenten-Lernen bis zu Auktionen und gelernten Mechanismen.
Zur Linie →Spieltheorie
Wer hat welchen Anreiz? Zehn Verfahren zu eigennützigen Lkw und zu Spediteuren, die Kosten teilen, jedes mit seinem gemessenen Befund.
Zur Linie →Wiederholte Spiele
Zwei Spediteure, die sich jede Woche wiedersehen: elf Stücke von Tit-for-Tat über das Folk-Theorem und Preiskriege bis zu lernenden Preis-Algorithmen.
Zur Linie →Gegner und Turniere
Direkter Wettbewerb: gegen einen Gegner planen und einen Wettbewerb so organisieren, dass er fair und aussagekräftig verläuft.
Turnierplanung
Wie plant man ein faires Turnier mit vertretbarer Rundenzahl, und was zählt sonst noch: Heimrecht, Reisedistanz, eine zweite Chance, der Gleichstand? Acht Antworten, jede gegen echte Referenzdaten oder Literatur geprüft.
Zur Linie →Adversarische Suche
Wie entscheidet eine Maschine ihren nächsten Zug gegen einen Gegner, der das Gegenteil will? Von der erschöpfenden Minimax-Suche über Effizienz-Tricks und Bewertungsfunktionen bis zum Selbstspiel-Training.
Zur Linie →Wertung und Ranking
Aus Ergebnissen eine Rangfolge machen und wissen, wie sicher sie ist: von der Siegtabelle über Bradley-Terry und Elo bis zum Vergleich der Verfahren.
Ranking
Wie wird aus Vergleichen eine Rangfolge, und wie sicher ist sie? Ein simuliertes Turnier mit bekannter Stärke, siebzehn Stücke von der Siegtabelle über Bradley-Terry und Elo bis zu Rangintervallen und Learning to Rank.
Zur Linie →Gemeinsam entscheiden und teilen
Aus verschiedenen Wünschen eine Entscheidung oder faire Verteilung machen: Wahlen, Sitze, Budgets, Güter, Mieten, Kuchen.
Abstimmen und Fair Teilen
Wie aus verschiedenen Wünschen eine Entscheidung oder eine faire Verteilung wird: fünfzehn Stücke von der Wahlregel bis zur Kuchenteilung.
Zur Linie →Empfohlene Reihenfolge
Wer einen Bereich von vorn lesen möchte: Die Reihenfolge folgt den Bausteinen, die eine Linie von einer anderen übernimmt (die Belege stehen auf den Linienseiten unter „Verwandt in anderen Linien“). Alles lässt sich auch einzeln lesen.
- Spieltheorie: Das Einmalspiel: Nash-Gleichgewicht, Anreize, Kostenteilung.
- Wiederholte Spiele: Setzt das Einmalspiel unendlich oft fort; dort trägt Kooperation als Gleichgewicht.
- Multi-Agenten-Koordination: Aufträge ohne zentrale Instanz; dort liegen die Zahlungsregeln der Auktion (VCG) und der gelernte Mechanismus als Gegenstück zur Spieltheorie.
- Adversarische Suche: Entscheiden gegen einen Gegner, der das Gegenteil will: von der Minimax-Suche bis zum Selbstspiel-Training.
- Turnierplanung: Wettbewerb organisieren: Rundenturnier, K.-o.-System, Schweizer System und der Gleichstand.
- Ranking: Aus den Ergebnissen eine Rangfolge machen; die Linie wertet, was ein Turnierplan liefert.
- Abstimmen und Fair Teilen: Aus verschiedenen Wünschen eine Entscheidung oder faire Verteilung machen; dort liegen Wahlregeln, Sitze und Budgets sowie das Teilen von Gütern, Mieten und Kuchen.
Wie die Linien dieses Bereichs zusammenhängen
Jede Kante steht für einen belegten Zusammenhang: Ein Verfahren nutzt innen eine Technik der anderen Linie, oder beide gehen dasselbe Problem aus verschiedenen Blickwinkeln an. Die Farbe zeigt das Themenfeld, gestrichelte Kästen sind Linien aus anderen Bereichen, mit denen es Verbindungen gibt. Die jeweilige Linienseite erklärt jeden Zusammenhang unter „Verwandt in anderen Linien“.
Die Kästen sind klickbar und öffnen die jeweilige Seite.
- Anreize und Strategien
- Gegner und Turniere
- Wertung und Ranking
- Gemeinsam entscheiden und teilen
- Linie eines anderen Bereichs
Weitere Bereiche
Optimierung
Verfahren, die aus sehr vielen Möglichkeiten eine beste oder gut begründete Entscheidung suchen: mit Beweis, mit Heuristik, für Planung und unter Unsicherheit.
Maschinelles Lernen
Verfahren, die aus Daten lernen: Struktur finden, wenn niemand die Antwort vorgibt, vorhersagen, wenn Beispiele vorliegen, und handeln oder Wirkung messen.
Signalverarbeitung
Verfahren, die aus gemischten oder unscharfen Messungen die ursprünglichen Signale zurückgewinnen oder aus verrauschten Messungen einen Zustand schätzen.
Graphentheorie
Verfahren, die Fragen über Netze selbst beantworten: erreichbar, verbunden, kritisch, zugeordnet, zentral, schmalbandig oder wie sich etwas auf dem Netz ausbreitet.