Θεωρητική Πληροφορική ΙΙ: Αλγοριθμική Θεωρία Παιγνίων (ΣΗΜΜΥ, ΣΕΜΦΕ, ΜΠΛΑ)

εαρινό εξάμηνο 2015-2016

● Γενικά ● Ανακοινώσεις ● Παρουσιάσεις ● Ασκήσεις

Γενικά

Διδάσκοντες

  • Δημήτρης Φωτάκης, Επ. Καθηγητής ()

Έναρξη μαθήματος

3/3/2016

Διαλέξεις

  • Πέμπτη 16:00-20:00, αίθουσα 1.1.29 (παλαιό) Κτήριο Ηλεκτρολόγων (ΕΜΠ)

Προαπαιτούμενα

Μαθήματα σε Αλγόριθμους και Πολυπλοκότητα.

Βιβλιογραφία και Χρήσιμοι Σύνδεσμοι

  1. Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007 (διαθέσιμο ηλεκτρονικά εδώ).
  2. Karloff. Linear Programming, 1991
  3. Roughgarden. An Algorithmic Game Theory Primer.
  4. Daskalakis. Topics in Algorithmic Game Theory 2011 Lecture Notes.
  5. Eξειδικευμένα surveys και ερευνητικές εργασίες (όσα αναφέρονται στο πρόγραμμα παρουσιάσεων).

Πληροφορίες

  • Δ. Φωτάκης, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 1.1.10. Τηλ. 210 7724302, fax: 210 7722509, email: .

Ανακοινώσεις

  • [3/6/2016] Η γραπτή εξέταση του μαθήματος θα πραγματοποιηθεί στις 29/6/2016 στις 15:00 στην αίθουσα 1.1.29.
  • [3/6/2016] Δημοσιεύτηκε η 3η σειρά ασκήσεων και μπορείτε να τη βρείτε στις Aσκήσεις.
  • [18/5/2016] Η προθεσμία παράδοσης της 2ης σειράς ασκήσεων μεταφέρεται στις 26/5/2016 και μπορεί να γίνει και ηλεκτρονικά στο e-mail lydiazak@corelab.ntua.gr.
  • [25/4/2016] Δημοσιεύτηκε η 2η σειρά ασκήσεων και μπορείτε να τη βρείτε στις Aσκήσεις.
  • [22/4/2016] Η προθεσμία παράδοσης της 1ης σειράς ασκήσεων μεταφέρεται στις 19/4/2016 και μπορεί να γίνει μέχρι τότε ηλεκτρονικά στο e-mail lydiazak@corelab.ntua.gr.
  • [6/4/2016] Δημοσιεύτηκε η 1η σειρά ασκήσεων και μπορείτε να τη βρείτε στις Aσκήσεις.
  • [20/3/2016] Το επόμενο μάθημα θα γίνει την Τετάρτη 23/3 στις 17:00 στην αίθουσα 1.1.29.

Παρουσιάσεις

Ημ/νία Ομιλητής Θέμα παρουσίασης
3/3 Δ. Φωτάκης (Διαφάνειες) Εισαγωγή: διαδικαστικά, αντικείμενο, θεματολογία, παραδείγματα. Χρήσιμες γνώσεις Γραμμικού Προγραμματισμού.
10/3 Λ. Ζακυνθινού (Διαφάνειες) Nash Equilibria in Bimatrix Games: 2-player zero-sum games. Learning the equilibrium: Fictitious play, Multiplicative Weights Update Algorithm. Nash's Theorem.
17/3 Ι. Τζιώτης (Διαφάνειες) PPAD: Sperner's lemma. PPAD,PPA,PPP,PLS. PPAD-completeness of 2-player NE. Symmetric games: Lemke-Howson's algorithm. LMM.
23/3 Δ. Καλημέρης (Διαφάνειες) Non-atomic Congestion Games: The model, connection to flows, equilibria. PoA. Bicriteria bounds. How to improve PoA: Stackelberg strategies, tolls.
31/3 Δ. Φωτάκης (Διαφάνειες) Non-atomic and Atomic Congestion Games: Stackelberg Strategies, LLF Strategy. Tolls . Introduction to atomic congestion games.
7/4 Δ. Φωτάκης (Διαφάνειες) Atomic Congestion Games: PoA and PoS. Convergence to PNE, PLS-completeness (Survey by Berthold Vöking). Potential Games.
14/4 Δ. Καλημέρης (Διαφάνειες) Advanced Topics in Selfish Routing: Restricted tolls. Uncertainty in Congestion Games. Graphical Congestion Games.
21/4 Μ. Αρσένης (Διαφάνειες) Mechanism Design: Social Choice. Arrow's Theorem. The Revelation Principle. Myerson's Lemma. VCG and welfare maximization. Revenue maximization.
12/5 Ι. Τζιώτης (Διαφάνειες)

Λ. Ζακυνθινού (Διαφάνειες)		 Combinatorial Auctions: Introduction to Combinatorial Auctions. Valuation types. Greedy approximation algorithm for single-minded bidders. Query types. Non-truthful 2-approximation for submodular bidders. Table of best algorithms and lower bounds. Approximation algorithm for subadditive bidders.
19/5 Λ. Ζακυνθινού (Διαφάνειες)

Κ. Νικολιδάκη (Διαφάνειες)		 Combinatorial Auctions: Multiplicative Update Method and Posted-Prices Mechanisms.

Online Mechanism Design: Scheduling Problems with related and unrelated machines. Dynamic Auction with expiring items. The Secretary Problem. Adaptive limited-supply auctions.
26/5 Κ. Νικολιδάκη (Διαφάνειες) Procurement Auctions: Frugality. Budget Feasible Mechanisms. Learning on a budget: Posted-Prices Mechanisms.
2/6 Δ. Φωτάκης (Διαφάνειες)


Φ. Μονάχου (Διαφάνειες) 		Public Good Allocation: The Combinatorial Public Project Problem. MIR truthful approximation algorithm. Impossibility Results.

PoA and Composable Mechanisms: PoA of First Price and Generalized Second Price Auctions. The Smoothness Property. Parallel and Sequential Composition. Lower Bounds.

Ασκήσεις