Strategieresistenz

Im Mechanismusdesign bezeichnet man als strategiesicheren (SP) Mechanismus eine Spielform, in der jeder Spieler eine schwach dominante Strategie besitzt , sodass kein Spieler durch „Spionieren“ der anderen Spieler einen Vorteil erlangen kann. Besitzen die Spieler private Informationen (z. B. ihren Typ oder ihren Wert für ein bestimmtes Objekt) und besteht der Strategieraum jedes Spielers aus den möglichen Informationswerten (z. B. möglichen Typen oder Werten), so ist ein wahrheitsgemäßer Mechanismus ein Spiel, in dem die Offenlegung der wahren Informationen für jeden Spieler eine schwach dominante Strategie darstellt. ^{[ 1 ] : 244} Ein SP-Mechanismus wird auch als dominant-strategie-anreizkompatibel (DSIC) bezeichnet , ^{[ 1 ] : 415} um ihn von anderen Arten der Anreizkompatibilität zu unterscheiden .

Ein SP-Mechanismus ist immun gegen Manipulationen durch einzelne Spieler (nicht aber durch Koalitionen). Im Gegensatz dazu kann in einem gruppenstrategieresistenten Mechanismus keine Gruppe ihre Präferenzen so verfälschen, dass alle Mitglieder bessergestellt sind. In einem stark gruppenstrategieresistenten Mechanismus kann keine Gruppe ihre Präferenzen so verfälschen, dass mindestens ein Mitglied der Gruppe bessergestellt ist, ohne dass die übrigen Mitglieder schlechtergestellt sind. ^{[ 2 ]}

Typische Beispiele für SP-Mechanismen sind:

• eine Mehrheitsentscheidung zwischen zwei Alternativen;
• eine Zweitpreisauktion , bei der die Teilnehmer einen quasilinearen Nutzen haben ;
• ein VCG-Mechanismus , wenn die Teilnehmer einen quasilinearen Nutzen haben

Typische Beispiele für Mechanismen, die keine SP sind, sind:

• jede deterministische, nicht-diktatorische Wahl zwischen drei oder mehr Alternativen;
• eine Auktion zum Erstpreis

Das Prinzip der Sparsamkeit (SP) ist auch beim Netzwerk-Routing anwendbar . Man stelle sich ein Netzwerk als Graph vor , in dem jeder Kante (d. h. Verbindung) Übertragungskosten zugeordnet sind , die dem Inhaber der Verbindung bekannt sind. Der Inhaber einer Verbindung möchte für die Weiterleitung von Nachrichten vergütet werden. Als Absender einer Nachricht im Netzwerk möchte man den kostengünstigsten Pfad finden. Dafür gibt es effiziente Methoden, selbst in großen Netzwerken. Es besteht jedoch ein Problem: Die Kosten für jede Verbindung sind unbekannt. Ein naiver Ansatz wäre, den Inhaber jeder Verbindung nach den Kosten zu fragen, anhand dieser angegebenen Kosten den kostengünstigsten Pfad zu finden und alle Verbindungen auf diesem Pfad mit ihren angegebenen Kosten zu bezahlen. Es lässt sich jedoch zeigen, dass dieses Zahlungsmodell nicht dem Prinzip der Sparsamkeit (SP) entspricht, d. h., die Inhaber einiger Verbindungen können durch falsche Angaben zu den Kosten einen Vorteil erlangen. Wir könnten am Ende weit mehr bezahlen als die tatsächlichen Kosten. Es lässt sich zeigen, dass unter bestimmten Annahmen über das Netzwerk und die Teilnehmer (Inhaber von Verbindungen) eine Variante des VCG-Mechanismus dem Prinzip der Sparsamkeit (SP) entspricht.

Es gibt eine Reihe möglicher Ergebnisse. ${\displaystyle X}$

Es gibt Akteure, die jedem Ergebnis unterschiedliche Bewertungen zuweisen. Die Bewertung eines Akteurs wird als Funktion dargestellt: ${\displaystyle n}$${\displaystyle i}$

${\displaystyle v_{i}:X\longrightarrow R_{+}}$

wobei der Wert, den es jeder Alternative beimisst, in Geldeinheiten ausgedrückt wird.

Es wird angenommen, dass die Agenten quasilineare Nutzenfunktionen haben; das bedeutet, dass, wenn das Ergebnis ist und der Agent zusätzlich eine Zahlung (positiv oder negativ) erhält, der Gesamtnutzen des Agenten wie folgt lautet: ${\displaystyle x}$${\displaystyle p_{i}}$${\displaystyle i}$

${\displaystyle u_{i}:=v_{i}(x)+p_{i}}$

Der Vektor aller Wertfunktionen wird mit bezeichnet . ${\displaystyle v}$

Für jeden Agenten wird der Vektor aller Wertfunktionen der anderen Agenten mit bezeichnet . Also . ${\displaystyle i}$${\displaystyle v_{-i}}$${\displaystyle v\equiv (v_{i},v_{-i})}$

Ein Mechanismus ist ein Funktionspaar:

• Eine Funktion, die als Eingabe den Wertvektor entgegennimmt und ein Ergebnis zurückgibt (sie wird auch als soziale Entscheidungsfunktion bezeichnet);${\displaystyle Outcome}$${\displaystyle v}$${\displaystyle x\in X}$
• Eine Funktion, die als Eingabe den Wertvektor nimmt und einen Vektor von Zahlungen zurückgibt, der bestimmt, wie viel jeder Spieler erhalten soll (eine negative Zahlung bedeutet, dass der Spieler einen positiven Betrag zahlen soll).${\displaystyle Payment}$${\displaystyle v}$${\displaystyle (p_{1},\dots ,p_{n})}$

Ein Mechanismus heißt strategiefest, wenn für jeden Spieler und für jeden Wertvektor der anderen Spieler gilt : ${\displaystyle i}$${\displaystyle v_{-i}}$

${\displaystyle v_{i}(Outcome(v_{i},v_{-i}))+Payment_{i}(v_{i},v_{-i})\geq v_{i}(Outcome(v_{i}',v_{-i}))+Payment_{i}(v_{i}',v_{-i})}$

Es ist hilfreich, einfache Bedingungen zu haben, um zu überprüfen, ob ein gegebener Mechanismus SP ist oder nicht. Dieser Unterabschnitt zeigt zwei einfache Bedingungen, die sowohl notwendig als auch hinreichend sind.

Wenn ein Mechanismus mit Geldtransfers SP ist, dann muss er für jeden Agenten die folgenden zwei Bedingungen erfüllen : ^{[ 1 ] : 226} ${\displaystyle i}$

1. Die Zahlung an Agent i ist eine Funktion des gewählten Ergebnisses und der Bewertungen der anderen Agenten – jedoch keine direkte Funktion der eigenen Bewertung des Agenten . Formal existiert eine Preisfunktion , die als Eingabe ein Ergebnis und einen Bewertungsvektor für die anderen Agenten entgegennimmt und die Zahlung an Agent i zurückgibt , sodass für jedes i gilt: ${\displaystyle i}$${\displaystyle v_{-i}}$${\displaystyle v_{i}}$${\displaystyle Price_{i}}$${\displaystyle x\in X}$${\displaystyle v_{-i}}$${\displaystyle i}$${\displaystyle v_{i},v_{i}',v_{-i}}$

${\displaystyle Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})}$

Dann:

${\displaystyle Payment_{i}(v_{i},v_{-i})=Payment_{i}(v_{i}',v_{-i})}$

BEWEIS: Wenn dann ein Agent mit Bewertungskennzeichen bevorzugt die Meldung , da sie ihm das gleiche Ergebnis und eine höhere Zahlung einbringt; ebenso bevorzugt ein Agent mit Bewertungskennzeichen die Meldung . ${\displaystyle Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})}$${\displaystyle v_{i}'}$${\displaystyle v_{i}}$${\displaystyle Payment_{i}(v_{i},v_{-i})<Payment_{i}(v_{i}',v_{-i})}$${\displaystyle v_{i}}$${\displaystyle v_{i}'}$

Daraus folgt, dass eine „Preisschild“-Funktion existiert , die als Eingabe ein Ergebnis und einen Bewertungsvektor für die anderen Agenten entgegennimmt und die Zahlung für Agent zurückgibt. Für jedes gilt: ${\displaystyle Price_{i}}$${\displaystyle x\in X}$${\displaystyle v_{-i}}$${\displaystyle i}$${\displaystyle v_{i},v_{-i}}$

${\displaystyle Outcome(v_{i},v_{-i})=x}$

Dann:

${\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})}$

2. Das gewählte Ergebnis ist für Agent optimal , unter Berücksichtigung der Wertvorstellungen der anderen Agenten. Formal: ${\displaystyle i}$

${\displaystyle Outcome(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Price_{i}(x,v_{-i})]}$

wobei die Maximierung über alle Ergebnisse im Bereich von erfolgt . ${\displaystyle Outcome(\cdot ,v_{-i})}$

BEWEIS: Wenn es ein anderes Ergebnis gibt , sodass , dann bevorzugt ein Agent mit der Bewertung die Meldung von , da ihm dies einen größeren Gesamtnutzen verschafft. ${\displaystyle x'=Outcome(v_{i}',v_{-i})}$${\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})}$${\displaystyle v_{i}}$${\displaystyle v_{i}'}$

Die Bedingungen 1 und 2 sind nicht nur notwendig, sondern auch hinreichend: Jeder Mechanismus, der die Bedingungen 1 und 2 erfüllt, ist SP.

NACHWEIS: Einen Makler beauftragen und Wertgutachten erstellen lassen . Hinweis: ${\displaystyle i}$${\displaystyle v_{i},v_{i}',v_{-i}}$

${\displaystyle x:=Outcome(v_{i},v_{-i})}$- das Ergebnis, wenn der Agent wahrheitsgemäß handelt.

${\displaystyle x':=Outcome(v_{i}',v_{-i})}$- das Ergebnis, wenn der Agent unwahrhaftig handelt.

Nach Eigenschaft 1 ist der Nutzen des Agenten bei wahrheitsgemäßem Verhalten:

${\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})}$

und der Nutzen des Agenten, wenn er unwahrhaftig handelt, ist:

${\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})}$

Gemäß Eigenschaft 2:

${\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')}$

Daher ist es für den Akteur eine dominante Strategie, wahrheitsgemäß zu handeln.

Das eigentliche Ziel eines Mechanismus ist seine Funktion; die Zahlungsfunktion ist lediglich ein Mittel, um die Spieler zu wahrheitsgemäßem Verhalten zu bewegen. Daher ist es nützlich zu wissen, ob eine bestimmte Ergebnisfunktion mithilfe eines SP-Mechanismus implementiert werden kann oder nicht (diese Eigenschaft wird auch als Implementierbarkeit bezeichnet ). ${\displaystyle Outcome}$

Die Monotonieeigenschaft ist für die Strategiefestigkeit notwendig.

Ein Ein-Parameter-Bereich ist ein Spiel, in dem jeder Spieler einen bestimmten positiven Wert für „Gewinn“ und den Wert 0 für „Verlieren“ erhält. Ein einfaches Beispiel ist eine Auktion mit einem einzigen Gegenstand, bei der der Wert, den der Spieler dem Gegenstand zuweist, n ist. ${\displaystyle i}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle i}$

In diesem Kontext lassen sich wahrheitsgemäße Mechanismen leicht charakterisieren. Beginnen wir mit einigen Definitionen.

Ein Mechanismus heißt normalisiert , wenn jedes verlorene Gebot 0 auszahlt.

Ein Mechanismus heißt monoton , wenn sich die Gewinnchancen eines Spielers (schwach) erhöhen, wenn er sein Gebot erhöht.

Bei einem monotonen Mechanismus gibt es für jeden Spieler i und jede Kombination von Geboten der anderen Spieler einen kritischen Wert , bei dem der Spieler vom Verlieren zum Gewinnen wechselt.

Ein normierter Mechanismus auf einem Einparameterbereich ist wahrheitsgemäß, wenn die folgenden beiden Bedingungen erfüllt sind: ^{[ 1 ] : 229–230}

1. Die Zuordnungsfunktion ist in jedem der Gebote monoton, und:
2. Bei jedem erfolgreichen Gebot wird der kritische Wert entrichtet.

Es gibt verschiedene Möglichkeiten, den Begriff der Wahrhaftigkeit auf randomisierte Mechanismen auszudehnen. Diese sind, von der stärksten zur schwächsten,: ^{[ 3 ] : 6–8}

• Universelle Wahrhaftigkeit : Bei jeder Randomisierung des Algorithmus ist der resultierende Mechanismus wahrheitsgemäß. Anders ausgedrückt: Ein universell wahrheitsgemäßer Mechanismus ist eine Randomisierung deterministischer wahrheitsgemäßer Mechanismen, wobei die Gewichte eingabeabhängig sein können.
• Starke stochastische Dominanz der Wahrhaftigkeit (starke SD-Wahrhaftigkeit) : Der Wahrscheinlichkeitsvektor, den ein Agent durch wahrheitsgemäßes Verhalten erhält, besitzt stochastische Dominanz erster Ordnung gegenüber dem Wahrscheinlichkeitsvektor, den er durch falsche Angaben erhält. Das heißt: Die Wahrscheinlichkeit, die höchste Priorität zu erhalten, ist mindestens genauso hoch, ebenso wie die Wahrscheinlichkeit, eine der beiden höchsten Prioritäten zu erhalten, und … die Wahrscheinlichkeit, eine der m höchsten Prioritäten zu erhalten, ist mindestens genauso hoch.
• Lexikographische Wahrhaftigkeit (lex-Wahrhaftigkeit) : Der Wahrscheinlichkeitsvektor, den ein Akteur durch wahrheitsgemäßes Verhalten erhält, ist lexikographisch dominant gegenüber dem Wahrscheinlichkeitsvektor, den er durch falsche Angaben erhält. Das heißt: Die Wahrscheinlichkeit, die höchste Priorität zu erhalten, ist höher ODER (die Wahrscheinlichkeit, die höchste Priorität zu erhalten, ist gleich, und die Wahrscheinlichkeit, eine der beiden höchsten Prioritäten zu erhalten, ist höher) ODER (die Wahrscheinlichkeit, die ersten m - 1 Prioritäten zu erhalten, ist gleich, und die Wahrscheinlichkeit, eine der m höchsten Prioritäten zu erhalten , ist höher) ODER (alle Wahrscheinlichkeiten sind gleich).
• Schwache stochastische Dominanz der Wahrhaftigkeit (schwache SD-Wahrhaftigkeit) : Der Vektor der Wahrscheinlichkeiten, die ein Akteur durch wahrheitsgemäßes Handeln erhält, wird nicht erster Ordnung stochastisch von dem Vektor der Wahrscheinlichkeiten dominiert, die er durch falsche Berichterstattung erhält.

Universal impliziert starke SD impliziert Lex impliziert schwache SD, und alle Implikationen sind strikt. ^{[ 3 ] : Thm. 3.4}

Für jede Konstante wird ein randomisierter Mechanismus mit Wahrscheinlichkeit als wahrheitsgemäß bezeichnet , wenn für jeden Agenten und jeden Gebotsvektor die Wahrscheinlichkeit, dass der Agent durch nicht wahrheitsgemäßes Bieten einen Vorteil erlangt, höchstens beträgt , wobei die Wahrscheinlichkeit über die Zufälligkeit des Mechanismus berechnet wird. ^{[ 1 ] : 349} ${\displaystyle \epsilon >0}$${\displaystyle 1-\epsilon }$${\displaystyle \epsilon }$

Wenn die Konstante mit zunehmender Anzahl der Bieter gegen 0 strebt, spricht man von einem Mechanismus mit hoher Wahrscheinlichkeit für wahrheitsgemäße Ergebnisse . Dieses Kriterium ist zwar schwächer als die vollständige Wahrhaftigkeit, aber in manchen Fällen dennoch nützlich; siehe z. B. Konsensschätzung . ${\displaystyle \epsilon }$

Eine neue Betrugsart, die mit der Vielzahl internetbasierter Auktionen immer häufiger auftritt, sind Gebote unter falschem Namen – Gebote, die von einem einzelnen Bieter unter Verwendung mehrerer Kennungen wie beispielsweise mehrerer E-Mail-Adressen abgegeben werden.

Falschnamenresistenz bedeutet, dass für keinen der Spieler ein Anreiz besteht, Falschnamengebote abzugeben. Dies ist ein stärkeres Konzept als Strategieresistenz. Insbesondere die Vickrey-Clarke-Groves -Auktion (VCG-Auktion) ist nicht falschnamenresistenz. ^{[ 4 ]}

Die Immunität gegen falsche Namen unterscheidet sich wesentlich von der Immunität gegen Gruppenstrategien, da sie davon ausgeht, dass ein Individuum allein bestimmte Verhaltensweisen simulieren kann, die normalerweise die kollusive Koordination mehrerer Personen erfordern.

Offensichtliche Strategieunempfindlichkeit (OSP) ist eine Verstärkung der Strategieunempfindlichkeit, die die Robustheit der Strategieunempfindlichkeit gegenüber kognitiv eingeschränkten Agenten erfasst. ^{[ 5 ]}

Die verdeckte Zweitpreisauktion ist strategieresistent, aber nicht offensichtlich strategieresistent, da die Bieter darauf vertrauen müssen, dass ihre Gebote verdeckt bleiben. ^{[ 6 ] [ 7 ]} Im Gegensatz dazu ist die aufsteigende Uhrenauktion offensichtlich strategieresistent, ^{[ 5 ]} obwohl die beiden Auktionen für vollständig rationale Akteure äquivalent sind. Weitere Beispiele für strategieresistente, aber nicht offensichtlich strategieresistente Mechanismen sind:

• Mehrheitsentscheidung zwischen zwei Alternativen;
• Aufgeschobene Annahme ^{[ 8 ]}
• Top-Handelszyklen

• Anreizkompatibilität
• Offensichtliche Strategieresistenz – eine Stärkung der Strategieresistenz
• Individuelle Rationalität
• Teilnahmekriterium – ein Spieler kann durch die Teilnahme am Spiel nicht verlieren (d. h. ein Spieler hat keinen Anreiz, die Teilnahme am Spiel zu vermeiden).

• Parkes, David C. (2004), On Learnable Mechanism Design, in: Tumer, Kagan und David Wolpert (Hrsg.): Collectives and the Design of Complex Systems, New York uaO, S. 107–133.
• Zur asymptotischen Strategiefestigkeit klassischer sozialer Entscheidungsregeln. Ein Artikel von Arkadii Slinko über Strategiefestigkeit in Wahlsystemen.