Θέμα: Διαλέξεις | Αλγοριθμική Θεωρία Παιγνίων

Ημερολόγιο

Δευτέρα	Τρίτη	Τετάρτη	Πέμπτη	Παρασκευή	Σάββατο	Κυριακή
						Κανένα γεγονός, Κυριακή, 1 Δεκεμβρίου Κανένα γεγονός, Κυριακή, 1 Δεκεμβρίου
Κανένα γεγονός, Δευτέρα, 2 Δεκεμβρίου Κανένα γεγονός, Δευτέρα, 2 Δεκεμβρίου	Κανένα γεγονός, Τρίτη, 3 Δεκεμβρίου Κανένα γεγονός, Τρίτη, 3 Δεκεμβρίου	Κανένα γεγονός, Τετάρτη, 4 Δεκεμβρίου Κανένα γεγονός, Τετάρτη, 4 Δεκεμβρίου	Κανένα γεγονός, Πέμπτη, 5 Δεκεμβρίου Κανένα γεγονός, Πέμπτη, 5 Δεκεμβρίου	Κανένα γεγονός, Παρασκευή, 6 Δεκεμβρίου Κανένα γεγονός, Παρασκευή, 6 Δεκεμβρίου	Κανένα γεγονός, Σάββατο, 7 Δεκεμβρίου Κανένα γεγονός, Σάββατο, 7 Δεκεμβρίου	Κανένα γεγονός, Κυριακή, 8 Δεκεμβρίου Κανένα γεγονός, Κυριακή, 8 Δεκεμβρίου
Κανένα γεγονός, Δευτέρα, 9 Δεκεμβρίου Κανένα γεγονός, Δευτέρα, 9 Δεκεμβρίου	Κανένα γεγονός, Τρίτη, 10 Δεκεμβρίου Κανένα γεγονός, Τρίτη, 10 Δεκεμβρίου	Κανένα γεγονός, Τετάρτη, 11 Δεκεμβρίου Κανένα γεγονός, Τετάρτη, 11 Δεκεμβρίου	Κανένα γεγονός, Πέμπτη, 12 Δεκεμβρίου Κανένα γεγονός, Πέμπτη, 12 Δεκεμβρίου	Κανένα γεγονός, Παρασκευή, 13 Δεκεμβρίου Κανένα γεγονός, Παρασκευή, 13 Δεκεμβρίου	Κανένα γεγονός, Σάββατο, 14 Δεκεμβρίου Κανένα γεγονός, Σάββατο, 14 Δεκεμβρίου	Κανένα γεγονός, Κυριακή, 15 Δεκεμβρίου Κανένα γεγονός, Κυριακή, 15 Δεκεμβρίου
Κανένα γεγονός, Δευτέρα, 16 Δεκεμβρίου Κανένα γεγονός, Δευτέρα, 16 Δεκεμβρίου	Κανένα γεγονός, Τρίτη, 17 Δεκεμβρίου Κανένα γεγονός, Τρίτη, 17 Δεκεμβρίου	Κανένα γεγονός, Τετάρτη, 18 Δεκεμβρίου Κανένα γεγονός, Τετάρτη, 18 Δεκεμβρίου	Κανένα γεγονός, Πέμπτη, 19 Δεκεμβρίου Κανένα γεγονός, Πέμπτη, 19 Δεκεμβρίου	Κανένα γεγονός, Παρασκευή, 20 Δεκεμβρίου Κανένα γεγονός, Παρασκευή, 20 Δεκεμβρίου	Κανένα γεγονός, Σάββατο, 21 Δεκεμβρίου Κανένα γεγονός, Σάββατο, 21 Δεκεμβρίου	Κανένα γεγονός, Κυριακή, 22 Δεκεμβρίου Κανένα γεγονός, Κυριακή, 22 Δεκεμβρίου
Κανένα γεγονός, Δευτέρα, 23 Δεκεμβρίου Κανένα γεγονός, Δευτέρα, 23 Δεκεμβρίου	Κανένα γεγονός, Τρίτη, 24 Δεκεμβρίου Κανένα γεγονός, Τρίτη, 24 Δεκεμβρίου	Κανένα γεγονός, Τετάρτη, 25 Δεκεμβρίου Κανένα γεγονός, Τετάρτη, 25 Δεκεμβρίου	Κανένα γεγονός, Πέμπτη, 26 Δεκεμβρίου Κανένα γεγονός, Πέμπτη, 26 Δεκεμβρίου	Κανένα γεγονός, Παρασκευή, 27 Δεκεμβρίου Κανένα γεγονός, Παρασκευή, 27 Δεκεμβρίου	Κανένα γεγονός, Σάββατο, 28 Δεκεμβρίου Κανένα γεγονός, Σάββατο, 28 Δεκεμβρίου	Κανένα γεγονός, Κυριακή, 29 Δεκεμβρίου Κανένα γεγονός, Κυριακή, 29 Δεκεμβρίου
Κανένα γεγονός, Δευτέρα, 30 Δεκεμβρίου Κανένα γεγονός, Δευτέρα, 30 Δεκεμβρίου	Κανένα γεγονός, Τρίτη, 31 Δεκεμβρίου Κανένα γεγονός, Τρίτη, 31 Δεκεμβρίου

Section outline

Διάλεξη 20/2/2024. Διαδικαστικά - Ατζέντα. Σύντομη εισαγωγή στις βασικές έννοιες της (Αλγοριθμικής) Θεωρίας Παγνίων.

Διάλεξη 27/2/2024. Μαθηματικοί ορισμοί των σημείων ισορροπίας και των κυρίαρχων στρατηγικών. Αμιγείς και μεικτές στρατηγικές. Παίγνια πολλών παικτών. Το θεώρημα του Nash για ύπαρξη σημείων ισορροπίας. Απλοποιήσεις παιγνίων, επαναλαμβανόμενη αφαίρεση κυριαρχούμενων στρατηγικών.
Διάλεξη 5/3/2024. Zero-sum games. Αμιγείς και μεικτές max-min στρατηγικές. Το θεώρημα του von Neumann.
Διάλεξη 12/3/2024. Αλγόριθμοι για γενικά παίγνια, προσεγγιστικά σημεία ισορροπίας.
Διάλεξη 19/3/2024. Εισαγωγή στον σχεδιασμό μηχανισμών. Δημοπρασίες για ένα αντικείμενο. Οι δημοπρασίες 1ης και 2ης τιμής. Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson. Διαφάνειες. Σημειώσεις από το μάθημα του Tim Roughgarden: σχεδιασμός μηχανισμών και Myerson's Lemma.
Διάλεξη 26/3/2024. Σχεδιασμός μηχανισμών για 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 στον σχεδιασμό μηχανισμών.
Διάλεξη 2/4/2024. 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. Υπολογιστικά αποδοτικοί προσεγγιστικοί μηχανισμοί
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/4/2024. Social welfare maximization, VCG μηχανισμός, Maximal-in-Range μηχανισμοί, Maximal-in-Range μηχανισμός για subadditive valuations (επανάληψη). Truthful (approximate) social welfare maximization με demand queries, μηχανισμός Krysta-Vocking. Μεγιστοποίηση πληρωμών (revenue maximization), monopoly price, reserve prices και virtual valuations, βέλτιστος truthful μηχανισμός που μεγιστοποιεί αναμενόμενες πληρωμές για single-parameter bidders, μεγιστοποίηση αναμενόμενων πληρωμών μέσω μεγιστοποίησης αναμενόμενου virtual welfare.
Διαφάνειες .
Σημειώσεις από το μάθημα του Tim Roughgarden: Μεγιστοποίηση κέρδους.
Ενότητες 13.1, 13.2, 13.3.1 και 13.3.2 από βιβλίο σε Algorithmic Game Theory.
Σημειώσεις από το μάθημα του Matt Weinberg: VCG μηχανισμός και Maximal-in-Distributional-Range μηχανισμός των Lavi και Swamy.
Διάλεξη 16/4/2024. Μεγιστοποίηση αναμενόμενων πληρωμών για single-parameter bidders μέσω μεγιστοποίησης αναμενόμενου virtual welfare (επανάληψη). Απλοί προσεγγιστικοί μηχανισμοί για bidders που δεν ακολουθούν την ίδια κατανομή, prophet inequality (σημειώσεις Βασίλη Λίβανου (set1 και set2) και σημειώσεις Tim Roughgarden σχετικά με prophet inequalities και την εφαρμογή τους στο σχεδιασμό μηχανισμών), prior-free μηχανισμοί, θεώρημα Bulow-Klemperer. Παίγνια συμφόρησης (congestion games) και τίμημα της αναρχίας (price of anarchy).
Διάλεξη 14/5/2024. nonAtomic Selfish Routing. Υπολογισμός ροής ισορροπίας και βέλτιστης ροής. Συνάρτηση δυναμικού, τίμημα της αναρχίας. Variational Inequality. Διόδια για ομογενείς και ετερογενείς πληθυσμούς.
Διαφάνειες
Διάλεξη 21/5/2024. Atomic Selfish Routing, τίμημα της αναρχίας, υπολογισμός ισορροπίας, συναρτήσεις δυναμικού, Max-Cut game. Voting, Stable matching.
Διαφάνειες για Atomic Routing, Συναρτήσεις δυναμικού, Max-Cut game
Διαφάνειες για Voting
Διαφάνειες για Stable Matching
Διάλεξη 28/5/2024. Top Trading Cycles, Kidney exchange, άλλες έννοιες ισορροπίας, Learning Dynamics.
Διαφάνειες για Top Trading Cycles και Kidney Exchange
Διαφάνειες για άλλες έννοιες ισορροπίας και Learning Dynamics
Διαφάνεις για Learning Dynamics (by Tuomas Sandholm and Brian Zhang)
- Επιλογή δραστηριότητας Ενότητα 0 - Πληροφορίες για το μάθημα
  
  Ενότητα 0 - Πληροφορίες για το μάθημα Αρχείο PDF
  
  159.0 KB
- Επιλογή δραστηριότητας Ενότητα 1 - Μοντέλα παιγνίων
  
  Ενότητα 1 - Μοντέλα παιγνίων Αρχείο PDF
  
  523.2 KB
- Επιλογή δραστηριότητας Ενότητα 2 - Game-theoretic solution concepts
  
  Ενότητα 2 - Game-theoretic solution concepts Αρχείο PDF
  
  633.9 KB
- Επιλογή δραστηριότητας Ενότητα 3 - Zero-sum games
  
  Ενότητα 3 - Zero-sum games Αρχείο PDF
  
  489.3 KB
- Επιλογή δραστηριότητας Ενότητα 4 - Αλγόριθμοι για γενικά παίγνια, Προσεγγιστικά σημεία ισορροπίας
  
  Ενότητα 4 - Αλγόριθμοι για γενικά παίγνια, Προσεγγιστικά σημεία ισορροπίας Αρχείο PDF
  
  856.6 KB

Δεκεμβρίου 2024

Section outline