Περιγραφή θέματος

  • Γενικά

    • Ανακοινώσεις Φόρουμ
      Εδώ αναρτώνται οι γενικές ανακοινώσεις από τους διδάσκοντες προς τους εγγεγραμμένους φοιτητές, οι οποίοι τις λαμβάνουν και στην ηλεκτρονική τους διεύθυνση.

    • Forum Ερωτήσεων/Απαντήσεων Φόρουμ

      Σε αυτό το forum, μπορεί οποιοσδήποτε εγγεγραμμένος φοιτητής να αναρτά ερωτήσεις σχετικές με το μάθημα και να λαμβάνει απαντήσεις από τους διδάσκοντες. Οι ερωτήσεις και οι απαντήσεις θα είναι διαθέσιμες σε όλους τους φοιτητές. 

      Οι φοιτητές μπορούν να δηλώσουν με την εγγραφή τους αν θέλουν να ενημερώνονται για τις αναρτώμενες ερωταπαντήσεις.


  • Διδάσκοντες / Βοηθοί Διδασκαλίας

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


    Ώρες Γραφείου Διδασκόντων

    • Βαγγέλης Μαρκάκης: Τετάρτη 16:00 - 17:00, Πέμπτη 12:00 - 14:00
    • Θανάσης Λιανέας: θα ανακοινωθούν.
    • Δημήτρης Φωτάκης: Τρίτη 14:00 - 15:00, στο γραφείο 1.1.10, (Παλαιό) Κτήριο Ηλεκτρολόγων.


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

    • Θα ανακοινωθούν.

    • Γενικές Πληροφορίες

      • Ενδεικτική Βιβλιογραφία / Προτεινόμενη Μελέτη


        • Διαλέξεις

          • Διάλεξη 1/3/2022. Διαδικαστικά - Ατζέντα. Σύντομη εισαγωγή στις βασικές έννοιες της Αλγοριθμικής Θεωρίας Παγνίων. Διαφάνειες εισαγωγικής διάλεξης.
          • Διάλεξη 8/3/2022. Μαθηματικοί ορισμοί των σημείων ισορροπίας και των κυρίαρχων στρατηγικών. Αμιγείς και μεικτές στρατηγικές. Παίγνια πολλών παικτών. Το θεώρημα του Nash για ύπαρξη σημείων ισορροπίας. Απλοποιήσεις παιγνίων, επαναλαμβανόμενη αφαίρεση κυριαρχούμενων στρατηγικών. Διαφάνειες 2ης διάλεξης.
          • Διάλεξη 15/3/2022. 0-sum games. Το θεώρημα δυικότητας γραμμικού προγραμματισμού (LP Duality). Αλγόριθμοι για 0-sum games. Αλγόριθμοι για άλλες κατηγορίες παιγνίων. The support theorem. Διαφάνειες για 0-sum games.
          • Διάλεξη 22/3/2022. Αλγόριθμοι για 2x2 και 2xn παίγνια. Το θεώρημα του Brouwer και το λήμμα του Sperner. Κλάσεις πολυπλοκότητας για total problems. PPAD-completeness για παίγνια 2 παικτών. Προσεγγιστικά σημεία ισορροπίας. Διαφάνειες για γενικά παίγνια.
          • Διάλεξη 29/3/2022. Εισαγωγή στον σχεδιασμό μηχανισμών. Δημοπρασίες για ένα αντικείμενο. Οι δημοπρασίες 1ης και 2ης τιμής. Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson. 
          • Διάλεξη 5/4/2022. Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson. Υπολογιστικά αποδοτικοί μηχανισμοί και μονότονοι αλγόριθμοι προσέγγισης. Εφαρμογές σε Knapsack auctions και σε auctions για single-minded bidders. Προσεγγιστικός άπληστος μηχανισμός για single-minded bidders, μη προσεγγισιμότητα, αναγωγή στο ανεξάρτητο σύνολο. Multi-dimensional bidders, complements and substitutes, subadditive, submodular και superadditive valuation functions. 
          • Διάλεξη 12/4/2022. 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. Truthful (approximate) social welfare maximization με demand queries, μηχανισμός Krysta-Vocking. 
          • Διάλεξη 3/5/2022. Μεγιστοποίηση κέρδους, reserve prices και virtual valuations, βέλτιστος truthful μηχανισμός που μεγιστοποιεί το αναμενόμενο κέρδος για single-parameter bidders, μεγιστοποίηση αναμενόμενου κέρδους μέσω μεγιστοποίησης αναμενόμενου virtual welfare. Απλοί προσεγγιστικοί μηχανισμοί για bidders που δεν ακολουθούν την ίδια κατανομή, prophet inequality, prior-free μηχανισμοί, θεώρημα Bulow-Klemperer. Weak monotonicity, negative cycles και χαρακτηρισμός truthful μηχανισμών.
          • Διάλεξη 10/5/22. Παίγνια συμφόρησης (congestion games): μοντέλο, παραδείγματα, συνάρτηση δυναμικού, ύπαρξη αμιγούς ισορροπίας Nash. Παίγνια δυναμικού (potential games): συναρτήσεις δυναμικού, exact, weighted, ordinal, generalized potential functions. Συναρτήσεις δυναμικού και σύγκλιση σε (αμιγή) ισορροπία Nash, better και best response dynamics, acyclic Nash dynamics και ύπαρξη συνάρτησης δυναμικού, οι αμιγείς ισορροπίες Nash ως τοπικά βέλτιστα μιας συνάρτησης δυναμικού.  Γρήγορη σύγκλιση σε προσεγγιστικές αμιγείς ισορροπίες Nash για συμμετρικά παίγνια συμφόρησης.
          • Διάλεξη 17/5/22. Mη ατομικά παίγνια δρομολόγησης (non-Atomic Selfish Routing / network Congestion Games). Υπολογισμός βέλτιστης ροής και ροής ισορροπίας. Φράγματα στο Τίμημα της Αναρχίας. Βελτίωση της ποιότητας με χρήση διοδίων.
          • Διάλεξη 24/5/22. Εφαρμογές δημοπρασιών. Sponsored search auctions, multi-unit auctions. Ανάλυση του τιμήματος της αναρχίας σε μη φιλαλήθεις μηχανισμούς.
            • Διάλεξη 31/5/22. Mechanisms without money. Voting, Stable Matching, Top trading cycles.
            • Διάλεξη 6/6/2022 από Παναγιώτη Μερτικόπουλο: From Convex Optimization to Learning in Games. 

            • Γραπτές Ασκήσεις

              • Θα ανακοινωθούν τρεις (3) σειρές γραπτών ασκήσεων. 
              • Οι γραπτές ασκήσεις υποβάλλονται στη σελίδα του μαθήματος, στο helios. Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
              • Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.

              Εκφωνήσεις Γραπτών Ασκήσεων