Was ist die algorithmische Spieltheorie? Mit Beispielen erklärt

Als Nisan und Ronen 1999 ihre Ideen zu einem Papier beisteuerten, wurde die Welt Zeuge eines neuen Konzepts für das Design algorithmischer Mechanismen. Es versucht, den Preis der Anarchie zu negieren, wo Eigeninteresse immer zu einem degradierten System führt.

Ihr Papier bewies, dass mehrere eigennützige Parteien ein produktives System im Gleichgewicht aufbauen könnten. Anstatt also auf eine degradierende Wirtschaft zu schauen, würden wir uns mit sozialer Wohlfahrt und Einkommensmaximierung befassen.

Algorithmic Game Theory (AGT) basiert auf dem Verständnis von Algorithmic Mechanism Design (AMD) .

Während AMD beschreibt, dass Eigeninteresse zu einem guten System führen könnte, zielt AGT darauf ab, ein strategisches Setup zu analysieren und zu entwerfen, das die Handlungen der eigennützigen Teilnehmer beschreibt.

Bevor wir uns ansehen, wie AGT im strategischen Umfeld funktioniert, schauen wir uns an, wie die Spieltheorie funktioniert!

Lassen Sie uns die Spieltheorie anhand eines Beispiels verstehen

In einer perfekten Welt, in der jeder Zug ein kalkuliertes Unterfangen ist, würde die Spieltheorie nicht so viel Sinn machen wie heute.

Die Idee, den nächsten Schritt intelligenter, rationaler Bürger zu berechnen, ist sowohl aufregend als auch beängstigend.

Die Spieltheorie schreibt vor, dass die konkurrierenden Parteien in jeder gegebenen sozialen Situation rationale Entscheidungen treffen können, indem sie die Gültigkeit der Möglichkeiten bewerten und die Nettobewegung des Konkurrenten abschätzen.

Während es wie ein Glücksspiel erscheinen mag, haben Theoretiker eine erklärbare Strategie wieder eingeführt, die den Glauben entwurzelt, dass es sich um ein Glücksspiel handelt.

Das am häufigsten genannte Beispiel ist das Gefangenendilemma.

Lernen: Top 8 Projekte, die jeder Entwickler unbedingt ausprobieren sollte

Gefangenendilemma erklärt

Die Prämisse ist einfach – als die Polizei zwei Sträflinge festnahm und sie zu dem Verbrechen befragte, würde keiner ihr Schweigen brechen.

Also beschloss der DA, dies zu vereinfachen, indem er drei Bedingungen vor sich aufstellte, da sie nebeneinander sitzen.

• Bedingung 1: Wenn keiner von ihnen die Tat gesteht, gehen sie für sechs Jahre ins Gefängnis.
• Bedingung 2: Wenn einer den anderen verrät, darf sich der Whistleblower frei bewegen, während der andere zehn Jahre lang reingeht.
• Bedingung 3: Wenn beide gestehen, gehen sie für ein Jahr ins Gefängnis.

Unmittelbar nach dem Anhören der Bedingungen werden sie in einen separaten Raum geführt, um ihre Entscheidungen zu treffen.

Wir können diese Daten als solche in Form einer Matrix übertragen;

Quelle

Die Lösung für dieses Problem ist einfach;

Jeder Gefangene wird erwägen, die Wahrheit über das Verbrechen zu sagen. Keiner der beiden kann streng sagen, dass der andere schweigen wird. Also geben beide der Wahrscheinlichkeit nach, das Verbrechen zu gestehen und gehen nur für ein Jahr ins Gefängnis.

Die Spieltheorie ist eine mächtige Waffe in den Händen dessen, der sie ausübt. Wir können selbst die komplexesten Situationen entschlüsseln, indem wir die Natur der Zahlen und die soziale Anordnung verstehen.

Algorithmische Spieltheorie

Betrachten Sie nun ein Venn-Diagramm der Spieltheorie und Informatik. Stellen Sie sich eine drastische Erhöhung der Genauigkeit vor, warum die Wahrscheinlichkeit, Antworten zu erhalten, grafisch dargestellt wird.

Und das macht die Algorithmische Spieltheorie (AGT) !

Es versucht, moderne Probleme zu lösen, indem es ein perfektes Gleichgewicht zwischen Computeralgorithmen und Spieltheorie findet.

Mit weiteren einfacheren Worten versucht die algorithmische Spieltheorie, das sozioökonomische Gleichgewicht zwischen der Ausführung einer Aufgabe zu definieren. Es verwendet auch die Prinzipien des Nash-Gleichgewichts; Es besagt, dass die Teilnehmer, sobald sie eine Strategie gefunden haben, die für sie funktioniert, nicht davon abweichen möchten, bis sie nicht mehr zu ihrem Vorteil funktioniert.

Nehmen wir ein kleines Beispiel, um die Funktionsweise der algorithmischen Spieltheorie zu verstehen.

Reisen wir zurück in die Schule, als wir Spiele wie Kho-Kho, Ice & Water, Chain-Cut usw. gespielt haben. Jedes dieser Spiele hat ein schönes Design und einen Mechanismus zum Spielen.

Betrachten wir zum Beispiel Ice & Water;

• Es gibt mehrere Spieler und einen Fänger. Der Fänger soll alle in Eis verwandeln.
• Die anderen Spieler haben die Macht, jemanden bei Berührung wieder in Wasser zu verwandeln.
• Es gibt Freizonen, in denen sich die Spieler 30 Sekunden ausruhen können.

Nun, wenn Sie genau hinschauen, werden Sie sehen, dass jede dieser Regeln den Mechanismus des Spiels ausmacht und sein Design definiert.

• Die Spieler können dieses Spiel so lange spielen, wie sie es interessant finden. Hier beschreibt The Nash Equilibria , dass die Spieler spielen sollten, solange sie ihre Strategie als funktionierend und das Spiel interessant finden.
• Die Ration eines Spielers darf nicht erwischt werden. Und sie handelt nach dieser Ration, indem sie den Aufbau versteht. Sie wendet einen objektiven Ansatz an, bei dem sie das Spiel gewinnt, indem sie nicht erwischt wird. Und dies ist im Volksmund als Mechanism Design oder Reverse Game Theory bekannt.
• Wenn nun jeder Spieler nur ein Motiv in Betracht zieht – „Nicht erwischt zu werden“ – und den zweiten Teil davon – „die anderen Spieler zu retten“ nicht berücksichtigt, dann wird dieses Konzept der Preis der Anarchie genannt. Es erklärt, wie die Effizienz jedes Systems aufgrund des egoistischen Verhaltens der Spieler abnimmt.

Aus den drei oben genannten Konzepten ergeben sich nun eine Fülle weiterer Konzepte. Während sie alle ganz oder teilweise mit der Spieltheorie verwandt sind, schaffen sie eine funktionale Basis für die algorithmische Spieltheorie.

Checkout: 42 spannende Python-Projektideen und -themen für Anfänger

Nun stellt sich die Frage: „Wie stellen wir ein strategisches Umfeld in Bezug auf Algorithmen dar?“

Schauen wir uns nun an, wie wir Python verwenden können, um eine strategische Umgebung zu definieren und die Implementierung von Nashpy für eine bestimmte Situation zu verstehen.

Stellen Sie sich vor, Sie spielen mit einem Ihrer Freunde eine Partie Schere-Stein-Papier. Jeder von Ihnen hat eine der drei Optionen;

• Felsen
• Papier
• Schere

Und die Rubrik, um das Spiel zu gewinnen, ist

• Stein zermalmt Schere
• Schere schneidet Papiere
• Papier bedeckt Stein

Und das bedeutet, dass, wenn beide Spieler Rock präsentieren, es zu Do-Overs kommt.

Wir können dies in Form einer 3×3-Matrix darstellen, wobei Aij ist;

Quelle

Hinweis: Hier sind i und j die Züge, die von den beiden Spielern gespielt werden.

Hier,

• Null bedeutet, dass Sie beide dasselbe Objekt gespielt haben (Stein-Stein; oder Papier-Papier)
• Einer stellt dar, dass einer von euch den anderen übertrumpft (wie eine Steinschere)
• Minus Eins bedeutet, dass einer von Ihnen verloren hat, weil der andere Sie übertrumpft hat (wie Steinpapier)

Um dies nun auf Nashpy darzustellen, schreiben Sie einen Code, der in etwa so aussieht;

Quelle

Abschließende Gedanken

Die algorithmische Spieltheorie ist ein perfektes Prinzip in der gegenwärtigen Welt, in der der Wettbewerb aus Eigeninteresse entsteht und der Sieg die Erfüllung des Eigeninteresses ist.

Wenn Sie also als moderne Manager, Lehrer, CXOs oder Geschäftsleute die Dominanz der algorithmischen Spieltheorie verstehen, dann erlauben Sie mir, das Zitat von Severus Snape aus Harry Potter zu ändern;

„Algorithmische Spieltheorie kann Ihnen beibringen, wie man Ruhm in Flaschen abfüllt, Ruhm braut und sogar Verluste eindämmt.“

Das Verständnis der algorithmischen Spieltheorie kann Ihnen dabei helfen, entschlossener als je zuvor mit Zahlen umzugehen. In der heutigen Zeit, in der wir bis ins kleinste Detail entscheiden, um einen nachhaltigen Plan zu entwickeln, erweist sich AGT als ein transformierender Aspekt.

Wir wissen bereits, dass Data Science Unternehmen in eine lukrative Arena verwandeln kann, aber AGT hat die Macht, die Schwelle zu erhöhen.

Angenommen, Sie stehen der Spieltheorie immer noch skeptisch gegenüber und erklären, dass Data Science heute der lukrativste und wettbewerbsfähigste Beruf ist.

Wenn Sie neugierig sind, mehr über Data Science zu erfahren, schauen Sie sich das PG Diploma in Data Science von IIIT-B & upGrad an, das für Berufstätige entwickelt wurde und mehr als 10 Fallstudien und Projekte, praktische Workshops, Mentoring mit Branchenexperten, 1- on-1 mit Mentoren aus der Branche, mehr als 400 Stunden Lern- und Jobunterstützung bei Top-Unternehmen.