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

εαρινό εξάμηνο 2010-2011

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

Γενικά

Διδάσκοντες

  • Στάθης Ζάχος, Καθηγητής ()
  • Άρης Παγουρτζής, Επικ. Καθηγητής ()
  • Δημήτρης Φωτάκης, Λέκτορας ()

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

10/3/2011.

Διαλέξεις

  • Πέμπτη 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. Eξειδικευμένα surveys και ερευνητικές εργασίες (όσα αναφέρονται στο πρόγραμμα παρουσιάσεων).

Πληροφορίες

  • Ε. Ζάχος, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 1.1.15. Τηλ. 210 7721646 - 44, fax: 210 7721645, email: .
  • Α. Παγουρτζής, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 1.1.30. Τηλ. 210 7721644, fax: 210 7721645, email: .
  • Δ. Φωτάκης, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 1.1.10. Τηλ. 210 7724302, fax: 210 7722509, email: .

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

  • [16/04/2011] Δημοσιεύτηκε η 3η σειρά ασκήσεων και μπορείτε να την βρείτε στις ασκήσεις.
  • [16/04/2011] Δημοσιεύτηκε η 2η σειρά ασκήσεων. Μπορείτε να την βρείτε στις ασκήσεις. Για την παράδοση της 1ης σειράς ασκήσεων έχει δοθεί παράταση εως την πρώτη εβδομάδα του Μαΐου
  • [26/03/2011] Δημοσιεύτηκε η 1η σειρά ασκήσεων. Μπορείτε να την βρείτε στις ασκήσεις.
  • [10/03/2011] Τα μαθήματα ξεκίνησαν. Το πρόγραμμα παρουσιάσεων σας ενημερώνει για το περιεχόμενο κάθε διάλεξης και τον εκάστοτε ομιλητή.

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

Ημ/νία Ομιλητής Θέμα παρουσίασης
10/3 Δ. Φωτάκης (Διαφάνειες) Εισαγωγή: διαδικαστικά, αντικείμενο, θεματολογία, παραδείγματα. [AGT, Κεφ. 1], [Roughgarden, AGT Primer].
17/3 Δ. Φωτάκης (Διαφάνειες) Linear Programming: Basics. The Simplex algorithm. [Karloff, Κεφ. 1 και 2]. Σημειώσεις του Goemans.
24/3 Δ. Φωτάκης (Διαφάνειες) Linear Programming Duality: The dual LP, weak and strong duality, complementary slackness, economic interpretation of the dual. A glimpse of the primal-dual method (shortest path). Nash equilibrium for 2-person zero-sum games. [Karloff, Κεφ. 3].
31/3 Θ. Λιανέας (Διαφάνειες) Selfish Routing and Non-Atomic Congestion Games: The model, connection to flows, existence and computation of NE, PoA, bicriteria bounds, the Braess paradox. [Roughgarden, Tardos], [Correa, Schulz, Stier-Moses], [Roughgarden, survey], [Schafer, Lecture Notes].
Existence and efficient computation of tolls [Karakostas, Kolliopoulos], [Jain, Fleischer, Mahdian], [Fleischer].
07/4 Δ. Φωτάκης (Διαφάνειες)

Χ. Αγγελιδάκης (Διαφάνειες)		 Stackelberg strategies [Roughgarden], [Karakostas, Kolliopoulos], [Swamy], [Bonifaci, Harks, Schafer].
Network design and the Braess paradox [Roughgarden], [Roughgarden, Valiant], [Fotakis, Kaporis, Spirakis].
14/4 Δ. Φωτάκης (Διαφάνειες)

M. Πετρόλια (Διαφάνειες) 		Atomic Congestion Games: Potential Games, existence, (efficient) computation, and convergence to (approximate) PNE, weighted congestion games, PoA and PoS, PoA reducing mechanisms: tolls and Stackelberg strategies.
Potential Games [Monderer, Shapley]. Σημειώσεις του Mansour.
05/5 Α. Αντωνόπουλος (Διαφάνειες Aντώνη, Voecking)
PLS-completeness of computing a PNE [Fabrikant, Papadimitriou, Talwar], [Ackermann, Roglin, Vocking].
12/5 Δ. Σακαβάλας (Διαφάνειες)

Α. Παγουρτζής (Διαφάνειες σελ. 20-44)

Χ. Λίτσας 		Coordination Mechanisms [Christodoulou, Koutsoupias, Nanavati], [Immorlica, Mirrokni, Schulz], [Azar, Jain, Mirrokni], [Caragiannis].
Selfish resource allocation in all-optical networks [Bampas, Pagourtzis, Pierrakos, Potika], [Bampas, Pagourtzis, Pierrakos, Syrganis](σελίδα 80).
Network Formation Games and the Potential Function Method [AGT, Κεφ. 19].
19/5 Χ. Τζάμος (Διαφάνειες) Introduction to Mechanism Design: social choice, Arrow’s theorem, the Gibbard-Satterthwaite theorem, VCG. [AGT, Κεφ. 9.1-9.5].
Mechanism Design without Money: single-peaked domains, connection to differentially private mechanisms, mechanisms for k-Facility Location games. [Κεφ. 10.1-10.2], [Moulin], [Procaccia and Tennenholtz], [Yu et al.], [Tennenholtz et al.].
26/6 Χ. Τζάμος (Διαφάνειες)

Ι. Παναγέας		 Combinatorial Auctions: VCG revisited, the single-minded case, iterative auctions, ascending auctions. [AGT, Κεφ. 11.1, 11.2, 11.5, 11.7].
Computationally Efficient Approximation Mechanisms: single-dimensional domains, scheduling on related parallel machines, multi-dimensional domains, combinatorial auctions, lower bounds. [AGT, Κεφ. 12.1-12.4]
02/6 Χ. Καρουσάτου (Διαφάνειες)

Θ. Γουλεάκης (Διαφάνειες)

Α. Γκόμπελ (Διαφάνειες)		 Congestion games with player specific payoffs

Distributed convergence to approximate NE [Fischer, Vocking], [Fischer, Racke, Vocking].

The Complexity of Computing a NE for Bimatrix Games: ΝΕ as a Linear Complementarity Program, the Lemke-Howson algorithm, the class PPAD and the complexity of NE. [Papadimitriou], [AGT, Κεφ. 2 και Κεφ. 3.1-3.5], [PDG], [Chen, Deng].
09/6 Σ. Δεσποτάκης

Ι. Τσελεκούνης (Διαφάνειες)		 Approximate NE equilibria [Lipton, Markakis, Mehta], [Daskalakis, Mehta, Papadimitriou], [Kontogiannis, Panagopoulou, Spirakis], [Kontogiannis, Spirakis] [Daskalakis, Papadimitriou, Mehta], [Bosse, Byrka, Markakis], [Tsaknakis, Spirakis].
16/6 Κ. Σέργης (Διαφάνειες)

Σ. Δήμος		 Sponsored Search Auctions [AGT, Κεφ. 28].
Cascading Behavior in Networks: Algorithmic and Economic Issues [AGT, Kef. 24].
23/6 Δ. Φωτάκης Other Notions, Open Problems, and Research Directions

Ασκήσεις

Τελευταία ανανέωση: 23 Ιουνίου 2011