Πληροφορίες μαθήματος
Κωδικός
ΗΥ-693
Όνομα
Εισαγωγή στη Θεωρία Παιγνίων
Πρόγραμμα
Μεταπτυχιακό
Περιοχές
Αλγοριθμική και Ανάλυση Συστημάτων
Δίκτυα Υπολογιστών και Τηλεπικοινωνίες
Περιγραφή
Περιγραφή Αντικειμένου Το μάθημα είναι μια εισαγωγή στην θεωρία παιγνίων, από τις πιο βασικές έννοιες σε πιο προχωρημένες οι οποίες μπορούν να χρησιμοποιηθούν στην μοντελοποίηση και στην επίλυση προβλημάτων που είναι χαρακτηριστικά στις ασύρματες επικοινωνίες, στην επιστήμη των υπολογιστών και στα οικονομικά. Ιδιαίτερα, θα μελετήσουμε έννοιες όπως την στρατηγική σκέψη, την ορθολογική λήψη αποφάσεων, τα κέρδη, τις συναρτήσεις ωφελιμότητας, τις προτιμήσεις, τις αγνές/μικτές στρατηγικές, τις κυρίαρχες στρατηγικές, τις στρατηγικές καλύτερης απόκρισης, τα παιχνίδια κανονικής μορφής, τις έννοιες επίλυσης ((προσεγγιστικά) σημεία ισορροπίας κατά Nash, Correlated σημεία ισορροπίας), παραδείγματα παιχνιδιών (συμμετρικά παιχνίδια δύο παικτών, παιχνίδια μηδενικού αθροίσματος), μοντελοποίηση των παιχνιδιών μηδενικού αθροίσματος μέσω γραμμικού προγραμματισμού και το Minimax θεώρημα. Επίσης, θα συζητήσουμε αλγόριθμους για τον υπολογισμό των εννοιών επίλυσης (υπολογισμός αγνών σημείων ισορροπίας κατά Nash, Lemke-Howson αλγόριθμος, αλγόριθμοι για προσεγγιστικά σημεία ισορροπίας κατά Nash, Correlated σημεία ισορροπίας μέσω γραμμικού προγραμματισμού), εκτεταμένα παιχνίδια και backward induction, επαναλαμβανόμενα παιχνίδια, μέτρηση αποδοτικότητας των εννοιών επίλυσης (Price of Anarchy, Price of Stability), εγωιστική δρομολόγηση (ατομικά/μη ατομικά παιχνίδια, Wardrop σημείο ισορροπίας, Braess paradox), σχεδιασμός μηχανισμών (δημοπρασίες πρώτης τιμής, δημοπρασίες δεύτερης τιμής), θεωρία αντιστοίχησης (Gale-Shapley αλγόριθμος). Τέλος, θα συζητήσουμε εφαρμογές της θεωρίας παιγνίων σε προβλήματα οικονομικών και ασύρματης δικτύωσης.
Μαθησιακοί Στόχοι
Μετά το μάθημα, οι φοιτητές θα είναι ικανοί να μοντελοποιήσουν προβλήματα χρησιμοποιώντας μαθηματικά εργαλεία της θεωρίας παιγνίων. Το μάθημα θα καλλιεργήσει στους φοιτητές τον στρατηγικό τρόπο σκέψης και θα δώσει την γνώση αλγορίθμων που χρησιμοποιούνται στην αντιμετώπιση χαρακτηριστικών προβλημάτων στα οικονομικά και στις τηλεπικοινωνίες, όπως προβλήματα που δημιουργούνται από την αλληλεπίδραση επιχειρήσεων ή από την κατανομή πόρων στις ασύρματες επικοινωνίες.
After the course, the students will be able to formulate problems using game theoretical tools. The course will let the students acquire a strategical thinking and reasoning as well as the knowledge of several state-of-art algorithms which can be leveraged to tackle typical economical and telecommunication problems, such as those derived from the interaction between firms or from the resource allocation processes in wireless communication.
Σχέση με άλλα μαθήματα που διδάσκονται ή διδάχθηκαν στο παρελθόν
Πιθανότητες, γραμμική άλγεβρα, Ασύρματες επικοινωνίες.
Probability theory, linear algebra, wireless communications.
Ύλη Διαλέξεων
Εβδομάδα |
Σύντομη περιγραφή ύλης διδακτικής εβδομάδας |
1 |
Introduction to game theory, strategic thinking and rational decision making |
2 |
Normal-form games |
3 |
Solution concepts ((Approximate) Nash equilibria, Correlated equilibria) |
4 |
Examples of games (symmetric bimatrix games) |
5 |
Zero-sum games (Linear programming formulation, Minimax theorem) |
6 |
Algorithms for computing solution concepts |
7 |
Extensive games |
8 |
Repeated games |
9 |
Inefficiency of solution concepts (Price of Anarchy, Price of Stability) |
10 |
Selfish routing (Atomic/non atomic games, Wardrop equilibrium, Braess paradox) |
11 |
Mechanism design (First price auctions, Second price auctions) |
12 |
Matching theory (Gale-Shapley algorithm) |
13 |
Applications of game theory |
Προτεινόμενα Συγγράμματα
- (υποχρεωτικό)
- ...
- (συνιστώμενο)
Προτεινόμενες Ασκήσεις
Εβδομάδα |
Σύντομη περιγραφή |
1,2 |
|
3,4 |
Άσκηση 1 (Επίλυση σε χαρτί) Assignement 1 |
5,6 |
|
8,9 |
Άσκηση 2 (Επίλυση σε χαρτί) Assignement 2 |
10,11 |
|
12,13 |
Άσκηση 3 (Επίλυση σε χαρτί) Assignement 3 |
|
|
Τρόπος Αξιολόγησης
Πρόοδος (M) |
Midterm (M) |
|
Ασκήσεις (Α) |
Assignements (A) |
|
Τελική Εξέταση(T) |
Final Exam (T) |
|
Προτζεκτ (P) |
Project (P) |
Προαιρετικό - optional |
Τελικός Βαθμός |
Final Grade |
max(30%A+20%M+50%Τ, 30%A+20%M+30%T+20%P) |
ECTS
6
Προαπαιτούμενα
Δεν έχει προαπαιτούμενα