Verständnis eines Mechanismus-Design-Beweises

Ich habe mit den technischen Details eines Beweises für die Auktionstheorie in diesem Artikel zu kämpfen: http://users.eecs.northwestern.edu/~hartline/omd.pdf

Insbesondere Satz 2.5: Die notwendigen und ausreichenden Bedingungen für einen wahrheitsgemäßen Mechanismus.

Noch genauer gesagt, die Vorwärtsrichtung des Beweises auf Seite 6. Wenn der Autor einen wahrheitsgemäßen Wert als und einen allgemeinen, möglicherweise falschen Wert (z. B. ein Gebot) als , postuliert er zwei zusätzliche Mengen: und . $v_i$ $b_i$ $z_1$ $z_2$

Er legt dann fest, dass , , was eine Ungleichung ergibt, die auf der vorherigen Arbeit des Papiers basiert. $v_i = z_1$ $b_i = z_2$

Er legt auch fest, dass , , was eine ähnliche, aber unterschiedliche Ungleichung ergibt, die auf der vorherigen Arbeit des Papiers basiert. $v_i = z_2$ $b_i = z_1$

Okay, fair genug. Dann subtrahiert er eine Ungleichung von der anderen und leitet sein gewünschtes Ergebnis auf der Grundlage der konsequenten Algebra ab. Ich verstehe nicht, warum diese Subtraktion gerechtfertigt ist - er scheint zwei Ungleichungen zu subtrahieren, die auf völlig unterschiedlichen (tatsächlich entgegengesetzten) Annahmen beruhen, und jedes Mal, wenn ich sie sehe, werde ich gewaltsam aus dem Gedankengang geworfen.

Ich bin mir ziemlich sicher, dass ich diesen grundlegenden Ansatz anders gesehen habe (Shoham und Leyton-Browns Buch? Ich habe es nicht in der Nähe, um es zu überprüfen), also scheint es eine verbreitete Idee zu sein, aber ich komme nicht daran vorbei. Kann mir jemand helfen zu verstehen, warum das gültig ist, oder mir erklären, was mir fehlt?

(Ich habe versucht, das gewünschte Ergebnis zu beweisen, indem ich drei Werte angenommen habe - einen wahren Wert und zwei Gebote, und -, um sein gewünschtes Ergebnis zu erhalten, bin aber auch gescheitert. Es kann also nicht nur üblich, sondern auch notwendig sein mach es auf die Weise des Autors. Aber ich verstehe es immer noch nicht.) $v_i$ $b_1$ $b_2$

Update: Ich wusste, dass ich in Shoham und Leyton-Browns Buch etwas Ähnliches gesehen hatte . Es ist nicht genau dasselbe, aber es ist sehr ähnlich und behandelt dieselbe Gleichung und denselben Gegenstand. Es ist Fall 1 von Satz 10.4.3.

Ausgehend vom Kontext wahrheitsgemäßer Mechanismen nehmen sie zunächst ein wahrheitsgemäßes und ein falsches und leiten ab, dass die auf basierende Zahlung kleiner oder gleich der auf basierenden Zahlung ist , z. B. . Sie nehmen dann das Gegenteil an, ein wahres und ein falsches , und leiten das entgegengesetzte Ergebnis ab, dass die auf basierende Zahlung geringer ist als die auf basierende Zahlung , z. B. . Okay, das macht Sinn. $v_i$ $v_i'$ $v_i$ $v_i'$ $P_i(v_i) \leq P_i(v_i')$ $v_i'$ $v_i$ $v_i'$ $v_i$ $P_i(v_i') \leq P_i(v_i)$

Sie sind dann der Ansicht, dass die auf und basierenden Zahlungen gleich sein müssen, als ob sie sagen, dass und gleichzeitig wahr sind obwohl sie das Ergebnis nicht nur unterschiedlicher, sondern auch entgegengesetzter Annahmen sind. $v_i$ $v_i'$ $P_i(v_i) \leq P_i(v_i')$ $P_i(v_i') \leq P_i(v_i)$

gt.game-theory Novak
quelle

Antworten:

Die Antwort ist, dass der Mechanismus für jeden Satz möglicher Typen wahr sein muss: Der Mechanismus weiß nicht im Voraus, welche Typen die wahren sind. Für ein Paar von Typen und muss der Mechanismus wahr sein, wenn der wahre Typ eines Agenten : dh sein Nutzen muss größer sein, wenn er bietet, als wenn er bietet . Der Mechanismus muss aber auch wahr sein, wenn der wahre Typ des Agenten ! Was den Mechanismus betrifft, könnte es doch so sein! In diesem Fall muss der Nutzen eines Agenten größer sein, wenn er im Vergleich zu bietet . $v_i$ $v_i'$ $v_i$ $v_i$ $v_i'$ $v_i'$ $v_i'$ $v_i$

Der Punkt ist, dass Wahrhaftigkeit dem gleichen Mechanismus gleichzeitig viele verschiedene Ungleichungen auferlegt: eine für jeden Typ, den ein Agent haben könnte, und für jede Abweichung, die er in Betracht ziehen könnte. Alle halten. Dieser Beweis verwendet nur zwei dieser Ungleichungen

Aaron Roth
quelle

Ich glaube, ich fange endlich an, das zu verstehen. In der Tat beeindruckt mich das Wissen, dass der Beweis richtig ist (und warum), noch mehr, wie streng und kraftvoll das Konzept der "Wahrhaftigkeit" tatsächlich ist. Vielen Dank.

Novak

Ich denke, was Sie wollen, ist der folgende Vorschlag.

Vorschlag. Sei und Mengen. Sei und . Angenommen, für alle wir Dann haben wir für alle $V$ $A$ $f:V^n\to A$ $p_1,\dots,p_n:V^n\to\mathbb{R}$ $i,x_i,y_i,v_{−i}$

x_{i} (f (x_{i}, v_{- i})) - p_{i} (x_{i}, v_{- i}) \geq x_{i} (f (y_{i}, v_{- i})) - p_{i} (y_{i}, v_{- i}) .

$x_i (f(x_i , v_{−i})) − p_i (x_i , v_{−i}) \geq x_i (f(y_i , v_{−i})) − p_i (y_i , v_{−i}).$

i, v_{i}, v_{i}^{'}, v_{- i}

$i,v_i,v'_i,v_{-i}$

v_{i} (f (v_{i}, v_{- i})) - v_{i} (f (v_{i}^{'}, v_{- i})) \geq v_{i}^{'} (f (v_{i}, v_{- i})) - v_{i}^{'} (f (v_{i}^{'}, v_{- i})) .

$v_i(f(v_i,v_{-i}))-v_i(f(v'_i,v_{-i}))\geq v'_i(f(v_i,v_{-i}))-v'_i(f(v'_i,v_{-i})).$

Beweis. Putting und wir haben Putting und wir haben Das Ergebnis folgt durch Hinzufügen dieser Ungleichungen und Neuanordnen. $x_i=v_i$ $y_i=v'_i$

v_{i} (f (v_{i}, v_{- i})) - p_{i} (v_{i}, v_{- i}) \geq v_{i} (f (v_{i}^{'}, v_{- i})) - p_{i} (v_{i}^{'}, v_{- i}) .

$v_i (f(v_i , v_{−i})) − p_i (v_i , v_{−i}) \geq v_i (f(v'_i , v_{−i})) − p_i (v'_i , v_{−i}).$

x_{i} = v_{i}

$x_i=v_i$

y_{i} = v_{i}^{'}

$y_i=v'_i$

v_{i}^{'} (f (v_{i}^{'}, v_{- i})) - p_{i} (v_{i}^{'}, v_{- i}) \geq v_{i}^{'} (f (v_{i}, v_{- i})) - p_{i} (v_{i}, v_{- i}) .

$v'_i (f(v'_i , v_{−i})) − p_i (v'_i , v_{−i}) \geq v'_i (f(v_i , v_{−i})) − p_i (v_i , v_{−i}).$

Die Mechanismusdesign-Interpretation dieses Satzes lautet, dass jeder anreizkompatible (dh strategiebeweise, dh wahrheitsgemäße) Mechanismus eine "schwache Monotonie" aufweist.

Aus irgendeinem Grund ist es üblich, unter Bezugnahme auf wahre Gebote und Lügen zu argumentieren. In diesem Zusammenhang sind "wahr" und "Lüge" nur Variablennamen wie "x" und "y". Es ist in Ordnung, denselben Namen zu verwenden, um in separaten Argumenten auf verschiedene Dinge zu verweisen, da es keinen formalen Unterschied zwischen einem echten Gebot und einer Lüge gibt.

Colin McQuillan
quelle

Das ist der fragliche Satz. (Obwohl ich denke, dass Sie in der dritten Zeile Ihres Beweises einen Tippfehler haben - die v_i-Zuweisungen sollten aus der ersten Zeile ausgetauscht werden.) Ich bin immer noch unklar, warum es akzeptabel ist, die beiden Ungleichungen hinzuzufügen, wenn sie sich aus unterschiedlichen Annahmen ergeben. Ja, es gibt keinen formalen Unterschied zwischen einem wahren und einem falschen Gebot. Sie sind beide Zahlen. Aber sie sind (oder genauer gesagt, sie können sein) unterschiedliche Zahlen.

Novak

@Novak: Wie wäre es damit: Wenn ich dir sage, dass für alle , würdest du akzeptieren, dass für alle ?

g (a, b) = 1

$g(a,b)=1$

a, b

$a,b$

g (x, y) - g (y, x) = 0

$g(x,y)-g(y,x)=0$

x, y

$x,y$

Colin McQuillan

Ja. Aber lassen Sie mich das im Kontext des Mechanismusdesigns ein wenig kauen. (Und zur gleichen Zeit aktualisiere meinen ursprünglichen Beitrag in Mathjax und füge den ähnlichen Fall hinzu, den ich aus Shoham und Leyton-Brown ausgegraben habe.)

Novak

Was mich hier stört, ist Ihre Aufstellung des Vorschlags. Wenn ich diese Behauptung sehe, dass der Satz wahr ist, ist es bereits im Zusammenhang, dass der wahre Wert und das (möglicherweise) falsche Gebot ist. Ich stelle auch die Idee in Frage, dass 'wahr' und 'Lüge' Variablennamen sind. Wahr und Lüge scheinen vielmehr tatsächliche Eigenschaften der gemeldeten Werte zu sein. Der Sinn des Spiels besteht darin, diesen Unterschied auszunutzen, um Anreize für die Berichterstattung über die wahrheitsgemäße Qualität zu schaffen.

x_{i}

$x_i$

y_{i}

$y_i$

Novak

Genauer gesagt, wenn Sie mir sagen, dass für alle wahrheitsgemäßen , für alle (was dem ursprünglichen Kontext etwas näher kommt), dann kann ich akzeptieren, dass wenn ich weiß, dass sowohl als auch wahr sind.

g (a, b) = 1

$g(a,b) = 1$

a

$a$

b

$b$

g (x, y) - g (y, x) = 0

$g(x,y) - g(y,x) = 0$

x

$x$

y

$y$

Novak