Ansichten eines Informatikers

Spieltheorie: Die Mafia-Variante von tit for tat

Hadmut
10.7.2013 23:22

Wenn Informatik in der Realität auftaucht. (Korrektur/Update)

In der Süddeutschen war ein interessanter Artikel über das „Gleichgewicht des Schreckens”, in dem verschiedene Varianten beschrieben werden, in denen gezeigt wird, dass ein gegenseitiges Vertrauen die beste Strategie sein kann. Verblüffenderweise müssen sogar Kriminelle und Diebe untereinander vertrauen. Auch bei der italienischen Mafia gibt es Varianten dieses Verhaltens.

Bemerkenswert daran:

Diese Strategie ist in der Informatik als „tit for tat” bekannt, eine Erkenntnis aus der Spieltheorie.

Man hat Experimente gemacht, in denen mehrere Mannschaften (z. B. von Studenten) je ein Programm ins Rennen schicken konnte, und dann jedes Programm einmal gegen jedes andere Programm spielen musste. Es gibt verschiedene Varianten der Spielregeln, ich kenne sie in dieser Version: Stellt Euch vor, Ihr müsst mit einem Fremden Koffer tauschen, ohne in den Koffer sehen zu müssen. Jeder soll für den Tausch den vereinbarten Wertgegenstand (z. B. Ware und Kaufpreis in Geld) in den Koffer packen, kann aber auch betrügen und einen leeren Koffer abgeben. Keiner kann in den Koffer des anderen schauen und muss ihn eben nehmen.

Betrügen beide oder sind beide ehrlich, hat man nichts gewonnen und nichts verloren. Der Saldo bleibt 0. [Korrektur: Sind beide ehrlich, gibt es einen geringfügigen Gewinn 0 < x << 1, siehe dazu weiter unten] Betrügt man, ohne betrogen zu werden, gewinnt man +1, und wird man betrogen, obwohl man selbst gezahlt hat, hat man Verlust -1. Und dann müssen je Spielerpaar 100 Koffer getauscht werden, also die Spieler je 100 Mal gegeneinander spielen. Nach jedem Tausch sehen sie natürlich, ob sie betrogen wurden. Es geht also darum, eine Stragie zu entwickeln, wonach man den Koffer füllt oder betrügt und am Ende das beste Ergebnis zu haben. Um die Strategie algorithmisch fest und präzise zu beschreiben, durften die teilnehmenden Mannschaften eben nicht selbst spielen, sondern mussten ein Programm einreichen, das ihre Strategie implementiert.

Frappierenderweise gewann dabei immer wieder eine Strategie, die gar nicht gewinnen kann: tit for tat. Ganz primitiv: Beim ersten Spiel (Koffertausch) ist man kooperativ und füllt den Koffer. Bei jedem weiteren Spiel macht man das, was der andere vorher getan hat. Bekam man einen gefüllten Koffer, füllt man selbst den Koffer im nächsten Spiel. Und wird man betrogen, betrügt man genau einmal. Damit kann man keine einzige Spielserie wirklich gewinnen, weil man immer mindestens so viele gefüllte Koffer herausgibt, wie man bekommen hat. Man kann nach 100 Spielen maximal auf 0 kommen, weil man selbst in Vorkasse geht und jeden Koffer, den man gefüllt bekommen hat, beim nächsten Spiel zurückgibt. Man wird jede Spielserie bestenfalls unentschieden für sich entscheiden.

Und trotzdem hat tit for tat in der Gesamtsicht jeder gegen jeden gewonnen.

Und ergreifenderweise scheint tit for tat auch im Umgang von Mafiosi miteinander die beste Strategie zu sein, obwohl keine dabei gewinnen kann. Ist aber unter Mafiosi tit for tat die beste Verhaltensstrategie, so erklärt das sogar die Blutrache als effektive Strategie: Bringst Du einen von meinen um, bringe ich einen von Deinen um. (der einzige Haken ist, dass man nicht mit Spielgeld sondern mit Leuten spielt, und die, die umgelegt werden, sicherlich nicht mehr als Gewinner dastehen können, aber aus Sicht der Bosse sind das ja nur Spielfiguren). Also ist es sogar tatsächlich sinnvoll, Blutrache zu üben und einen von den anderen umzulegen. Und so hin und her.

Der Knaller ist, dass sie übergangslos von Mafiosi zu Professoren und deren Verhalten in Prüfungen springen:

Ähnlich strukturiert sei eine von der Camorra organisierte illegale Lotterie: Gewinne werden zuverlässig ausgezahlt, damit der gute Ruf erhalten bleibt. Eine ähnliche Mentalität sei sogar in akademischen Kreisen zu finden, mahnt Gambetta: An italienischen Universitäten sei es üblich, dass Professoren die Studenten anderer Professoren in Prüfungen durchwinken, mit der berechtigten Erwartung, dass auch die eigenen Studenten bei den Kollegen reüssieren. Dieses System permanenter Gegenleistung werde von ausscheidenden Hochschullehrern sogar auf deren Nachfolger übertragen.

Universitätsprofessoren verhalten sich wie die Camorra. Nicht nur in Italien, hier in Deutschland läuft das genauso. Da nickt auch jeder als Zweitprüfer ab, was der Erstgutachter will, um auf Gegenseitigkeit den eigenen Prüfling durchzubekommen. Oder eben beim Peer Review. Würde man das Paper der anderen kritisieren, würde dann das eigene auch abgesägt.

Das heißt, es geht beim Peer Review und bei Promotionsprüfungen nicht darum, wissenschaftlich zu arbeiten, sondern tit for tat zu spielen.

Und dieses Camorra-Prinzip habe ich ja kürzlich noch woanders gefunden: Bei der Wahl von Verfassungsrichtern durch den Bundestag.

Da werden Kandidaten auch nicht geprüft, sondern jede Partei bringt nach Parteienproporz ihren Kandidaten, und die anderen halten das Maul, um im Gegenzug ihren Kandidaten durchzubringen. tit for tat.

Oder wie in der Camorra.

Nachtrag: Zu tit for tat ein Video, in dem Richard Dawkins das Spiel und tit for tat erklärt:

Nachtrag 2/Korrektur: Ein kleiner Fehler ist mir unterlaufen (ist ja immerhin nun auch schon über 25 Jahre her, dass ich während des Informatik-Studiums davon gehört hatte). Der Fehler lag darin, dass man im Falle der Kooperation einen kleinen Gewinn einstreicht, der aber geringer als beim Betrug ist, wenn man dabei nicht selbst betrogen hat. Die Spielkategorie ist übrigens nicht auf das Gefangenendilemma beschränkt, sondern eben – deshalb auch die Sache mit den Koffern – jedes Spiel, bei dem man iteriert blind aber rückblickend ein Spiel mit gleichzeitigen Aktionen spielt.

Um es ganz allgemein zu formulieren schaut mal in diese Foliensammlung (von einem der Erfinder dieser spieltheoretischen Spielreihen) und darin Seite 11 ff. (Computer Tournaments). Und dort die Payoff-Matrix auf Seite 13. Eine ganze Klasse von Spielen lässt sich mit dieser Matrix-Darstellung beschreiben.

22 Kommentare (RSS-Feed)

Tom
10.7.2013 23:38
Kommentarlink

das nennt man in der Politik “Checks and Balances”


Henning
10.7.2013 23:53
Kommentarlink

Hallo Hadmut,
ich kann mich grob an einen Artikel in der Scientific American zur erfolgreichsten Spielvariante erinnern. Meines Wissens hatte damals aber nicht Tit for Tat gewonnen, sondern tatsächlich eine leicht abgewandelte Version, die manchmal betrügt. Reines Tit For Tat war aber zweitbeste Strategie.


Foobar
11.7.2013 0:17
Kommentarlink

Das Experiment mit den Koffern verstehe ich nicht.

Wenn man unter den von dir beschriebenen Bedingungen einfach immer betruegt, kommt man doch im schlechtesten Fall auf 0 raus, was dem besten Fall der tit-for-tat methode entspricht.

Einleuchtender find ich da schon das Gefangenenparadox:

http://de.wikipedia.org/wiki/Gefangenenparadoxon


Hanz Moser
11.7.2013 0:45
Kommentarlink

Ähhh, such noch mal nach den Spielregeln, bitte.

Dass tit for that mit den von dir angegebenen Regeln besser abschneiden würde als konsequentes Betrügen ergibt keinen Sinn. Da muss bei den Regeln noch irgendeine Einschränkung vorhanden gewesen sein.


Hadmut
11.7.2013 0:58
Kommentarlink

Alex
11.7.2013 0:45
Kommentarlink

Die sind letztlich alle mehr oder weniger identisch die Spiele.

Allerdings funktionieren tit-for-tat oder ähnliche strategien nur bei (potenziell) endlosen spielen.
Sobald ein spiel endlich ist, gibt es einen nash’shen fixpunkt, und der ist dann optimal (bei 100spielen wäre das immer betrügen, wie sich sofort induktiv zeigen lässt)


[…] habe ich den Artikel bei Hardmut Danisch über »tit for tat« gelesen und dort wird auf einen Artikel bei der SZ verlink der da lautet: Auch Verbrecher brauchen […]


Hanz Moser
11.7.2013 2:41
Kommentarlink

Soweit ich das überflogen habe ist in den Quellen das Ergebnis von beidseitiger Kooperation besser als von beidseitigem Betrug. Also das klassische Prisoner’s Dilemma. Der dritte Link sagt deutlich, dass das Problem bei rational agierenden einzelnen Agenten ist, dass sie das gewichtete Risiko der Ergebnisse minimieren und daher immer petzen, obwohl durchgehende Kooperation besser wäre.

Das ist ein himmelweiter Unterschied zu deinem Beispiel, in dem beidseitige Kooperation keinen Vorteil bringt, sondern ein Vorteil ausschließlich durch Betrug zu erreichen ist und Kooperation nie ein Vorteil sein kann.

Lies noch mal was du geschrieben hast. Entweder du hattest einen Aussetzer beim Schreiben oder du hast es nicht begriffen.


Hadmut
11.7.2013 20:58
Kommentarlink

@Hanz:

> Das ist ein himmelweiter Unterschied zu deinem Beispiel,

Nein, ein einziger Parameter (der Payoff bei Kooperation) war falsch angegeben.

> Lies noch mal was du geschrieben hast. Entweder du hattest einen Aussetzer beim Schreiben oder du hast es nicht begriffen.

Wegen einem Schreib-/Flüchtigkeitsfehler? Sieh Dir bitte den Nachtrag oben an.


kokko
11.7.2013 4:24
Kommentarlink

“Damit kann man keine einzige Spielserie wirklich gewinnen, weil man immer mindestens so viele gefüllte Koffer herausgibt, wie man bekommen hat.”

in deinem kofferbeispiel
wenn man gegen jemanden spielt der immer betrügt, man selbst aber tit-for-tat mit kooperieren beim ersten mal spielt

dann steht es doch am ende des spiels +1 zu -1 für den gegner dh man selbst verliert. oder hab ich da was falsch gelesen?

+
seit wann agiert die mafia bitte nach tit-for-tat oder war das nur auf ganz bestimmte situationen bezogen?


DerdieBuchstabenzählt
11.7.2013 7:20
Kommentarlink

Also, wenn ich zB die CDU wäre, dann wäre die Baer für mich ein Betrugskoffer der Grünen. Aber wahrscheinlich sind die zu blöd, oder selber schon feministisch durchseucht.Ich frage mich warum die sich überhaupt zu so einer “Wahl” treffen? Sitzungsgelder, so tun als ob oder nur um die rechtlichen Vorgaben einzuhalten?

Die fordern sogar öffentlich ein solches Verhalten:

1999, EU Kommissarin Michaele Schreyer

>Ihre Berufung stieß auf Protest der Opposition im Bund (CDU/CSU und FDP), da mit ihr und Günter Verheugen (SPD) zwei Mitglieder der Regierungsparteien EU-Kommissare wurden. Zuvor war es üblich, dass einer der beiden Kommissare der Opposition angehörte.<

http://de.wikipedia.org/wiki/Michaele_Schreyer

Ob da eine Rache folgte weiß ich nicht.


Hadron
11.7.2013 9:30
Kommentarlink

Zitat aus dem dritten Link bestätigt Alex’ Feststellung:
“Playing the prisoner’s dilemma with a fixed, finite, pre-determined, commonly known number of rounds, defection is the best strategy”
(Zitat aus dem dritten Link)

Bei fest vorgegebener und beiden Teilnehmern bekannter Anzahl der Wiederholungen (hier: n=100), ist die optimale Strategie immer “betrügen”. Die Überlegung geht so: Die Strategie “betrügen” dominiert die Strategie “nicht betrügen”. Selbst wenn rational denkende Teilnehmer 99 mal aus Vorsicht oder Angst vor Bestrafung immer kooperieren, werden sie daher beim letzten Mal die Strategie “betrügen” wählen. Das letzte Verhalten kann schließlich nicht mehr heimgezahlt werden.

Wenn beide Teilnehmer aber wissen, dass beim letzten Mal rational immer “betrügen” gewählt wird, kann die gleiche Überlegung auch auf das vorletzt Mal angewandt werden, also ist auch hier “betrügen” optimal usw.

Sobald die Anzahl von Wiederholungen beiden Teilnehmern unbekannt ist, ergibt sich spieltheoretisch eine andere Situation, in der “betrügen” nicht mehr notwendig optimal ist. Letzteres sollte als Botschaft in die Ellenbogengesellschaft hineingebracht werden.

Das eigentlich interessante aber ist, finde ich, das Verhalten der Camorra mit Professorenverhalten zu vergleichen. »Nimmst du meinen Studi, nehm’ ich deinen Studi« – Kooperatives Verhalten, weil keiner genau weiß, wie oft sich dieses unsaubere Spielchen wiederholen wird? Oder weil gilt: »Nimmst du meinen Studi nicht, rufe ich kurz bei der Camorra an…«


Jeff
11.7.2013 12:03
Kommentarlink

Da fällt mir diese interessante Dokumentation über den Zusammenhang von Spieltheorie, John Nash und dem Wirtschaftssystem ein:
http://www.youtube.com/watch?v=3fSCRxoEdj0

Hier die Regeln zu “Fuck you buddy” aka “So long sucker”. Bisher konnte ich leider noch nicht genug Leute finden, die das mal spielen wollen. https://en.wikipedia.org/wiki/So_Long_Sucker


egon
11.7.2013 13:24
Kommentarlink

Toll. Alltägliche Binsenweisheiten wissenschaftlich aufgeladen.
tit for tat, “informatik”, “spieltheorie”, “dawkins”,…. oh mann, gehts noch danisch?
Welche Sensation findet Herr Danisch als näcstes? Im Sommer ist es warm?


Hadmut
11.7.2013 14:18
Kommentarlink

@egon:

> oh mann, gehts noch danisch?

Och, es geht eigentlich. Mmmh. Ja. Geht noch ne Weile.


DerdieBuchstabenzählt
11.7.2013 14:00
Kommentarlink

@Hadron

>Das eigentlich interessante aber ist, finde ich, das Verhalten der Camorra mit Professorenverhalten zu vergleichen.Das letzte Verhalten kann schließlich nicht mehr heimgezahlt werden.<

Doch, der Prof. könnte zB seinen Nachfolger einweisen sich zu rächen
(steht übrigens auch im Zitat das Hadmut gebracht hat) oder aus Wut das ganze System auffliegen lassen.

Das bedeutet die "Spiele" haben eben keine Ende! Sowohl der Mafiosi als auch der Prof. haben jeweils Nachfolger.


Alter Knacker
11.7.2013 20:43
Kommentarlink

tit for tat. Solange bis einer die Regeln einseitig ändert.
Im Spiel nicht möglich in der Realität schon. Eine kleine “Bombe”
im Koffer kann zu großer Heiterkeit anregen. *eg*


Hanz Moser
11.7.2013 22:17
Kommentarlink

@ Hadmut

>Nein, ein einziger Parameter (der Payoff bei Kooperation) war falsch angegeben.
Ja, aber auf genau DEN kommt es an 😉

>Wegen einem Schreib-/Flüchtigkeitsfehler? Sieh Dir bitte den Nachtrag oben an.
Wenn es nur ein Schreibfehler gewesen wäre, hätte es dir sofort mit dem Kommentar von foobar klar sein müssen, spätestens aber beim Überfliegen der Quellenlinks.

Solche Aussetzer passieren aber jedem Mal. Zeig mir einen Programmierer, der nicht gelegentlich vor seinem Quellcode sitzt und einfachste Fehler für Minuten (oder länger) übersieht…


Hadmut
11.7.2013 23:48
Kommentarlink

@Hanz: Es war mir auch sofort klar.

Nur nimm gefälligst zur Kenntnis, dass ich tagsüber arbeite und vom Arbeitsplatz nicht blogge. Ich habe mit dem iPad aus der U-Bahn ein paar Kommentare moderiert, aber nach Schreiben des Kommentars bis zur Ergänzung keine Gelegenheit gehabt, etwas zu schreiben.

> Solche Aussetzer passieren aber jedem Mal.

Rutsch mir den Buckel runter.


Nicht ganz ontopic, aber dennoch interessant:
http://i.imgbox.com/abqm8TjV.jpg


[…] zwei unterschiedlichen Blogs war gerade die Rede von Vertrauen: Bei Hadmut Danisch und Felix Schwenzel. Zwei sehr unterschiedlichen Blogs. Hartmut Danish nahm die Feder auf, dass […]


silver price
16.7.2013 0:35
Kommentarlink

Da diese Definition der kollektiven Stabilität unabhängig von der Höhe der Auszahlungen ist, lässt sie sich auch auf das iterierte Gefangenendilemma mit variierenden Auszahlungen anwenden. Unsere Frage lautet dann: Gibt es auch bei variierenden Auszahlungen kooperative Strategien, die kollektiv stabil sind? Unter einer kooperativen Strategie verstehe ich dabei eine Strategie, die nicht unmotiviert defektiert, so dass jede hinreichend freundlich gesonnene Gegnerstrategie jederzeit mit ihr kooperieren kann. Tit for Tat ist in diesem Sinne eine kooperative Strategie. Wie Axelrod bewiesen hat (Axelrod 1984, Anhang B), ist Tit for Tat im iterierten Gefangenendilemma mit gleichbleibenden Auszahlungen kollektiv stabil.