Αλγοριθμική Θεωρία ΠαιγνίωνΑκαδημαϊκό Έτος 2012 -- 2013 |
[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]
Διδάσκων: | Σπύρος Κοντογιάννης |
Email -- URL -- Voice: | -- http://www.cs.uoi.gr/~kontog/ -- (26510) 08812 |
URL Μαθήματος: | http://www.cs.uoi.gr/~kontog/courses/AGT/ |
Ώρες Διαλέξεων: | Κάθε Παρασκευή 10:00--13:00 |
Χώρος Διαλέξεων: | Αίθουσα Α2 (αίθουσα μεταπτυχιακών διαλέξεων, 1ος όροφος κτιρίου) |
Ώρες Επικοινωνίας: |
[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]
Η Θεωρία Παιγνίων είναι η επιστήμη που αποσκοπεί στο να παράσχει τα κατάλληλα αναλυτικά εργαλεία τα οποία θα μας βοηθήσουν στην κατανόηση φαινομένων που παρατηρούμε σε ανταγωνιστικά περιβάλλοντα, όπως για παράδειγμα συστήματα διαχείρισης πόρων στα οποία συμμετέχουν οντότητες με προσωπικές στρατηγικές και επιδιώξεις. Μια από τις θεμελιώδεις υποθέσεις της Θεωρίας Παιγνίων είναι αυτή της εγωιστικής (ή λελογισμένης) συμπεριφοράς: Κάθε οντότητα καθορίζει τις επιλογές της ώστε να βελτιστοποιήσει το ατομικό της όφελος, δεδομένων των επιλογών που κάνουν ή των στρατηγικών που υιοθετούν οι άλλες οντότητες που συμμετέχουν στο σύστημα. Η Θεωρία Παιγνίων λοιπόν ασχολείται ακριβώς με τη μελέτη των καταστάσεων στις οποίες μπορούν να περιέλθουν συστήματα που περιλαμβάνουν εγωιστικά συμπεριφερόμενες, αλληλεπιδρώσες οντότητες. Μερικά από τα πιο σημαντικά ερωτήματα είναι λοιπόν ο ορισμός αλλά και η διαπίστωση της ύπαρξης "σημείων ισορροπίας" ολόκληρου του συστήματος, η αναζήτηση μεθόδων σύγκλισης προς αυτές τις ισορροπίες, καθώς και διάφορα ποιοτικά χαρακτηριστικά τους που προκύπτουν ως συνέπεια της εγωιστικής συμπεριφοράς.
Η Αλγοριθμική Θεωρία Παιγνίων, είναι η τομή της Πληροφορικής με τη Θεωρία Παιγνίων, εστιάζει δηλαδή στη μελέτη των φαινομένων που απασχολούν τη Θεωρία Παιγνίων από την οπτική γωνία ενός επιστήμονα της Πληροφορικής. Για παράδειγμα, δε μας απασχολεί μόνο η ύπαρξη ισορροπιών μεταξύ των οντοτήτων που συμμετέχουν, αλλά και (πχ) ο εντοπισμός μιας τέτοιας ισορροπίας σε αποδοτικό χρόνο, πώς μπορούμε να συγκλίνουμε σε κάποια από αυτές όσο το δυνατόν ταχύτερα (και ενδεχομένως με τα κατάλληλα κίνητρα για τους συμμετέχοντες), πώς μπορούμε να διακρίνουμε και ενδεχομένως να επιβάλουμε (ως διαχειριστές ενός συστήματος) ισορροπίες που είναι περισσότερο επιθυμητές για το σύστημα από άλλες, πώς μπορούμε να σχεδιάσουμε αποδοτικούς μηχανισμούς που επηρεάζουν το παιχνίδι προς όφελος ολόκληρου του συστήματος, κ.λπ.
Στόχος του παρόντος μαθήματος είναι η εξερεύνηση των βασικών εννοιών και τεχνικών που αφορούν την (αλγοριθμική) Θεωρία Παιγνίων. Θα ασχοληθούμε με διάφορες κατηγορίες παιγνίων (συνδυαστικά παίγνια, παίγνια σε εκτενή μορφή, στρατηγικά παίγνια, επαναλαμβανόμενα παίγνια, παίγνια με ελλιπή γνώση, κ.λπ.), διάφορα σκεπτικά λύσεων που επιχειρούν να περιγράψουν τις τελικές καταστάσεις του συστήματος (πχ, ισορροπίες Nash, συσχετιζόμενες ισορροπίες, εξελικτικά σταθερές καταστάσεις, κ.λπ.), μεθόδους για την αξιολόγηση της ποιότητας των λύσεων που προκύπτουν ως αποτέλεσμα της εγωιστικής συμπεριφοράς (πχ, τίμημα της αναρχίας), καθώς επίσης και τρόπους παρέμβασης στο παιχνίδι (εφαρμογή φόρων, παιχνίδια stackelberg, μηχανισμοί, κ.λπ.) προς όφελος ολόκληρου του συστήματος.
Τελικός Βαθμός = 0.45*[Βαθμός Παρουσίασης] + 0.45* [Βαθμός Γρ. Εξέτασης] + 0.1*[Ενεργή Συμμετοχή στις Διαλέξεις]
[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]
[14/6/2013] Η
τελική βαθμολογία του μαθήματος διατίθεται ηλεκτρονικά
εδώ.
[31/5/2013] Το
πρόγραμμα παρουσιάσεων των φοιτητών είναι έτοιμο (και
αναρτημένο ηλεκτρονικά), σύμφωνα και με τις δηλωθείσες
προτιμήσεις που υποβλήθηκαν από τους φοιτητές στο διδάσκοντα του μαθήματος.
Οι παρουσιάσεις θα γίνουν την Παρασκευή 14/6/2013, από τις 0900
έως τις 1600. Η παρουσία όλων των φοιτητών του μαθήματος σε
όλες τις παρουσιάσεις είναι υποχρεωτική. Θα είναι μέρος της
αξιολόγησής κάθε φοιτήτη/φοιτήτριας (πέρα από τη δική τους παρουσίαση) και η
ενεργή συμμετοχή τους στις παρουσιάσεις των συμφοιτητών τους μέσω ερωτήσεων
/ σχολίων.
[27/5/2013] Οι φοιτητές/φοιτήτριες του
μαθήματος μπορούν στην
ακόλουθη ιστοσελίδα
να μελετήσουν τη λίστα με τις υποψήφιες αναθέσεις ερευνητικών άρθρων για
παρουσίαση στην τελική ημερίδα του μαθήματος, που θα γίνει την Παρασκευή
14/6/2013. Θα πρέπει κάθε φοιτητής/φοιτήτρια να δηλώσει (με αποστολή
σχετικού μηνύματος στο διδάσκοντα) με σειρά προτίμησης τουλάχιστον 3
από τις εργασίες αυτές, μέχρι την ερχόμενη Πέμπτη 30/5/2013. Στη
συνέχεια ο διδάσκων θα κάνει την τελική ανάθεση των εργασιών στους φοιτητές
και θα ανακοινώσει το πρόγραμμα των παρουσιάσεων, στη διάλεξη της Παρασκευής
31/5/2013.
[1/5/2013] Η αναπλήρωση της αναβληθείσας διάλεξης (19/4/2013)
θα γίνει την Πέμπτη 16/5/2013, και ώρα 11:00-14:00.
[17/4/2013] Η προγραμματισμένη διάλεξη της Παρασκευής 19/4/2013
ΑΝΑΒΑΛΛΕΤΑΙ, λόγω έκτακτου κωλύματος του διδάσκοντα. Η συγκεκριμένη διάλεξη
θα αναπληρωθεί σε ημερομηνία που θα καθοριστεί μετά από συνεννόηση με τους
φοιτητές που παρακολουθούν το μάθημα (στην επόμενη προγραμματισμένη διάλεξη,
την Παρασκευή 26/4/2013).
[8/3/2013] Την Πέμπτη 14/3/2013 (10:00-13:00) θα γίνει αναπλήρωση
τη διάλεξης που χάθηκε την Παρασκευή 1/3/2013.
[8/3/2013] Η ιστοθεσία του μαθήματος έχει ήδη ενεργοποιηθεί για το
ακαδημαϊκό έτος 2013-13. Οι κωδικοί πρόσβασης στο υλικό δίνονται κατά τις
διαλέξεις.
[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]
Διδακτική Εβδομάδα | Ημερομηνίες Διδασκαλίας | Ύλη Εβδομάδας | Συνοδευτικό Υλικό | |
Διαφάνειες |
Ασκήσεις | |||
1η | 22/2/2013 | Εισαγωγή | Διαφάνειες 1ης εβδομάδας [ανάγνωση][εκτύπωση] |
|
2η | 1/3/2013 | Συνδυαστικά Παίγνια: Βασικές Έννοιες και Ιδιότητες (ΠΡΟΣΟΧΗ: Αναπλήρωση διάλεξης στις 14/3/2013) |
Διαφάνειες 2ης + 3ης εβδομάδας [ανάγνωση][εκτύπωση] |
|
3η | 8/3/2013 | Ανιδιοτελή Συνδυαστικά Παίγνια: Ισοδυναμία με ΝΙΜ Παίγνια | ||
4η | 22/3/2013 |
Παίγνια σε Εκτενή Μορφή -- Αναπαράσταση μέσω δένδρων παιγνίων -- Μετασχηματισμοί σε κανονική μορφή -- Επιλυσιμότητα μέσω προς-τα-πίσω επαγωγής -- Παίγνια δέσμευσης |
Διαφάνειες 4ης εβδομάδας [ανάγνωση][εκτύπωση] |
|
5η | 29/3/2013 |
Ισορροπία Nash -- Ορισμός ισορροπιών για παίγνια σε κανονική μορφή -- Επέκταση ισορροπιών σε παίγνια σε εκτενή μορφή |
Διαφάνειες 5ης εβδομάδας [ανάγνωση][εκτύπωση] |
|
6η | 5/4/2013 |
Αναμενόμενες ωφέλειες Χαρακτηρισμός μικτών ισορροπιών |
Διαφάνειες 6ης-7ης-8ης εβδομάδας [ανάγνωση][εκτύπωση] |
|
7η | 12/4/2013 |
Ύπαρξη μικτών ισορροπιών σε πεπερασμένα στρατηγικά παίγνια Υπολογισμός όλων των ισορροπιών σε διμητρικά παίγνια |
||
8η | 19/4/2013 |
Χειρισμός Εκφυλισμένων Διμητρικών Παιγνίων Επίλυση διμητρικών παιγνίων μηδενικού αθροίσματος |
||
9η |
16/5/2013 (εξ αναβολής) |
Παίγνια Ατελούς Πληροφόρησης |
Διαφάνειες 9ης εβδομάδας [ανάγνωση][εκτύπωση] |
|
10η | 17/5/2013 | Παίγνια Ατελούς Πληροφόρησης |
Διαφάνειες 10ης εβδομάδας [ανάγνωση][εκτύπωση] |
|
11η | 24/5/2013 | Παίγνια Συναλλαγών |
Διαφάνειες 11ης εβδομάδας [ανάγνωση][εκτύπωση] |
|
12η | 31/5/2013 | Παρουσιάσεις φοιτητών (09:00 -- 18:00) |
Διαφάνειες 12ης εβδομάδας [ανάγνωση][εκτύπωση] |
|
13η | 7/6/2013 | |||
ΕΞΕΤΑΣΗ ΜΑΘΗΜΑΤΟΣ: -- Ώρα: -- Αίθουσα: Α2 |
[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]
Τα βασικά εγχειρίδια του μαθήματος είναι:
Τα ακόλουθα βιβλία είναι επίσης πολύ χρήσιμες αναφορές για το μάθημα:
[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]
Δημιουργία και συντήρηση σελίδας μαθήματος: Σπύρος Κοντογιάννης. Ημερομηνία τελευταίας αλλαγής:
14/06/2013.