27 Απριλίου - 3 Μαΐου
Section outline
-
- Παίγνια συμφόρησης (congestion games): μοντέλο, παραδείγματα, συνάρτηση δυναμικού, ύπαρξη αμιγούς ισορροπίας Nash.
- Παίγνια δυναμικού (potential games): συναρτήσεις δυναμικού, exact, weighted, ordinal, generalized potential functions.
- Συναρτήσεις δυναμικού και σύγκλιση σε (αμιγή) ισορροπία Nash, better και best response dynamics, acyclic Nash dynamics και ύπαρξη συνάρτησης δυναμικού, οι αμιγείς ισορροπίες Nash ως τοπικά βέλτιστα μιας συνάρτησης δυναμικού.
- Υπολογισμός ισορροπιών για παίγνια συμφόρησης μέσω σύγκλισης και μέσω αναγωγής στο πρόβλημα min-cost-flow, η κλάση PLS (Polynomial Local Search), PLS-completeness και δυσκολία υπολογισμού τοπικών βέλτιστων.
- Γρήγορη σύγκλιση σε προσεγγιστικές αμιγείς ισορροπίες Nash για συμμετρικά παίγνια συμφόρησης.
Προτεινόμενη μελέτη:- Διαφάνειες.
- Σημειώσεις από το μάθημα του Tim Roughgarden: atomic selfish routing and congestion games (section 2), potential games and existence of pure Nash equilibrium (sections 1 και 2), best response dynamics and convergence to pure Nash equilibrium.
- Σημειώσεις από τα μαθήματα των Yishay Mansour και Aaron Roth.
- Ένα σύντομο (και μάλλον επιλεκτικό) survey για congestion games και selfish routing.
- Ένα σύντομο survey σχετικά με την κλάση PLS και τη δυσκολία υπολογισμού ισορροπίας Nash σε potential games.
- Το άρθρο των Johnson, Papadimitriou και Yannakakis όπου ορίζεται η κλάση PLS.
Δυστυχώς, για τεχνικούς λόγους, δεν κατέστη δυνατή η βιντεοσκόπηση της διάλεξης.