Τμημα Πληροφορικης Πανεπιστημιου Ιωαννινων

Αλγοριθμική Θεωρία Παιγνίων

Ακαδημαϊκό Έτος 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*[Ενεργή Συμμετοχή στις Διαλέξεις]

 

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

 

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

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

 

Ημερολόγιο Μαθήματος

Διδακτική  Εβδομάδα Ημερομηνίες Διδασκαλίας Ύλη Εβδομάδας Συνοδευτικό Υλικό
Περιοχη Περιορισμενης Προσβασης
Διαφάνειες
password protected
Ασκήσεις
password protected
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

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

 

Χρήσιμο Υλικό

Βιβλιογραφία Μαθήματος

Τα βασικά εγχειρίδια του μαθήματος είναι:

 

Τα ακόλουθα βιβλία είναι επίσης πολύ χρήσιμες αναφορές για το μάθημα:

 

Ενδιαφέροντες Σύνδεσμοι Σχετικά με την (Αλγοριθμική) Θεωρία Παιγνίων

Professional Associations

AGT-related BLOGs

Journals

Conferences


 

 

 

 

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Δημιουργία και συντήρηση σελίδας μαθήματος: Σπύρος Κοντογιάννης. Ημερομηνία τελευταίας αλλαγής: 14/06/2013.