• Christian Hoffmeister

Googles PageRank und Spieltheorie

Die Spieltheorie hat eine große Bedeutung in der Gestaltung digitaler Geschäftsmodelle insbes. bei der Gestaltung der Algorithmen, die die Abläufe und Ergebnisse auf Plattformen steuern. UBER, eBay, booking.com aber eben besonders Google, nutzen die Möglichkeiten der Spieltheorie, um ihre Plattformen zu gestalten. Dies deshalb, weil die Spieltheorie eine interaktive Entscheidungstheorie darstellt.

Wenn also mehrere Akteure gemeinsam ein Ergebnis erzielen, ist dies ein Anwendungsgebiet der Spieltheorie. Das Ergebnis jedes Akteurs hängt also nur von seinen eigenen Aktionen ab, sondern auch von den Aktionen der anderen Spieler. Und kein Akteur kann alleine sein optimales Ergebnis entscheiden.


Es geht bei der Spieltheorie daher immer um Interaktion und Steuerung, weshalb diese Themengebiet natürlich ganz nahe an den Ideen und Konzepten der modernen Computer liegt.


Und an Hand der kurzen Beschreibung lässt sich schon erahnen, warum der PageRank, also der Algorithmus, der entscheidet, wie eine Website in Bezug auf ein bestimmtes KeyWord auf der Suchergebnisseite von Google gerankt wird, eine spieltheoretische Anwendung darstellt. Denn kein Websitebetreiber kann alleine bestimmen, wie er innerhalb der Ergebnisse gerankt wird, denn seine Position hängt maßgeblich von den Aktionen (vor allem den Verweisen oder auch Backlinks) anderer Websitebetreiber ab.


Sehen wir uns nun den ursprünglichen PageRank an, wie dieser in der „einfachen“ Form funktioniert und wie dieser die Ideen der Spieltheorie integriert.


Die Formel lautet:





Dabei steht PR für PageRank, n = Gesamtzahl der Seiten, c = Anzahl abgehender Links einer betrachteten Website n und d ist der Dämpfungsfaktor, der auf alle PR angewandt wird (und den ich daher im Folgenden weglasse).


Wird nun zum Beispiel der PR von n-Seiten gesucht, dann muss zuerst festgelegt werden, wieviel Seiten n überhaupt betrachtet werden.


Nehmen wir ein ganz einfaches Beispiel. Es werden 3 Seiten (=n) A/B/C betrachtet.


Also n = 3


Der erste Schritt besteht dann darin, dass alle Seiten A/B/C den PR 1/n also in unserem Fall 1/3 erhalten. Für A gilt also PR(A) = 0,33.








Nun wird eine Seite analysiert in dem nachgeschaut wird, welche andere Seite diese Seite verweist. Nehmen wir also A und sagen, dass C auf A verweist. Dann sieht dies graphisch so aus










In der Formel steht dabei c für Verlinkung. Die Seite C weißt also c=1 auf.


Nun wenden wir die Formel (ohne Dämpfungsfaktor) an:



PR (A) ist die Summe aus dem eigenen PR (0,33) und der Summe aus den anteiligen PR der verweisenden Seiten, also in diesem Fall bekommt A etwas von C zurück.

In der Formel steht PR(C)/c(C), d.h. der PR der Seite C (der ja momentan auch noch 1/3 ist) wird durch die Anzahl der ausgehenden Links geteilt. Und da C aktuell nur einen ausgehenden Link aufweist, ergibt sich 1/3 geteilt durch 1. Damit bekommt A in diesem Fall 1/3 von C zugerechnet. Der neue PR von A ist nun also 0,33+0,33 bzw. 0,66.


Wenn nun aber die Seite C auch auf B verweist, dann ändert sich der PageRank von A und von B. denn c ist nun 2 und nicht mehr 1.










In diesem Fall müssen wir den PageRank A neu berechnen.


A erhält nun PR(C)/c(C) und c ist nun 2 (zwei ausgehende Links). Damit bekommt nun A nicht mehr 1/3 geteilt durch 1 sondern, 1/3 geteilt durch 2, also 0,17. Der PageRank von A wäre in diesem Fall nur noch 0,5 statt zuvor 0,66.


Eine Besonderheit, liegt nun darin (dies kann man aus der Formel nicht erkennen), dass Google Website, die keine ausgehenden Links setzen insofern bestraft, dass diese anteilig auf alle betrachteten Websites n, ihren PageRank aufteilen müssen, d.h. sie werten alle anderen Seiten auf, und sich selbst damit ab.


Daher würde sich nun der PageRank von C verändern, weil nun A wieder an C etwas zurückgibt. In unserem Fall muss A nun 0,5/2 an die Seiten B und C abgeben.

Der PageRank C verändert sich also auf 1/3 + (0,5/2) = 0,58.


Wie man nun schon erkennen kann, ändert sich nun wieder der PR A, denn nun erhält A von C nicht 0,17, sondern 0,29. Damit steigt PR von A nun auf 0,62.


Würde nun A aktiv einen Link auf B setzen, dann wird wiederum das Ergebnis verändert und wenn B einen Link auf C setzt ebenfalls. Das Beispiel würde daher nun folgendermaßen aussehen:










Nehmen wir nun willkürlich B heraus und wollen denn PageRank (PR) von B wissen, dann ergibt dieser aus einer ersten Berechnung circa 1, da er sich wie folgt berechnet:



Da aber B wieder C und C wiederum A beeinflusst, müssten die einzelnen PR dynamisch und mehrmals gerechnet werden, um auf ein stabiles Ergebnis zu gelangen


Dieses simple Beispiel ist nun schon so komplex, dass es von einem Menschen nicht mehr schnell und effizient berechnet werden kann. Will man das gezeigte Beispiel nun selber durchrechnen, wird man feststellen, dass es sich um eine Endlosschlaufe handelt, da sich alle wechselseitig beeinflussen und es daher kein finales Ergebnis geben kann. In der Praxis wird dies dadurch gelöst, dass für die festlegte Menge an betrachteter Seiten n, 1.000 Iterationen berechnet werden. Statistisch gesehen kommt es danach zu keinen großen Veränderungen mehr, egal wie groß n ist.


Da Menschen derartige Anwendungen nicht rechnen können, übernehmen das nun Computer, die das in Millisekunden berechnen können. Wer dies für das Beispiel überprüfen will, kann dies hier tun.

Das Ergebnis lautet dann (in diesem Fall mit Dämpfungsfaktor):










Aus der einfachen Analyse einer Verlinkungsstruktur hat nun Google eine Art unendliches interaktives Superspiel entwickelt, bei dem sich die Akteure in ihren Positionen immer wechselseitig beeinflussen. Jede Website hängt also sowohl von den eigenen Entscheidungen als auch von den Entscheidungen aller anderen Akteure ab.


Der Google PageRank kann daher als eine spezielle Form der angewandten Spieltheorie gesehen werden. Dies wird an den folgenden Punkten noch einmal verdeutlicht:


Allgemein lässt sich ein Spiel im Sinne der Spieltheorie beschreiben, wenn folgende Kriterien erfüllt sind:

  • Mehrere Akteure interagieren

  • Jeder Akteur hat gewisse Handlungsoptionen (Verweisen / nicht verweisen).

  • Aus diesen Möglichkeiten wählt jeder Akteur aus

  • Jede Auswahl führt zu einer Belohnung/Bestrafung im Sinne eines positiven oder negativen eigenen Ergebnisses

  • Jeder Spieler versucht, sein Ergebnis zu maximieren


Übertragen auf den PageRank lassen sich die Kriterien folgendermaßen anwenden:

  • Mehrere Akteure interagieren, d.h. alle Websitebetreiber interagieren direkt und indirekt miteinander

  • Jeder Akteur hat gewisse Handlungsoptionen (Verweisen / nicht verweisen).

  • Aus diesen Möglichkeiten wählt jeder Akteur seine Strategie aus (verlinke ich und wenn ja an wen?)

  • Jede Auswahl führt zu einer Belohnung/Bestrafung im Sinne eines positiven oder negativen eigenen Ergebnisses, d.h. die Wahl die eine Websitebetreiber in Bezug auf die Links trifft, hat Auswirkungen auf die Position anderer Websites und auch auf seine eigene Position.

  • Jeder Spieler versucht, sein Ergebnis zu maximieren, u.a. durch geeignete Linkstrategien.




46 Ansichten
DCI Institute GmbH

Hartwicusstrase 6

22087 Hamburg

Geschäftsführer:

Christian Hoffmeister
Amtsgericht Hamburg 

HRB 99381