Ubung zu Algorithmische Spieltheorie - ZAIK

Universität zu Köln
Institut für Informatik
Dr. O. Schaudt
A. van der Grinten
Übung zu Algorithmische Spieltheorie
Blatt Nr. 10
Dieses Übungsblatt muss bis zum 23.01.2017, vor der Übung abgegeben werden. Schreiben Sie Ihren
Namen und Ihre Übungsgruppe oben auf die Abgabe!
Allgemeine Hinweise
• Die Abgabe der Aufgaben erfolgt in den entsprechend beschrifteten Briefkasten in der 5. Etage
des Weyertal 121.
Aufgabe 1: PoA in Standortspielen (Bewertet)
Der soziale Überschuss eines Ausgangs s in einem Standortspiel ist definiert als
X
vj − min{vj , cij : i ∈ s}
j∈M
Dabei gibt vj den Wert des Marktes j an und cij die Kosten um Markt j von Standort i aus zu
beliefern.
Durch den sozialen Überschuss lässt sich ein Preis der Anarchie (PoA) definieren. Finden Sie ein
Standortspiel mit einem PoA von 21 .
Aufgabe 2: Grobe korrelierte Gleichgewichte
Zeigen Sie, dass jedes korrelierte Gleichgewicht eines Kostenminimierungsspiels auch ein grobes korreliertes Gleichgewicht ist.
Aufgabe 3: Potential von Standortspielen
Zeigen Sie, dass Standortspiele Potentialspiele sind. Geben Sie die Potentialfunktion an.
1

Download Report