Section outline
-
- Διάλεξη 1/3/2022. Διαδικαστικά - Ατζέντα. Σύντομη εισαγωγή στις βασικές έννοιες της Αλγοριθμικής Θεωρίας Παγνίων. Διαφάνειες εισαγωγικής διάλεξης.
- Διάλεξη 8/3/2022. Μαθηματικοί ορισμοί των σημείων ισορροπίας και των κυρίαρχων στρατηγικών. Αμιγείς και μεικτές στρατηγικές. Παίγνια πολλών παικτών. Το θεώρημα του Nash για ύπαρξη σημείων ισορροπίας. Απλοποιήσεις παιγνίων, επαναλαμβανόμενη αφαίρεση κυριαρχούμενων στρατηγικών. Διαφάνειες 2ης διάλεξης.
- Διάλεξη 15/3/2022. 0-sum games. Το θεώρημα δυικότητας γραμμικού προγραμματισμού (LP Duality). Αλγόριθμοι για 0-sum games. Αλγόριθμοι για άλλες κατηγορίες παιγνίων. The support theorem. Διαφάνειες για 0-sum games.
- Διάλεξη 22/3/2022. Αλγόριθμοι για 2x2 και 2xn παίγνια. Το θεώρημα του Brouwer και το λήμμα του Sperner. Κλάσεις πολυπλοκότητας για total problems. PPAD-completeness για παίγνια 2 παικτών. Προσεγγιστικά σημεία ισορροπίας. Διαφάνειες για γενικά παίγνια.
- Διάλεξη 29/3/2022. Εισαγωγή στον σχεδιασμό μηχανισμών. Δημοπρασίες για ένα αντικείμενο. Οι δημοπρασίες 1ης και 2ης τιμής. Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson.
- Διαφάνειες.
- Σημειώσεις από το μάθημα του Tim Roughgarden: Σχεδιασμός μηχανισμών.
- Διάλεξη 5/4/2022. Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson. Υπολογιστικά αποδοτικοί μηχανισμοί και μονότονοι αλγόριθμοι προσέγγισης. Εφαρμογές σε Knapsack auctions και σε auctions για single-minded bidders. Προσεγγιστικός άπληστος μηχανισμός για single-minded bidders, μη προσεγγισιμότητα, αναγωγή στο ανεξάρτητο σύνολο. Multi-dimensional bidders, complements and substitutes, subadditive, submodular και superadditive valuation functions.
- Διαφάνειες.
- Σημειώσεις από το μάθημα του Tim Roughgarden: Myerson's Lemma και εφαρμογές.
- Διάλεξη 12/4/2022. Social welfare maximization, Walrasian equilibrium, first and second social welfare theorems, tatonnement, gross substitutes, Kelso-Crawford. Combinatorial auctions, demand και value queries. VCG μηχανισμός, truthfulness, Clarke pivot rule. Άπληστος προσεγγιστικός αλγόριθμος για Social Welfare Maximization με submodular valuations. Υπολογιστικά αποδοτικοί προσεγγιστικοί μηχανισμοί, Maximal-in-Range μηχανισμοί, Maximal-in-Range μηχανισμός για subadditive valuations. Truthful (approximate) social welfare maximization με demand queries, μηχανισμός Krysta-Vocking.
- Tutorial σε gross substitutes και υπολογισμό Walrasian equilibrium από Renato Paes Leme και Inbal Talgam-Cohen: 1ο και 2ο μέρος.
- Ενότητες 9.3, 9.5, 11.2, 11.3, 11.5 και 11.7 από βιβλίο σε Algorithmic Game Theory.
- Σημειώσεις από το μάθημα του Tim Roughgarden: VCG μηχανισμός.
- Ενότητες 9.3, 9.5, 11.2, 11.3, 11.5 και 11.7 από βιβλίο σε Algorithmic Game Theory.
- Σημείωσεις από το μάθημα του Matt Weinberg: VCG μηχανισμός και Maximal-in-Distributional-Range μηχανισμός των Lavi και Swamy.
- Διάλεξη 3/5/2022. Μεγιστοποίηση κέρδους, reserve prices και virtual valuations, βέλτιστος truthful μηχανισμός που μεγιστοποιεί το αναμενόμενο κέρδος για single-parameter bidders, μεγιστοποίηση αναμενόμενου κέρδους μέσω μεγιστοποίησης αναμενόμενου virtual welfare. Απλοί προσεγγιστικοί μηχανισμοί για bidders που δεν ακολουθούν την ίδια κατανομή, prophet inequality, prior-free μηχανισμοί, θεώρημα Bulow-Klemperer. Weak monotonicity, negative cycles και χαρακτηρισμός truthful μηχανισμών.
- Διαφάνειες.
- Σημειώσεις από το μάθημα του Tim Roughgarden: Μεγιστοποίηση κέρδους.
- Ενότητες 13.1, 13.2, 13.3.1 και 13.3.2 από βιβλίο σε Algorithmic Game Theory.
- Διάλεξη 10/5/22. Παίγνια συμφόρησης (congestion games): μοντέλο, παραδείγματα, συνάρτηση δυναμικού, ύπαρξη αμιγούς ισορροπίας Nash. Παίγνια δυναμικού (potential games): συναρτήσεις δυναμικού, exact, weighted, ordinal, generalized potential functions. Συναρτήσεις
δυναμικού και σύγκλιση σε (αμιγή) ισορροπία Nash, better και best
response dynamics, acyclic Nash dynamics και ύπαρξη συνάρτησης
δυναμικού, οι αμιγείς ισορροπίες Nash ως τοπικά βέλτιστα μιας συνάρτησης
δυναμικού. Γρήγορη σύγκλιση σε προσεγγιστικές αμιγείς ισορροπίες 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.
- Διάλεξη 17/5/22. Mη ατομικά παίγνια δρομολόγησης (non-Atomic Selfish Routing / network Congestion Games). Υπολογισμός βέλτιστης ροής και ροής ισορροπίας. Φράγματα στο Τίμημα της Αναρχίας. Βελτίωση της ποιότητας με χρήση διοδίων.
- Διαφάνειες.
- Σημειώσεις από το μάθημα του Tim Roughgarden.
- Περί τιμήματος της Αναρχίας: δημοσίευση των José R. Correa, Andreas S. Schulz και Nicolás E. Stier-Moses.
- Σχετικά με διόδια: δημοσίευση της Lisa Fleischer, δημοσίευση των Lisa Fleischer, Kamal Jain και Mohammad Mahdian.
- Διάλεξη 24/5/22. Εφαρμογές δημοπρασιών. Sponsored search auctions, multi-unit auctions. Ανάλυση του τιμήματος της αναρχίας σε μη φιλαλήθεις μηχανισμούς.
- Διάλεξη 6/6/2022 από Παναγιώτη Μερτικόπουλο: From Convex Optimization to Learning in Games.