Section outline

  • Collapse Expand

    General

    Collapse all Expand all
    Διδάσκοντες

    • Βαγγέλης Μαρκάκης, Επικ. Καθηγητής ( 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, παλαιό κτήριο ΣΗΜΜΥ, ΕΜΠ)

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


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


  • Collapse Expand

    24 February - 1 March


  • Collapse Expand

    2 March - 8 March

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

  • Collapse Expand

    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

  • Collapse Expand

    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 σετ διαφανειών

  • Collapse Expand

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

  • Collapse Expand

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



  • Collapse Expand

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


  • Collapse Expand

    13 April - 19 April

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

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



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



  • Collapse Expand

    20 April - 26 April

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

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

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


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

  • Collapse Expand

    4 May - 10 May

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

  • Collapse Expand

    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)
  • Collapse Expand

    18 May - 24 May

  • Collapse Expand

    25 May - 31 May

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

    1 June - 7 June

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