Θεωρία Παιγνίων

8η ΣΥΝΕΔΡΙΑΣΗ - ΠΑΡΑΣΚΕΥΗ 1-12-2017 

Στη σημερινή μας συνάντηση ασχοληθήκαμε με ένα αθώο φαινομενικά παιχνίδι, αρχικά στην μονοδιάστατη του και κατόπιν στη δισδιάστατη εκδοχή του. 
Το παιχνίδι αυτό είναι η υλοποίηση μιας από τις απλούστερες μορφές του λήμματος Sperner το οποίο μαζί με το τοπολογικό θεώρημα του Βrower χρησιμοποιήθηκαν από τον Τζων Φορμπς Νας (John Forbes Nash) για την διατύπωση της έννοιας της Ισορροπίας Nash στη Θεωρία Παιγνίων . 
Η θεωρία παιγνίων είναι ουσιαστικά η μαθηματική μελέτη διαμόρφωσης μιας πετυχημένης στρατηγικής σε ένα παιχνίδι όπου κάθε παίκτης δεν γνωρίζει τις επιλογές των υπόλοιπων ανταγωνιστών του, αλλά επηρεάζεται από αυτές, Στη θέση του παίκτη, μπορεί να είναι ένα άτομο, ένα κράτος, ή μια ομάδα ανθρώπων κοινών συμφερόντων.
Σε κάποια συνάντηση θα δούμε και θα σχολιάσουμε, τη σχετική ταινία που αναφέρεται στη ζωή του Nash (A beautiful mind).
Αξίζει να σημειωθεί ότι ο γνωστός απόφοιτος του Βαρβακείου (1998) Κωνσταντίνος Δασκαλάκης, καθηγητής σήμερα στο Τεχνολογικό Ινστιτούτο Μασαχουσέτης, έδειξε ότι η ισορροπία Nash, σε ορισμένες περιπτώσεις, είναι υπολογιστικά αδύνατη, δηλαδή δεν υπάρχει τρόπος για να προβληθεί η ισορροπία. Για αυτή του την απόδειξη βραβεύθηκε από τον διεθνή οργανισμό ΑCΜ Αssociation for Computing Μachinery το 2008.

Χειρισμός και κανόνες 

Καθορίζεται από κοινού η αρχική περιοχή ανάπτυξης. 

Καθορίζεται η σειρά με την οποία θα παίζουν οι παίκτες (πρώτος- δεύτερος). Κάθε παίκτης έχει δικαίωμα να τοποθετήσει ένα πιόνι οποιουδήποτε χρώματος στην περιοχή ανάπτυξης του παιχνιδιού.

 Δυο διαδοχικές θέσεις πιονιών ορίζουν μια «αποδεκτή» ή «μη αποδεκτή» κατάσταση.

Ως «αποδεκτή» ορίζεται η κατάσταση: δυο διαδοχικά πιόνια είναι διαφορετικού χρώματος. Ως «μη αποδεκτή» ορίζεται η κατάσταση: δυο διαδοχικά πιόνια είναι του ίδιου χρώματος. Νικητής θεωρείται εκείνος ο παίκτης που έχει οδηγήσει τον αντίπαλό του, να μην έχει την δυνατότητα επιλογής αποδεκτής κατάστασης.

Η ανάπτυξη του παιχνιδιού

1.Οι δύο παίκτες, με αυθαίρετες επιλογές και τυχαίες κινήσεις προσπαθούν να πετύχουν τη νίκη. Αντιλαμβάνονται όμως ότι οι τυχαίες και μη λογικά αιτιολογημένες  κινήσεις οδηγούν σε αντίφαση ως προς την βεβαιότητα επίτευξης του ζητούμενου, δηλαδή της νίκης.

2. Η ανάγκη άρσης αυτής της αντίφασης οδηγεί στη συνέχεια στην ανάπτυξη έγκυρων συλλογισμών.

Προτροπή: Θυμόμαστε πάντα σε ένα άγνωστο και πιθανώς δύσκολο πρόβλημα μια βασική συμβουλή από τις στρατηγικές επίλυσης (Polya) : "Αν δεν μπορείτε να λύσετε το πρόβλημά σας, προσπαθήστε να το λύσετε στην απλούστερη εκδοχή του". 

3. Με την προτροπή αυτή κατασκευάσαμε πίνακα καταγραφής του πλήθους των επιλεγμένων οπών (αρχικό διάστημα) και των κινήσεων των παικτών :

Ανάπτυξη στρατηγικής 

Σύμφωνα με τις προηγούμενες παρατηρήσεις, διαμορφώνεται η ακόλουθη στρατηγική: 

Αν το πλήθος των επιλεγμένων οπών είναι περιττός αριθμός, τότε αποφάσισε να παίξεις πρώτος.        

Αν το πλήθος των επιλεγμένων οπών είναι άρτιος αριθμός, τότε  αποφάσισε να παίξεις δεύτερος.

Σύμφωνα με την συγκεκριμένη στρατηγική δεν υπάρχει περίπτωση ισοπαλίας

Ερωτήματα

1.Πως  "βεβαιώνεται" ότι η παραπάνω διατυπωθείσα στρατηγική έχει καθολική ισχύ; Δηλαδή ότι είναι αληθής για κάθε n το πλήθος οπών στην περιοχή ανάπτυξης του παιχνιδιού; 

2. Μπορούν τα Μαθηματικά να συνεισφέρουν σε αυτή τη βεβαιότητα και αν ναι, με ποιο τρόπο;

                                          Μαθηματική μοντελοποίηση του παιχνιδιού     

Διατύπωση σε μαθηματική γλώσσα: 

Ένας πεπερασμένος αριθμός σημείων υποδιαιρεί ένα κλειστό διάστημα σε υποδιαστήματα. Σημειώνουμε τα άκρα του αρχικού διαστήματος με διαφορετικά σύμβολα: αριστερά με 0 και δεξιά με 1, ενώ κάθε ένα από τα εσωτερικά σημεία με 0 ή 1.

Για κάθε πεπερασμένο πλήθος σημείων μιας ευθείας που βρίσκονται μεταξύ δυο σταθερών διαφορετικού συμβολισμού σημείων 0 και 1, υπάρχει τουλάχιστον μια αποδεκτή κατάσταση (δηλαδή ένα διάστημα με διαφορετικά άκρα) και το πλήθος των αποδεκτών καταστάσεων είναι περιττός αριθμός¨ (Απλούστερη εκδοχή του Λήμματος Sperner).

Σε επόμενο μάθημα θα προσπαθήσουμε να δούμε την απόδειξη...

Σημείωση: Δείτε παρακάτω το πιο διάσημο πρόβλημα της θεωρίας Παιγνίων για να το συζητήσουμε : Το δίλημμα του φυλακισμένου

Το δίλημμα του φυλακισμένου επινοήθηκε και αναλύθηκε από τους Merill Flood και Melvin Dresher, την εποχή του Ψυχρού Πολέμου, στην Καλιφόρνια του 1950, όταν δούλευαν για λογαριασμό της Rand Corporation ( του ερευνητικού κέντρου που ήθελε μελέτες στη θεωρία των παιγνίων για να τις χρησιμοποιήσει σε ενδεχόμενο πυρηνικό πόλεμο). Οι δυο μαθηματικοί ανακάλυψαν ένα απλό μαθηματικό μοντέλο σε μορφή παιγνίου στο οποίο οι παίκτες μπορούν είτε να συνεργαστούν μεταξύ τους, είτε να προδώσουν ο ένας τον άλλον.

Ο τίτλος και η εκδοχή με τις καταδικαστικές αποφάσεις φυλάκισης οφείλονται στον μαθηματικό Albert William Tucker, καθηγητή του νομπελίστα John Nash, που ήθελε να κάνει τις ιδέες του προσιτές σε ψυχολόγους του Stanford.

Η δομή του «Διλήμματος του Φυλακισμένου» αναδεικνύει την ισορροπία μεταξύ συνεργασίας και ανταγωνισμού και αποτελεί ένα πολύ χρήσιμο εργαλείο για την στρατηγική λήψης των αποφάσεων.

Μπορεί ακόμη να εφαρμοστεί σε διάφορους τομείς: από τις επιχειρήσεις, την οικονομία, τα δημοσιονομικά και τις πολιτικές επιστήμες έως τη φιλοσοφία, την ψυχολογία, τη βιολογία και την κοινωνιολογία.

Το σενάριο του διλήμματος του φυλακισμένου έχει ως εξής:

Δυο ύποπτοι (Α και Β) έχουν συλληφθεί ως μέλη μιας συμμορίας για ένα έγκλημα και κρατούνται σε χωριστά δωμάτια σε ένα αστυνομικό τμήμα, χωρίς να έχουν δυνατότητα επικοινωνίας μεταξύ τους. Οι μηνυτές έχουν έλλειψη επαρκών αποδείξεων για να τους καταδικάσουν με τη βασική κατηγορία. Ταυτόχρονα ο ανακριτής προσφέρει στους φυλακισμένους μια συμφωνία, έχοντας πει στον καθένα τα ακόλουθα:

Εάν ομολογήσεις και συμφωνήσεις να καταθέσεις εναντίον του άλλου υπόπτου, ότι διέπραξε έγκλημα, οι κατηγορίες εναντίον σου θα αποσυρθούν και θα αφεθείς ελεύθερος ατιμώρητος.

Εάν δεν ομολογήσεις και το κάνει ο άλλος ύποπτος, θα καταδικαστείς με τη μέγιστη ποινή των 3 ετών.

Εάν ομολογήσετε και οι δυο, θα καταδικαστείτε με 2 χρόνια κάθειρξη.

Εάν κανείς από τους δυο δεν ομολογήσει και οι δυο θα κατηγορηθείτε για πταίσμα και θα καταδικαστείτε με 1 χρόνο φυλακή.

Η ουσία του διλήμματος του φυλακισμένου είναι τι θα κάνουν οι ύποπτοι και η θεωρία παιγνίων ρωτά ποια είναι η αναμενόμενη ορθολογικά «βέλτιστη» στάση του καθενός από τους φυλακισμένους.
Χωρίς την ύπαρξη επικοινωνίας, η ομολογία και από τους δύο, φαίνεται να είναι η λιγότερο ριψοκίνδυνη επιλογή, και αντιπροσωπεύει μια «ισορροπία Nash», παρότι δεν είναι η βέλτιστη λύση για τους δύο !!!