Trennung zwischen grobkorrelierten Gleichgewichten und korrelierten Gleichgewichten

16

Ich suche nach Beispielen für Techniken zum Nachweis des Preises von Anarchiegrenzen, die die Fähigkeit haben, den Preis der Anarchie über grobkorrelierte Gleichgewichte (die begrenzte Menge der Dynamik ohne äußeres Bedauern) vom Preis der Anarchie über korrelierte Gleichgewichte (die Begrenzung) zu trennen Satz von No-Swap-Regret-Dynamiken). Sind natürliche Separationen dieser Art bekannt?

Ein Hindernis für die Trennung dieser beiden Klassen besteht darin, dass der natürlichste (und häufigste) Weg, den Preis von Anarchiegrenzen zu beweisen, darin besteht, nur zu beobachten, dass kein Spieler im Gleichgewicht einen Anreiz hat, von seiner Aktion bei OPT abzuweichen und dies auf irgendeine Weise zu nutzen die soziale Wohlfahrt in einer bestimmten Konfiguration mit der sozialen Wohlfahrt von OPT zu verbinden. Leider gilt jeder Beweis, dass der Preis für Anarchie über grobkorrelierte Gleichgewichte klein ist und dass nur Abweichungen jedes Spielers von einer einzelnen alternativen Aktion (z. B. der Aktion von OPT) berücksichtigt werden müssen, auch für korrelierte Gleichgewichte und kann daher keine Trennung liefern. Dies liegt daran, dass der einzige Unterschied zwischen einem grobkorrelierten Gleichgewicht und einem korrelierten Gleichgewicht die Fähigkeit eines Spielers in einem korrelierten Gleichgewicht ist, gleichzeitig zu berücksichtigenMehrfache Abweichungen, bedingt durch sein Signal des aus der Gleichgewichtsverteilung gezogenen Spielprofils.

Sind solche Trennungen bekannt?

Aaron Roth
quelle

Antworten:

7

Repariere M >> 1 >> e und sieh dir das folgende Zwei-Spieler-Koordinationsspiel an (beide Spieler erhalten dasselbe Dienstprogramm):

M   | 1+e  | 2e   |  e

1+e |  1   |  e   |  0

2e  |  e   |  M   | 1+e

e   |  0   | 1+e  | 1

Die zweite und vierte Reihe und Spalte sind streng dominiert, so dass sie bei keinem korrelierten Gleichgewicht unterstützt werden können. Dies würde sich also auf das Teilspiel beziehen:

M  |  2e

2e |  M

für die jedes korrelierte Gleichgewicht jedem Spieler mehr als M / 2 Nutzen bringen würde.

Betrachten Sie andererseits die gemeinsame Wahrscheinlichkeitsverteilung, die jedem der Einsen die Wahrscheinlichkeit 1/2 und damit jedem Spieler die Nützlichkeit 1 verleiht. Die Behauptung ist, dass dies ein grobes Gleichgewicht ist. In einem groben Gleichgewicht sind die möglichen Abweichungen des Reihenspielers zu einer der reinen Strategien unabhängig vom Ergebnis der gemeinsamen Verteilung. Wenn nur bekannt ist, dass sich der Spaltenspieler gleichmäßig zwischen der 2. und 4. Spalte mischt, ist der maximale Nutzen, den der Reihenspieler erhalten kann, 0,5 + e <1, sodass eine Abweichung nicht rentabel ist.

Noam
quelle