Το Πρόβλημα της κυρίας Miniver

Το "Πρόβλημα της κυρίας Miniver" είναι ένα κλασικό πρόβλημα συνδυαστικής και πιθανοτήτων που εστιάζει στη στρατηγική επιλογή αριθμών. Διατυπώθηκε αρχικά στη λογοτεχνία, στο βιβλίο Mrs. Miniver (1939) της Jan Struther, και έχει συνδεθεί με τη θεωρία παιγνίων.

Διατύπωση του Προβλήματος

Οι συμμετέχοντες καλούνται να επιλέξουν έναν αριθμό (π.χ. από το 1 έως το 100) με στόχο να είναι ο μικρότερος μοναδικός αριθμός – δηλαδή, ο μικρότερος που να έχει επιλεγεί μόνο από έναν παίκτη.

ΒΙΒΛΙΟ: GAME THEORY, Giacomo Bonanno (pdf)

In the current economic and geopolitical context, the outstanding book Game Theory by Giacomo Bonanno, which is available to the public, is well worth reading for everyone.

Click on the image.

Stanford University: "Algorithmic Game Theory" (20 video)

Lecture Videos here.

Τα Μαθηματικά στην καθημερινότητα | 9. Θεωρία παιγνίων (Game Theory)

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

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

9. Θεωρία παιγνίων (Game Theory)

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

Real-Life Applications of Game Theory

Εξηγώντας την «ισορροπία» του Νας στη Θεωρία Παιγνίων

Οι ιδέες του Τζον Νας έχουν χαραχτεί ανεξίτηλα στον κλάδο των μαθηματικών και την στρατηγική λήψη αποφάσεων, μέσω της Θεωρίας των Παιγνίων, όπου οι «παίκτες» λειτουργούν με λογική και εγωισμό, προσπαθώντας να προβλέψουν παράλληλα τι θα κάνουν οι υπόλοιποι «παίκτες». 

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

Θεωρία παιγνίων και το δίλημμα του φυλακισμένου

Πόσο κοστίζει ο εγωισμός; Γιατί εμείς οι άνθρωποι αργά ή γρήγορα πρέπει να μάθουμε να συνεργαζόμαστε; Ένα μαθηματικό παίγνιο μπορεί να απαντήσει σε αυτά τα ερωτήματα;

Καλιφόρνια 1950. Ο ψυχρός πόλεμος στα φόρτε του. Δύο Αμερικανοί μαθηματικοί, ο Merrill Meeks Flood και ο Melvin Dresher εργάζονται στο ερευνητικό κέντρο που τροφοδοτεί με μελέτες τις Αμερικανικές Ένοπλες δυνάμεις, τη RAND Corporation. Το ερευνητικό κέντρο ήθελε μελέτες στη θεωρία των παιγνίων με σκοπό την χρησιμοποίησή τους σε ενδεχόμενο πυρηνικό πόλεμο.

Θεωρία Παιγνίων: Το Δίλημμα του Φυλακισμένου

Θεωρία Παιγνίων: Το Δίλημμα του Φυλακισμένου

Θεωρία Παιγνίων: Μικτές Στρατηγικές

 

Από το «PRIME magazine», το περιοδικό των φοιτητών και αποφοίτων του Μαθηματικού Α.Π.Θ.

ΘΕΩΡΙΑ ΠΑΙΓΝΙΩΝ - Μικτές Στρατηγικές

Πηγή

Το Παίγνιο των Πειρατών

Υπάρχουν 5 ορθολογικοί πειρατές Α, Β, Γ, Δ και Ε. Βρίσκουν 100 νομίσματα χρυσού. Πρέπει να αποφασίσουν πώς θα τα διανείμουν.

Οι πειρατές έχουν μια αυστηρή σειρά αρχαιότητας: ο Α είναι ανώτερος από τον Β, ο οποίος είναι ανώτερος από τον Γ, που είναι ανώτερος από τον Δ, που είναι ανώτερος από τον Ε.

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

Καλοκαιρινές διακοπές

Ένα ζευγάρι παικτών $1$ και $2$, πρέπει να αποφασίσει μεταξύ τεσσάρων εναλλακτικών προορισμών για να περάσουν τις διακοπές τους. 

Η διαδικασία απόφασης είναι η εξής: Οι δύο παίκτες απορρίπτουν εναλλάξ από έναν προορισμό, μέχρι να απομείνει μόνο ένας. Πρώτος ξεκινά ο παίκτης 1. Οι τέσσερις εναλλακτικοί προορισμοί είναι οι Α, Β, Γ και Δ.

Μοίρασμα του κέικ

Ο απλούστερος τύπος παιχνιδιού είναι το παιχνίδι μηδενικού αθροίσματος για δύο παίκτες και δύο στρατηγικές - ένα παιχνίδι στο οποίο δύο απόλυτα λογικοί παίκτες παίζουν με σκοπό να κερδίσουν, οπότε το σύνολο του κέρδους είναι 0, δηλαδή ό,τι κερδίζει ένας παίκτης το χάνει ο άλλος. Ένα διασκεδαστικό παράδειγμα είναι γνωστό ως το παιχνίδι «μοίρασμα του κέικ». Ένα κοινό σενάριο σε πολλά νοικοκυριά είναι η διαίρεση ενός κέικ ανάμεσα σε δύο παιδιά, ώστε κανένα από τα δύο να μην νιώθει ότι το άλλο έχει πάρει μεγαλύτερο κομμάτι. Η λύση είναι μία διαδικασία δύο βημάτων: το ένα παιδί κόβει το κέικ στη μέση και το δεύτερο επιλέγει πρώτο το κομμάτι του.

Συνεταιριστικό παίγνιο

Ένα ενδιαφέρον πρόβλημα, συνεργασία του εκλεκτού φίλου Θανάση Παπαδημητρίου, τον οποίον και ευχαριστώ θερμά!

Σε ένα συνεταιρισμό ${\rm N}$ ατόμων, με $N\ge 3$ ,κάποιος χορηγός κάνει την ακόλουθη πρόταση: Κάθε μέλος του συνεταιρισμού θα συνεισφέρει προαιρετικά σε ένα ειδικό ταμείο ένα ποσό $\alpha$, το ίδιο για όλους όσοι επιθυμούν να συνεισφέρουν. Για κάθε μέλος που καταβάλλει το ποσό $\alpha$, ο χορηγός θα καταβάλει ένα επιπλέον ποσό $\beta$, με: $\alpha <\beta <(N-1)\times \alpha$.

John Forbes Nash

Ο Τζων Φορμπς Νας (John Forbes Nash Jr.) (γεν. 1928) είναι Αμερικανός μαθηματικός και οικονομολόγος. Τιμήθηκε το 1994 με το Νόμπελ Οικονομικών, μαζί με τους Ρ. Ζέλτεν και Τζ. Χαρσάνυι για τη συμβολή του στη θεωρία παιγνίων. 

Συγκεκριμένα, δημιούργησε την έννοια της ισορροπίας για παιχνίδια μη-μηδενικού αθροίσματος, ισορροπία που πήρε το όνομά του ως ισορροπία Νας. Η έννοια της ισορροπίας κατά Νας

▪ Το δίλημμα του κρατουμένου

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

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

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

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

Ποια στρατηγική πρέπει να ακολουθήσουν?

▪ Διπλό Σκάκι

"H κρυμμένη αρμονία είναι καλύτερη απ'τη φανερή"

Ηράκλειτος

Το "διπλό" ή ακριβέστερα το "διπλοκίνητο" σκάκι είναι μια παραλλαγή του σκακιού, στην οποία απλώς ο κάθε παίκτης παίζει δύο κινήσεις διαδοχικά, αντί για μία. Ξεκινάει πρώτος πάντα ο Λευκός. Δείξτε ότι υπάρχει μια στρατηγική για τον Λευκό, η οποία του εξασφαλίζει τουλάχιστον την ισοπαλία!

Σημ. Αρκεί να αποδειχτεί η ύπαρξη μιας τέτοιας στρατηγικής.

▪Περηφάνια, προκατάληψη και θεωρία παιγνίων

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

Δεν είναι ούτε ο νομπελίστας μαθηματικός John Nash, ούτε ο “πατέρας” της θεωρίας παιγνίων John von Neumann. «Πρόκειται για τη σπουδαία μυθιστοριογράφο του 19ου αιώνα Jane Austen», λέει, χωρίς δισταγμό, ο Michael Suk – Young Chwe, καθηγητής και ειδικός στη θεωρία παιγνίων στο UCLA. Η άποψη του τεκμηριώνεται στο βιβλίο «Jane Austen, Game Theorist» που κυκλοφορεί, αυτές τις μέρες, από τις εκδόσεις Princeton University Press.

«Tα μυθιστορήματα της Jane Austen είναι εγχειρίδια της Θεωρίας παιγνίων», γράφει. Και συμπληρώνει : «Η συγγραφέας ωθεί με μοναδικό τρόπο τους αναγνώστες των βιβλίων της να αξιοποιήσουν τις υψηλότερες νοητικές τους δεξιότητες και να σκεφτούν στρατηγικά.»

▪Ευρωπαιχνιδάκι

«Ρώτα πέντε οικονομολόγους και θα πάρεις πέντε διαφορετικές απαντήσεις. Έξι, αν ο ένας είναι του Χάρβαρντ.» 

Edgar R. Fiedler (διάσημος Αμερικ. οικονομολόγος) 

Παίζετε το εξής παιχνίδι: 

Στρίβετε ένα «τίμιο» νόμισμα (σαν το «ευρώ» ας πούμε..) μέχρι να φέρετε «γράμματα». Όσες φορές ρίξετε το νόμισμα, τόσα ευρώ κερδίζετε. Ας πούμε, αν φέρετε αμέσως με την πρώτη: «γράμματα», κερδίζετε $1$ ευρώ. Αν φέρετε κατά σειρά Κ-Γ κερδίζετε $2$ ευρώ, κλπ. Ποια είναι η αναμενόμενη τιμή των κερδών σας;

2η ερώτηση
Το ίδιο παιχνίδι, μόνο που τώρα ο αριθμός των ευρώ που κερδίζετε ισούται με: 

$2^{\nu -1}$

όπου ν είναι ο αριθμός ρίψεων που χρειάζεστε μέχρι να έρθει «γράμματα».

Ποια είναι σ’αυτήν την περίπτωση η αναμενόμενη τιμή κερδών; Σάς φαίνεται λογικό το αποτέλεσμα ή παράδοξο;

▪ Συμφέρει ή όχι;

Ένα νέο Καζίνο άνοιξε και προσφέρει το καινούργιο "Παιχνίδι με τα 3 κοψίματα". Σε μια κανονική 52άρα τράπουλα ο παίκτης "κόβει" 3 φορές. Αν εμφανιστεί 1 φιγούρα σε τουλάχιστον ένα κόψιμο κερδίζετε 1 ευρώ. Αν δεν εμφανιστεί φιγούρα σε κανένα κόψιμο, χάνετε 1 ευρώ. 

Θα παίζατε στο καινούργιο παιχνίδι; Ποια είναι η αναμενόμενη μέση τιμή του (ελπίδα);

Σημ: Ένα παιχνίδι θεωρείται "τίμιο"/ισορροπημένο όταν η μαθηματική του ελπίδα (expectation) είναι 0. Αυτό σημαίνει ότι μακροπρόθεσμα σ'αυτό το παιχνίδι τα κέρδη σας εξισορροπούνται από τη χασούρα  και έρχεστε " μία ή άλλη" ή "στα λεφτά σας".