Weekly outline

  • General

    Διδάσκοντες

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

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

    • Αλβέρτος Καλαβάσης, Υ.Δ. ( kalavasis@corelab.ntua.gr )

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


    Οι διαλέξεις θα ξεκινήσουν την Τρίτη 2 Μαρτίου, 2021. 


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


  • 1 March - 7 March

    Διάλεξη 2/3: Εισαγωγή, Διαδικαστικά, Παραδείγματα Παιγνίων, Ισορροπία Nash


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


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




    • 8 March - 14 March

      • Μαθηματικοί ορισμοί των σημείων ισορροπίας και των κυρίαρχων στρατηγικών
      • Αμιγείς και μεικτές στρατηγικές
      • Παίγνια πολλών παικτών
      • Το θεώρημα του Nash για ύπαρξη σημείων ισορροπίας
      • Απλοποιήσεις παιγνίων, επαναλαμβανόμενη αφαίρεση κυριαρχούμενων στρατηγικών
      • Υλικό: Διαφάνειες της διάλεξης 


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


      • 15 March - 21 March

        • 0-sum games
        • Το θεώρημα δυικότητας γραμμικού προγραμματισμού (LP Duality)
        • Αλγόριθμοι για 0-sum games
        • Αλγόριθμοι για άλλες κατηγορίες παιγνίων
        • The support theorem
        • Υλικό: Διαφάνειες για 0-sum games και (οι διαφάνειες για γενικά παίγνια είναι στην επόμενη εβδομάδα)


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


        • 22 March - 28 March

          • Αλγόριθμοι για γενικά παίγνια
          • 2x2 και 2xn παίγνια
          • Tο Θεώρημα του Brouwer και το Λήμμα του Sperner
          • Η κλάση PPAD, PPAD-completeness αποτελέσματα για παίγνια 2 παικτών 
          • Προσεγγιστικά σημεία ισορροπίας
          • Υλικό: Διαφάνειες της διάλεξης


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



          • 29 March - 4 April

            • Εισαγωγή στον σχεδιασμό μηχανισμών.
            • Δημοπρασίες για ένα αντικείμενο
            • Οι δημοπρασίες 1ης και 2ης τιμής
            • Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson.

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


            Σύνδεσμος στη βιντεοσκοπημένη διάλεξη 


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

            • 5 April - 11 April

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

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

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



              • 12 April - 18 April

                • Γρήγορη ανασκόπηση προηγούμενης διάλεξης: προσεγγιστικοί μηχανισμοί για το Knapsack. 
                • Προσεγγιστικός άπληστος μηχανισμός για single-minded bidders, μη προσεγγισιμότητα, αναγωγή στο ανεξάρτητο σύνολο.
                • Multi-dimensional bidders, complements and substitutes, subadditive, submodular και superadditive valuation functions.
                • Social welfare maximization, Walrasian equilibrium, first and second social welfare theorems, tatonnement, gross substitutes, Kelso-Crawford. 


                Προτεινόμενη μελέτη: 
                • Διαφάνειες.
                • 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. 


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


                • 19 April - 25 April

                  • Γρήγορη ανασκόπηση προηγούμενης διάλεξης: complements and substitutes, subadditive, submodular και superadditive valuation functions, social welfare maximization, Walrasian equilibrium, first and second social welfare theorems. 
                  • Walrasian equilibrium, tatonnement process, 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.

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


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



                  • 26 April - 2 May

                    • Μεγιστοποίηση κέρδους, reserve prices και virtual valuations, βέλτιστος truthful μηχανισμός που μεγιστοποιεί το αναμενόμενο κέρδος για single-parameter bidders, μεγιστοποίηση αναμενόμενου κέρδους μέσω μεγιστοποίησης αναμενόμενου virtual welfare. 
                    • Απλοί προσεγγιστικοί μηχανισμοί για bidders που δεν ακολουθούν την ίδια κατανομή, prophet inequality, prior-free μηχανισμοί, θεώρημα Bulow-Klemperer. 
                    • Weak monotonicity, negative cycles και χαρακτηρισμός truthful μηχανισμών. 

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



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

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

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


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


                      • 17 May - 23 May

                        • Mη ατομικά παίγνια δρομολόγησης (non-Atomic Selfish Routing / network Congestion Games)
                        • Υπολογισμός βέλτιστης ροής και ροής ισορροπίας
                        • Φράγματα στο Τίμημα της Αναρχίας
                        • Βελτίωση της ποιότητας με χρήση διοδίων

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


                        Σύνδεσμος στη βιντεοσκοπημένη διάλεξη  

                        • 24 May - 30 May

                          • Auction mechanisms in practice
                          • Sponsored search auctions
                          • Multi-unit auctions (Discriminatory and Uniform Price Auction)
                          • PoA analysis of non-truthful mechanisms
                          • Deferred-acceptance auctions
                          • Διαφάνειες 

                          Σύνδεσμος στη βιντεοσκοπημένη διάλεξη  

                          • 31 May - 6 June

                            Διάλεξη Βασίλη Γκατζέλη σχετικά με τις δυνατότητες και τους περιορισμούς των Clock Auctions (διαφάνειες)

                            Σύντομη περίληψη της διάλεξης: In this presentation, we will be focusing on the class of (deferred-acceptance) clock auctions, introduced by economists Paul Milgrom and Ilya Segal. Clock auctions satisfy a sequence of impressive properties: i) they areobviously strategyproof, which implies that it is very easy for the participating bidders to identify their optimal strategy, ii) they are weakly group-strategyproof, which guarantees that even the bidders collude, they cannot manipulate the auction, iii) they are transparent and do not require that the bidders trust the auctioneer, and iv) they satisfy unconditional winner privacy, which means that the winners of the auction do not need to reveal their true value. This unique combination of benefits that clock auctions provide make them ideal for real-world problems, since they require very little from the participating bidders. Our presentation will first discuss these properties in detail, it will then study the extent to which clock auctions can match the state-of-the-art performance guarantees of previously known auctions (proving both positive and negative results), and will conclude with a discussion of some open problems and future directions.

                            • 7 June - 13 June

                              Διάλεξη Παναγιώτη Μερτικόπουλου σχετικά με online learning σε παίγνια (διαφάνειες)

                              Σύντομη περίληψη της διάλεξης: Does learning with empirical observations lead to a Nash equilibrium? This question - originally due to Nash himself - has been at the forefront of game-theoretic research ever since the early days of the field. However, despite immense progress and intense scrutiny, a full and complete answer remains elusive. In this talk, we will examine the long-run behavior of a wide array of algorithms for learning in games – including the multiplicative/exponential weights algorithm, gradient descent/ascent, their optimistic variants, etc. We will consider both finite and continuous games, with different types of feedback (from full information to purely emprical, bandit-type observations), and we will present a unified framework for their analysis through the lens of stochastic approximation. We will subsequently use this viewpoint to survey a range of recent results in the field – both positive and negative – and we will discuss a number of open questions that have attracted considerable interest in machine learning and beyond.