Weekly outline

  • General

    Διδάσκοντες

    • Βαγγέλης Μαρκάκης, Επικ. Καθηγητής ( markakis@aueb.gr )
    • Θανάσης Λιανέας, Μεταδιδακτορικός Ερευνητής ( lianeas@corelab.ntua.gr )
    • Δημήτρης Φωτάκης, Αναπλ. Καθηγητής ( fotakis@cs.ntua.gr )

    Βοηθοί Διδασκαλίας

    • Αγγελική Μαθιουδάκη, Υ.Δ. ( tmathiou@corelab.ntua.gr )
    • Παναγιώτης Πατσιλινάκος, Υ.Δ. ( patsilinak@corelab.ntua.gr )

    Πρόγραμμα Διαλέξεων

    • κάθε Τρίτη 15:00-18:00 (Αίθουσα 1.1.31, παλαιό κτήριο ΣΗΜΜΥ, ΕΜΠ)

    Ενδεικτική Βιβλιογραφία


    Πρόσθετο Υλικό


  • 24 February - 1 March


    • 2 March - 8 March

      • Μαθηματικοί ορισμοί των σημείων ισορροπίας και των κυρίαρχων στρατηγικών
      • Αμιγείς και μεικτές στρατηγικές
      • 0-sum games
      • Υλικό: 3ο σετ διαφανειών 

      • 9 March - 15 March

        • Computation of exact equilibria
        • Algorithms for 0-sum games
        • Algorithms for special classes of general games
        • Complexity results for Nash equilibria
        • Υλικό: 4ο σετ διαφανειών για 0-sum games και 5ο σετ για γενικά παίγνια και για approximate equilibria

        • 16 March - 22 March

          • Algorithms for approximate Nash equilibria
          • Υλικό για approximate equilibria: Δείτε το τελευταίο μέρος του 5ου σετ διαφανειών την προηγούμενη εβδομάδα.
          • Introduction to Mechanism Design
          • Single-item auctions
          • Characterization of truthful mechanisms for single-parameter environments 
          • Υλικό για mechanism design: 6o σετ διαφανειών

          • 23 March - 29 March

            • Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson. 
            • Υπολογιστικά αποδοτικοί μηχανισμοί και μονότονοι αλγόριθμοι προσέγγισης. 
            • Εφαρμογές σε Knapsack auctions και auctions για single-minded bidders. 
            • Multi-dimensional bidders, complements and substitutes, subadditive, submodular και superadditive valuation functions. 

            Προτεινόμενη μελέτη: 


            Σύνδεσμος στη βιντεοσκοπημένη διάλεξη (βιντεοσκοπήθηκε μόνο το 2ο μέρος της διάλεξης, και δυστυχώς υπήρξαν κάποια τεχνικά προβλήματα). 


            (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση στο βιντεοσκοπημένο μέρος της διάλεξης. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).

            • 30 March - 5 April

              • Γρήγορη ανασκόπηση προηγούμενης διάλεξης, complements and substitutes, subadditive, submodular και superadditive valuation functions (επανάληψη).
              • 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. 

              Προτεινόμενη μελέτη: 

              Σύνδεσμος στη βιντεοσκοπημένη διάλεξη (η βιντεοσκόπηση ξεκίνησε με μικρή καθυστέρηση). 


              (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση στο βιντεοσκοπημένο μέρος της διάλεξης. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).



              • 6 April - 12 April

                • Γρήγορη ανασκόπηση προηγούμενης διάλεξης: VCG μηχανισμός, social welfare maximization για submodular valuations, Maximal-in-Range μηχανισμοί, truthful Maximal-in-Range μηχανισμός με value queries για subadditive valuations. 
                • Truthful (approximate) social welfare maximization με demand queries, μηχανισμός Krysta-Vocking.  
                • Weak monotonicity, negative cycles και χαρακτηρισμός truthful μηχανισμών.  
                • Μεγιστοποίηση κέρδους, reserve prices και virtual valuations, βέλτιστος truthful μηχανισμός που μεγιστοποιεί το αναμενόμενο κέρδος για single-parameter bidders, μεγιστοποίηση αναμενόμενου κέρδους μέσω μεγιστοποίησης αναμενόμενου virtual welfare. 

                Προτεινόμενη μελέτη: 


                (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση στο βιντεοσκοπημένο μέρος της διάλεξης. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).


                • 13 April - 19 April

                  • Γρήγορη ανασκόπηση προηγούμενης διάλεξης: μεγιστοποίηση κέρδους, reserve prices και virtual valuations, βέλτιστος truthful μηχανισμός που μεγιστοποιεί το αναμενόμενο κέρδος για single-parameter bidders, μεγιστοποίηση αναμενόμενου κέρδους μέσω μεγιστοποίησης αναμενόμενου virtual welfare. 
                  • Απλοί προσεγγιστικοί μηχανισμοί για bidders που δεν ακολουθούν την ίδια κατανομή, prophet inequality, prior-free μηχανισμοί, θεώρημα Bulow-Klemperer. 
                  • Εφαρμογές σχεδιασμού μηχανισμών και αλγοριθμικής θεωρίας παιγνίων σε αγορές ηλεκτρικής ενέργειας (guest lecture από Γ. Τσαούσογλου). 

                  Προτεινόμενη μελέτη: 



                  (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση στο βιντεοσκοπημένο μέρος της διάλεξης. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).



                  • 20 April - 26 April

                    Δεν έγινε διάλεξη, λόγω των διακοπών του Πάσχα. 

                    • 27 April - 3 May

                      • Παίγνια συμφόρησης (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 για συμμετρικά παίγνια συμφόρησης. 

                      Προτεινόμενη μελέτη: 


                      Δυστυχώς, για τεχνικούς λόγους, δεν κατέστη δυνατή η βιντεοσκόπηση της διάλεξης. 

                      • 4 May - 10 May

                        • Selfish Routing Model (nonatomic network Congestion Games)
                        • Computing Optimal and Equilibrium flows
                        • Bounding the Price of Anarchy

                      • 11 May - 17 May

                        • Selfish Routing reminder
                        • Use of tolls to improving network's performance
                        • On detecting and excluding the Braess' Paradox
                        • When some players are willing to cooperate: Stackelberg Strategies (to be continued in the near future)

                      • 18 May - 24 May

                        • 25 May - 31 May

                          1ο μισό
                          • Deferred Acceptance Auctions (slides στην προηγούμενη εβδομάδα)
                          • Voting
                          2ο μισό
                          • Stable Matching

                        • 1 June - 7 June

                          1ο μισό (συνέχεια από 26/5)
                          • Top Trading Cycles
                          • Kidney Exchange
                          2o μισό (συνέχεια από 12/5)
                          • Dealing with Braess Paradox
                          • Stackelberg Strategies