|
Title: Προβλήματα Συνεργασίας Post by: thanasiskehagias on April 03, 2006, 16:43:20 pm OK, να ένα άλλο πρόβλημα, για την ακρίβεια μια σειρά ΤΡΙΩΝ προβλημάτων. Μπορούμε να τα ονομάσουμε γρίφους, με την έννοια ότι έχουν μια καλώς ορισμένη λύση, αλλά πρέπει να σας προειδοποιήσω ότι έχουν γίνει αντικείμενο εκτεταμενης έρευνας επειδή πολλοί είναι αυτοί που δεν παραδέχονται την "κλασσική" λύση.
Και τα τρία προβλήματα σχετίζονται με την έννοια της συνεργασίας, για την οποία συζητήσαμε και στον γριφο με τους ληστές. ==================== 1ο Πρόβλημα ==================== Ένας ευεργέτης κάνει την εξής πρόταση στον Αλέκο και στον Βασίλη (απο εδώ και πέρα θα τους ονομάζω παίκτη Α και παίκτη Β). Ο Α γράφει σε ένα κομμάτι χαρτί (κρυφά) το γράμμα C (Cooperation, συνεργασία) ή D (Defection, λιποταξία). Το ίδιο κάνει και ο Β. Κατόπιν δίνουν τα χαρτιά (τις "κινήσεις" τους) στον ευεργέτη. Υπάρχουν τέσσερα ενδεχόμενα: 1) Αν και οι δύο γράψουν C, ο ευεργέτης δίνει στον καθένα 300 Euro. 2) Αν ο Α γράψει C και ο Β γράψει D, o A παίρνει 0 Euro και ο Β 500 Euro. 3) Συμμετρικά αν ο Β γράψει C και ο Α γράψει D. 4) Αν και οι δύο γράψουν D, παίρνουν από 100 Euro. Το παιχνίδι μπορεί να παρασταθεί από την παρακάτω πίνακα.
όπου οι γραμμές αντιστοιχούν στις κινήσεις του Α, οι στήλες στις κινήσεις του Β και σε κάθε κελλί ο πρώτος αριθμός είναι το κέρδος του Α και ο δεύτερος το κέρδος του Β. Οι παίκτες αποκαλύπτουν τις κινήσεις τους ταυτόχρονα. Τυχόν συμφωνίες που θα κάνουν πριν παίξουν δεν είναι δεσμευτικές!!! ΕΡΩΤΗΣΗ: Τι πρέπει να παίξει ο κάθε παίκτης για να μεγιστοποιήσει το κέρδος του? ==================== 2ο Πρόβλημα ==================== Το δεύτερο παιχνίδι αποτελείται από 10 (γενικότερα Ν) συνεχείς γύρους του 1ου παιχνιδιού. ΕΡΩΤΗΣΗ: Τι πρέπει να παίξει ο κάθε παίκτης για να μεγιστοποιήσει το συνολικό κέρδος του? ==================== 3ο Πρόβλημα ==================== Στο τρίτο παιχνίδι παίζεται ένας άγνωστος αριθμός γύρων του 1ου παιχνιδιού. Για την ακρίβεια μετά κάθε γύρο, υπάρχει πιθανότητα 1/2 (γενικότερα p) το παιχνίδι να λήξει. ΕΡΩΤΗΣΗ: Τι πρέπει να παίξει ο κάθε παίκτης για να μεγιστοποιήσει το συνολικό αναμενόμενο κέρδος του? ================================================== Ξέρω την "σωστή" απάντηση για τα 2 πρώτα προβλήματα, αλλά όχι για το 3ο (αν και είμαι σίγουρος ότι κάποιος έχει δώσει τουλάχισοτν μια απάντηση). Ξαναλέω ότι τα παραπάνω προβλήματα έχουν συζητηθεί ευρύτατα. Τονίζω ότι ο κάθε παίκτης έχει ως μόνο σκοπό την μεγιστοποίηση του κέρδους του. Θα πρότεινα και πάλι να μου στείλετε απαντήσεις με Private Message στις επόμενες 2-3 μέρες, κατόπιν θα συνοψίσω σε ένα post και (αν υπάρχει ενδιαφέρον) θα ακολουθήσει συζήτηση. Θ Title: Re: Προβλήματα Συνεργασίας (Απάντηση στο 1ο ερώτημα) Post by: thanasiskehagias on April 08, 2006, 12:20:47 pm Δεν είχα μεγάλη ανταπόκριση στα "Προβλήματα Συνεργασίας". Κρίμα, γιατί είναι ωραία προβλήματα που εγείρουν σοβαρά φιλοσοφικά ερωτήματα.
Anyway, έλαβα μια εκτενή απάντηση από τον Junior, Την οποία θα παραθέσω αυτούσια στο επόμενο μήνυμα. Ωστόσο ας δώσω καταρχήν την απάντηση στο ερώτημα 1 και 2. Θυμίζω ότι ουσιαστικά παίζεται ένα ΠΑΙΓΝΙΟ μεταξύ των παικτών Α και Β, με πίνακα ανταμοιβών τον εξής:
όπου ο Α επιλέγει μια γραμμή του πίνακα και ο Β επιλέγει μια στήλη -- κατόπιν στο αντίστοιχο κελλί του πίνακα ο πρώτος αριθμός είναι η ανταμοιβή (σε Ευρώ) του παίκτη Α και ο δεύτερος η ανταμοιβή του Β. Οι επιλογές γίνονται ταυτόχρονα (π.χ. οι Α και Β γράφουν κρυφά ο καθένας σε ένα χαρτί C ή D και τα αποκαλύπτουν ταυτόχρονα). Συμφωνίες πριν το παιχνίδι ΔΕΝ είναι δεσμευτικές. Το 1ο ερώτημα ήταν: "αν το παιχνίδι παιχτεί ΜΙΑ φορά", ποια κίνηση μεγιστοποιεί το βέβαιο κέρδος κάθε παίκτη. Η απάντηση σε αυτό το ερώτημα είναι: η κίνηση D. Και ο λόγος είναι ο εξής. Έστω ότι είμαι ο παίκτης Α. Εξετάζω δύο περιπτώσεις: ι) ο Β παίζει C. Δηλ. είμαστε στην πρώτη στήλη. Αν παίξω C παίρνω 300, αν παίξω D παίρνω 500. Αρα καλύτερα να παίξω D. ιι) ο Β παίζει D. Δηλ. είμαστε στην δεύτερη στήλη. Αν παίξω C παίρνω 0, αν παίξω D παίρνω 100. Αρα καλύτερα να παίξω D. Δηλ. σε κάθε περίπτωση, καλύτερα να παίξω D! (Αυτή είναι και η λύση που πρότεινε ο Junior). Υπάρχει ένα ενδεχόμενο παράδοξο στην παραπάνω λύση. Αν ο κάθε παίκτης παίξει εγωιστικά, τελικα θα καταλήξουμε στις κινήσεις (D,D) και ο κάθε παίκτης θα πάρει από 100. Ανυπήρχε εμπιστοσύνη μεταξύ των παικτών, θα έπαιζαν και οι δύο C και με κινήσεις (C,C) θα έπαιρναν από 300, που είναι καλύτερο και για τους δύο. Όμως αν ο (π.χ.) Α έχει λόγο να πιστεύει ότι ο Β θα παίξει C, τότε είναι και πάλι καλύτερα γι' αυτόν (τον Α) να παίξει C. Ετσι τελικά φαίνεται ότι είναι αδύνατο να δικαιολογηθεί λογικά η κίνηση αμοιβαίας εμπιστοσύνης. Οι εφαρμογές σε καθημερινά προβλήματα νομίζω ότι είναι προφανείς. Για ιστορικούς λόγους, το παραπάνω παίγνιο (και το "παράδοξο") αναφέρονται ως "δίλημμα του φυλακισμένου" (Prisoner's Dilemma). Υπάρχει τεράστια βιβλιογραφία πάνω στο θέμα, αν παρατηρήσω ενδιαφέρον θα ποστάρω σχετικά links. Θ Title: Re: Προβλήματα Συνεργασίας (η απάντηση του Junior) Post by: thanasiskehagias on April 08, 2006, 12:22:53 pm (Έχει ΜΕΓΑΛΟ ενδιαφέρον, αν και είναι εξαιρετικά εκτενής αξίζει να την διαβάσετε!)
================================================= « Sent to: thanasiskehagias on: April 07, 2006, 16:48:35 PM » Για τα "προβλήματα συνεργασίας" Πρόβλημα 1: Ανεξάρτητα από το τι θα γράψει ο άλλος παίκτης, ο κάθε παίκτης παίρνει περισσότερα γράφοντας D. Άρα ο καθένας έχει μεγαλύτερο συμφέρον γράφοντας D. Οποιαδήποτε συμφωνία γίνει δεν είναι δεσμευτική και η τήρησή της ή όχι δεν έχει επίπτωση στο παιχνίδι, αφού το αν τηρήθηκε γίνεται γνωστό μετά το τέλος του παιχνιδιού. Πρόβλημα 2: Στο πρόβλημα αυτό δεν κατάφερα να βρω μια ολοκληρωμένη λύση, αλλά μόνο μια προσέγγιση στη λύση, που δεν ξέρω αν μπορεί να επεκταθεί σε κάτι ολοκληρωμένο. Στη 10η επανάληψη του παιχνιδιού το πρόβλημα γίνεται ίδιο με το πρόβλημα 1. Θεωρούμε ότι πριν από κάθε γύρο γίνεται συμφωνία μεταξύ των παικτών, η οποία όμως δεν είναι δεσμευτική. Επίσης θεωρούμε ότι αν κάποιος δεν τηρήσει τη συμφωνία, τότε ο άλλος παίκτης δεν περιμένει από αυτόν να τηρήσει καμία συμφωνία στο μέλλον, οπότε θα ρίχνει συνεχώς D. Για να γίνει σε κάποιο γύρο συμφωνία πρέπει να συμφέρει όσο το δυνατόν περισσότερο και τους δύο. Δηλαδή η καλύτερη συμφωνία που μπορεί να γίνει είναι να γράψουν και οι δύο C. Επομένως στην αρχή για κάποιον αριθμό γύρων θα γράφουν και οι δύο C, στον επόμενο γύρο ένας από τους δύο ή και οι δύο θα προδώσουν τον άλλο και στη συνέχεια θα γράφουν και οι δύο D. Επειδή ο κάθε παίκτης, για οποιαδήποτε στρατηγική του, δεν ξέρει ποιο είναι το ακριβές ποσό που θα πάρει, δεν μπορεί να προβλέψει ποια στρατηγική θα του δώσει το μέγιστο κέρδος. Το μέγιστο σίγουρο κέρδος προφανώς είναι 100ν, αν γράφει συνέχεια D. Για οποιαδήποτε άλλη στρατηγική υπάρχει η περίπτωση ο άλλος παίκτης να γράφει συνέχεια D, άρα ο πρώτος παίκτης θα πάρει λιγότερα από 100ν. Όμως, με τη στρατηγική “γράφω συνέχεια D” γίνεται μικρότερο και το μέγιστο δυνατό κέρδος, αφού ο άλλος παίκτης θα σταματήσει να εμπιστεύεται τον πρώτο και θα γράφει και αυτός D. Το καλύτερο θα ήταν να υπολογίσουμε το αναμενόμενο κέρδος, δηλαδή το ζυγισμένο μέσο όρο των κερδών με αντίστοιχα βάρη τις πιθανότητές τους. Θεωρούμε ότι ο κάθε παίκτης έχει πιθανότητα pκ να σχεδιάζει να γράψει πρώτη φορά D στον κ γύρο. Είναι Σpi = 1, αφού στον τελευταίο γύρο σίγουρα θα γράψει D. Οι αντίστοιχες πιθανότητες για τους δύο παίκτες είναι οι ίδιες, αφού σκέφτονται με τον ίδιο τρόπο και αυτό το ξέρουν. - Αν ο πρώτος παίκτης γράψει D από τον πρώτο γύρο, τότε αν γράψει και ο άλλος παίκτης D, ο πρώτος θα πάρει 100ν ευρώ. Αν ο άλλος παίκτης γράψει στον πρώτο γύρο C (αλλά αναγκαστικά στους επόμενους γύρους D), τότε ο πρώτος παίκτης θα πάρει 100ν + 400. Το αναμενόμενο κέρδος είναι (100ν)*p1 + (100ν + 400)* (1-p1) = 100ν + 400 * (1-p1) - Αν ο πρώτος παίκτης γράψει στον πρώτο γύρο C και μετά συνέχεια D, τότε υπάρχουν τρία ενδεχόμενα: Ο δεύτερος παίκτης γράφει καμία, μία ή δύο φορές C. Στις τρεις αυτές περιπτώσεις το κέρδος του πρώτου παίκτη είναι αντίστοιχα 100ν – 100, 100ν + 200, 100ν + 600. Το αναμενόμενο κέρδος είναι (100ν-100)*p1 + (100ν+200)*p2 + (100ν+600)*(1-p1-p2) = 100ν + 600 – 700p1 – 400p2. - Αν ο πρώτος παίκτης σχεδιάζει να γράψει πρώτη φορά D στον κ (2<κ<10) γύρο, τότε υπάρχουν τρία ενδεχόμενα: Ο δεύτερος παίκτης μπορεί να γράψει πρώτη φορά D α) στον λ (λ<κ) γύρο β) στον κ γύρο γ) στον κ+1 γύρο. Τα αντίστοιχα κέρδη του πρώτου παίκτη στις τρεις αυτές περιπτώσεις είναι: α) 300*(λ-1)+100*(ν-λ) = 200λ + 100ν – 300 β) 300*(κ-1) + 100*(ν-κ+1) = 200κ + 100ν - 200 γ) 300*(κ-1) + 500 + 100*(ν-κ) = 200κ +100ν + 200 Το αναμενόμενο κέρδος είναι (200*1 + 100ν – 300)*p1 + (200*2 + 100ν -300)*p2 + … + [200*(κ-1) + 100ν – 200]*p(κ-1) + (200κ +100ν – 200)*pκ + (200κ + 100ν + 200)*[p(κ+1)+p(κ+2)+…+p(ν)] - Αν ο πρώτος παίκτης σκοπεύει να γράψει πρώτη φορά D στο ν γύρο, τότε υπάρχουν δύο ενδεχόμενα: Ο δεύτερος παίκτης γράφει πρώτη φορά D στο λ (λ<ν) γύρο ή στο ν γύρο. Το κέρδος του πρώτου παίκτη στην πρώτη περίπτωση είναι 300*(λ-1) + 100*(ν-λ) = 200λ + 100ν – 300, ενώ στη δεύτερη περίπτωση είναι 300*(ν-1) + 100 = 300ν – 200. Το αναμενόμενο κέρδος είναι (200*1 + 100ν – 300)*p1 + (200*2 + 100ν -300)*p2 + … + [200*(ν-1) + 100ν – 200]*p(ν-1) + (300ν – 200)*pν. Εκφράσαμε τα αναμενόμενα κέρδη μ1, μ2, …, μν ως συναρτήσεις των p1, p2, …, pν. Αν θεωρήσουμε ότι η πιθανότητα ένας παίκτης να ακολουθήσει κάποια στρατηγική είναι ανάλογη του αναμενόμενου κέρδους που θα έχει, τότε, για να ισχύει Σp = 1, πρέπει pκ = μκ/Σμ, για κάθε κ από 1 έως ν. Αντικαθιστώντας τα μ1, μ2, …, μν παίρνουμε ν εξισώσεις με ν μεταβλητές. Οι εξισώσεις αυτές δεν είναι γραμμικές, γι’ αυτό και δεν μπορούμε να προβλέψουμε τον αριθμό των λύσεων. Αν υπάρχει μοναδική λύση του συστήματος, τότε εύκολα υπολογίζουμε τα μ1, μ2, …, μν και ο παίκτης 1 επιλέγει τη στρατηγική που του δίνει μεγαλύτερο αναμενόμενο κέρδος. Αν υπάρχουν περισσότερες από μία λύσεις ή καμία λύση δεν μπορεί να πάρει κάποια απόφαση ο παίκτης. Title: Re: Προβλήματα Συνεργασίας (Υπόδειξη για το 2ο ερώτημα) Post by: thanasiskehagias on April 08, 2006, 12:44:31 pm Θυμιζω ότι το δεύτερο ερώτημα είναι: πως πρέπει να παίξει ο κάθε παίκτης αν το παίγνιο επαναληφθεί 10 φορές. Ο Junior έχει πιάσει αυτό που εγώ (και πολλοί άλλοι) θεωρούν την βασική ιδέα, αλλά υπάρχει μια πιο απλή ανάλυση. Δεν θα την δώσω εδώ, αλλά θα δώσω την λύση για την περίπτωση που το παίγνιο επαναλαμβάνεται ΔΥΟ φορές.
Η βασική ιδέα είναι ότι στον τελευταίο γύρο του παιχνιδιού, ο κάθε παίκτης πρέπει "λογικά" να παίξει D. Αυτή η ιδέα μπορεί να διατυπωθεί πολύ ξεκάθαρα, αν θεωρήσουμε ότι οι δύο γύροι του αρχικού παιχνιδιού μπορούν να περιγραφούν ως ΕΝΑ παίγνιο, με ΕΝΑ πίνακα ανταμοιβών. Στο νέο παίγνιο, ο κάθε παίκτης έχει 4 δυνατές κινήσεις: CC, CD, DC, DD (π.χ. CC σημαίνει στην πρώτη κίνηση παίζω C και στην δεύτερη το ίδιο, CD σημαίνει ότι παίζω πρώτα C και μετά D κτλ.) Μπορώ να σχηματίσω τον πίνακα ανταμοιβών για το νέο παιγνιο από τον αρχικό πίνακα. Π.χ. Έστω ότι ο Α παίζει CC και ο B παίζει CD. Αυτό σημαίνει ότι στο πρώτο γύρο ο Α θα πάρει 300 και ο Β 300, ενώ στον δεύτερο γύρο ο Α θα πάρει 0 και ο Β 500. Με αντίστοιχο τρόπο υπολογίζω τις ανταμοιβές και για τις υπόλοιπες δυνατές κινήσεις. Είναι
Όπως ακριβώς και στην περίπτωση του ενός γύρου, ότι και αν παίξει ο Β, ο Α έχει πάντα συμφέρον να παίξει DD (η DD είναι κυρίαρχη στρατηγική). Το ίδιο φυσικά ισχύει και για τον Β, οπότε "λογικά" πρέπει να παίζουν πάντα D και η συνεργασία δεν έχει λογική βάση. Φαντάζομαι ότι βλέπετε πως αυτό γενικεύεται για Ν γύρους. Θα έλεγα, αν κάποιος έχει σχόλια, εναλλακτικές λύσεις κτλ. να τα δημοσιεύσει πλέον ανοιχτά (όχι με personal message). Θ |