Η Μοιρασια του Θησαυρου

Πεντε πειρατες με διαφορετικες ηλικιες συμφωνουν να μοιρασουν ενα θησαυρο απο 100 χρυσα νομισματα ως εξης:

O μεγαλυτερος σε ηλικια πειρατης προτεινει πρωτος ενα τροπο μοιρασιας του θησαυρου. Αν τουλαχιστον το 50% ολων των πειρατων συμφωνησουν με την προταση, τοτε η μοιρασια γινεται οπως προτεινε ο πειρατης. 
Αν ομως δεν συμφωνησουν, τοτε ο πειρατης που εκανε την προταση ριχνεται στη θαλασσα, και η ιδια διαδικασια συνεχιζεται με τους εναπομειναντες πειρατες.
Δηλ. ο αμεσως επομενος σε ηλικια πειρατης προτεινει ενα τροπο μοιρασιας του θησαυρου. Αν τουλαχιστον το 50% των πειρατων συμφωνησουν, τοτε η μοιρασια γινεται συμφωνα με την προταση του. Αν ομως διαφωνησουν, τοτε ο πειρατης ριχνεται στη θαλασσα και συνεχιζει ο επομενος σε ηλικια πειρατης. κ.ο.κ.

Ολοι οι πειρατες ειναι απολυτως λογικοι αλλα και αιμοδιψεις. Δηλ. αν μπορουν να κερδισουν περισσοτερα αλλά ακομη και τα ιδια χρυσα νομισματα τοτε απορριπτουν την προταση και ριχνουν τον πειρατη που την εκανε, στη θαλασσα!

Πώς θα γίνει η μοιρασία?

Λυση:

Το πρόβλημα λυνεται με διερευνηση απο το τέλος προς την αρχή (Backward Deduction):

Έστω ότι οι πειρατές κατά σειρά ηλικίας είναι A,B,C,D,E.

Σταδιο 4:

Αν η μοιρασια φτασει στο τελευταιο σταδιο θα εχουν απομεινει οι πειρατες D,E.
Τοτε ο πειρατης D θα προτεινει: D=100 νομισματα και Ε=0 νομισματα.
Ο D θα εγκρινει την προταση του η οποια και θα εφαρμοσθει μιας και θα εχει εγκριθει τουλαχιστον απο το 50% των εναπομειναντων πειρατων.

Αρα ο πειρατης Ε δεν θα θελει η μοιρασια να φτασει στο Σταδιο 4 γιατι ετσι δεν θα παρει κανενα νομισμα.

Σταδιο 3:

Στο σταδιο αυτο εχουν απομενει οι πειρατες C,D,E.
Τοτε ο πειρατης C θα προτεινει: C=99, D=0 και Ε=1.
Ο πειρατης C θα εγκρινει την προταση του. Το ιδιο θα κανει και ο πειρατης E γιατι ετσι θα κερδισει 1 νομισμα, ενω αν η μοιρασια φτασει στο επομενο σταδιο δεν προκειται να κερδισει κανενα! Αρα η προταση θα εγκριθει απο τουλαχιστον το 50% των πειρατων και θα εφαρμοσθει.

Αρα ο πειρατης D  δεν θα θελει η μοιρασια να φτασει στο Σταδιο 3 γιατι ετσι δεν θα παρει κανενα νομισμα.

Σταδιο 2:

Στο σταδιο αυτο εχουν απομενει οι πειρατες B,C,D,E

Ο πειρατης B θα προτεινει: B=99, C=0, D=1, E=0.
Ο πειρατης B θα εγκρινει την προταση του. Το ιδιο θα κανει και ο πειρατης D γιατι ετσι κερδιζει 1 νομισμα, ενω στο επομενο σταδιο δεν προκειται να κερδισει κανενα. Συνεπως η προταση εγκρινεται απο τουλαχιστον το 50% των πειρατων και εφαρμοζεται.

Αρα οι πειρατες C,Ε δεν θελουν να φτασει η μοιρασια στο Σταδιο 2 γιατι ετσι δεν θα κερδισουν κανενα νομισμα.

Σταδιο 1:

Ο πειρατης A θα προτεινει: A=98, B=0, C=1,D=0, E=1.
Ο πειρατης Α θα εγκρινει την προταση του. Οι πειρατες C και Ε επισης θα εγκρινουν την προταση γιατι ετσι κερδιζουν απο 1 νομισμα, ενω αν η μοιρασια φτασει στο επομενο σταδιο δεν θα κερδισουν κανενα. Ετσι η προταση εγκρινεται απο τουλαχιστον to 50% των πειρατων και εφαρμοζεται.

Αρα η μοιρασια απο τον πειρατη Α θα γινει: Α=98, Β=0, C=1, D=0, E=1

Η παραπάνω διαδικασία απεικονίζεται γραφικά στο σχέδιο που ακολουθεί, οπου φαίνονται αναλυτικά όλα τα πιθανά στάδια της μοιρασιάς. 

Στο σχέδιο φαίνεται ότι ο κάθε πειρατής, όταν φτασει η σειρά του να προτείνει ένα τρόπο μοιρασιάς, κάνει μια τέτοια πρόταση την οποία θα αποδεχτούν τουλάχιστον 50% από τους πειρατές, ώστε η διαδικασία να λήξει, και να παραμείνει ζωντανός...αλλά και πλούσιος! 

Η λύση του προβλήματος αποτελεί Σημείο Ισορροπίας Nash (Nash Equilibrium).

Το Δίλημμα του Φυλακισμένου (Prisoner’s Dilemma)

Κλασσικό παράδειγμα της Θεωρίας Παιγνίων (Game Theory) αποτελεί το Δίλημμα του Φυλακισμένου (Prisoner’s Dilemma, PD):

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

•  Αν ο ένας καταθέσει εναντίον του άλλου (και ο άλλος δεν καταθέσει), τότε αυτός που θα καταθέσει θα αφεθει ελευθερος και ο άλλος θα καταδικαστεί σε φυλάκιση 10 χρόνων
•  Αν δεν καταθέσει κανένας από τους δυο, τότε και οι δυο θα καταδικαστούν σε φυλάκιση 1 χρόνου, για άλλα μικρά αδικήματα για τα οποία η αστυνομία έχει αποδείξεις
• Αν και οι δύο καταθέσουν ο ένας εναντίον του άλλου, τότε θα καταδικαστούν και οι δυο σε 5 χρόνια φυλάκισης, με το ελαφρυντικό της κατάθεσης

Τι θα κάνουν οι ύποπτοι?

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

Και τους δυο ύποπτους τους συμφέρει να μην καταθέσουν, έτσι ώστε να φυλακιστούν από 1 χρόνο, δηλ. να επιλέξουν (Δεν καταθέτει, Δεν καταθέτει) = (1,1).

Ο κάθε ένας όμως φοβάται, ότι αν δεν καταθέσει, μπορεί ο άλλος να καταθέσει, κι έτσι να καταδικαστεί σε 10 χρόνια φυλάκισης, δηλ. (Δεν καταθέτει, Καταθέτει) = (10,0) ή (Καταθέτει, Δεν Καταθέτει) = (0,10).

Έτσι και οι δυο επιλέγουν να καταθέσουν, οπότε η ποινή είναι 5 χρόνια φυλάκισης στον κάθε ένα, δηλ. (Καταθέτει, Καταθέτει) = (5,5)

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

Η γενική περίπτωση του Διλήμματος του Φυλακισμένου εκφράζεται ως (όπου d > a > b > c):

Το Σημείο Ισορροπίας Nash ενός παιχνιδιού (Nash Equilibrium) ορίζεται σαν το σημείο εκείνο όπου κανείς από τους δυο παίκτες δεν μετανιώνει ποτέ για την επιλογή του, ότι και αν διάλεξε ο άλλος.

Το σημείο αυτό στο αριθμητικό παράδειγμα είναι το (Καταθέτει, Καταθέτει) = (5,5), και στο γενικό παράδειγμα είναι το (Καταθέτει, Καταθέτει) = (a,a).

Γιατί?

• Αν ο Α δεν καταθέσει και ανακαλύψει ότι ο Β κατέθεσε, τότε ο Α μετανιώνει για την επιλογή του (φυλακίζεται 10 χρόνια ενώ αν είχε καταθέσει θα φυλακιζόταν μόνο 5 χρόνια). Θα ήθελε δηλ. εκ των υστέρων  να είχε κάνει διαφορετική επιλογή!
• Αν ο Α καταθέσει, τότε δεν μετανιώνει ποτέ για την επιλογή του. Αν ανακαλύψει ότι και ο Β δεν κατέθεσε, τότε απελευθερώνεται. Αν ανακαλύψει ότι και ο Β κατέθεσε, τότε φυλακίζεται 5 χρόνια (και όχι 10 αν δεν είχε καταθέσει). Δηλ. δεν θα ήθελε εκ των υστέρων να έχει κάνει διαφορετική επιλογή σε καμία περίπτωση!

Έτσι η Ισορροπία Nash προβλέπει την τελική έκβαση ενός παιχνιδιού, και όχι την καλύτερη έκβαση. 

Στο παράδειγμα των φυλακισμένων η ισορροπία είναι (Καταθέτει, Καταθέτει) ενώ η καλύτερη έκβαση θα ήταν (Δεν καταθέτει, Δεν καταθέτει), η οποία όμως δεν αποτελεί ισορροπία!