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

    • Διαδικαστικά - Ατζέντα
    • Σύντομη εισαγωγή στις βασικές έννοιες της Αλγοριθμικής Θεωρίας Παγνίων
    • Υλικό: Διαφάνειες (1ο και 2ο σετ), και κάποιες σημειώσεις

    • 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 ή μέσο).