Seminar

Mechanismenentwurf - Optimierungsprobleme bei egoistischen Agenten

Internetuser und Service Provider verhalten sich eigennützig und spontan, ohne dass es eine Autorität gibt, die den Netzwerkbetrieb überwacht und reguliert, um irgendein soziales Optimum wie z.B. minimale totale Wartezeit zu erreichen. Eine interessante und aktuelle Frage ist, wie viel Leistung dadurch verloren geht. Diese Frage führt zu neuen algorithmischen Problemen, wo wir die Kosten eines Mangels an Zusammenarbeit untersuchen statt eines Mangels an Informationen (Online-Algorithmen) oder eines Mangels an unbegrenzter Rechenleistung (Approximationsalgorithmen).

Im algorithmischen Mechanism Design geht es darum, eigennützige Agenten dazu zu bringen, ihre privaten Daten preiszugeben, damit wir die Leistung optimieren können. Das erfordert ein Auktionsmechanismus oder (häufiger) den Entwurf von geeigneten (monotone) Approximationsalgorithmen für das jeweilige Problem. In dieses Seminar werden wir verschiedene solche Algorithmen und Mechanismen betrachten.

Zu behandelnde Arbeiten:

3. Mai 2007 N. Nisan and A. Ronen,
Algorithmic Mechanism Design
Andreas Geiger, Paul David Dütting
24. Mai 2007 A. Archer and E. Tardos,
Truthful Mechanisms for One-Parameter Agents
Sabine Neubauer
31. Mai 2007 Nir Andelman, Yossi Azar and Motti Sorani,
Truthful Approximation Mechanisms for Scheduling Selfish Related Machines
Tim Kieritz
14. Juni 2007 A. Archer, C. Papadimitriou, K. Talwar and E. Tardos,
An approximate truthful mechanism for combinatorial auctions with single parameter agents
Boris Gross-Hardt
21. Juni 2007 Annamaria Kovacs,
Fast monotone 3-approximation algorithm for scheduling related machines
Tim Kieritz
  • Dozenten: Peter Sanders und Rob van Stee

    Zeit: Donnerstags, 14.00-15.30, SR 236, Informatikgebäude

  • Beginn: 19.4.2007

  • Anmeldung: Mail an vanstee@ira.uka.de