10 Μαΐου - 16 Μαΐου
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.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση στο βιντεοσκοπημένο μέρος της διάλεξης. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).