Tea an a fa .


21 views
Uploaded on:
Category: Home / Real Estate
Description
?F Live. . ?p?e. ???s????. C. D. C. D. ?F: ?????s?. . ?p?e. ???s????. C. D. C. D. . G?a t?? ?p??: 3<5 ?a? 0<1 ??a C<DG?a t?? ??as.: 3<5 ?a? 0<1 ??a C<D??a ???? pa????? D. ????
Transcripts
Slide 1

Θεωρία � αιγνίων και Εφαρμογές Θ. Κεχαγιάς Γενικό Τμήμα � ολυτεχνική Σχολή, Απθ

Slide 2

� ράσινος C D Μπλε Δφ Live C D

Slide 3

Δφ: Ανάλυση � ράσινος C D Μπλε C D Για τον Μπλέ: 3<5 και 0<1 άρα C<D Για τον � ρασ.: 3<5 και 0<1 άρα C<D Άρα όλοι παίζουν D. Αλλά …

Slide 4

Το Δίλημμα του Φυλακισμένου � ράσινος C D Μπλε Το Αρχικό Δφ C D Δύο ύποπτοι για ληστεία ανακρίνονται από την αστυνομία … Αν ομολογήσει μόνο ο ένας τον αφήνουν ελεύθερο ο άλλος τιμωρείται με 5 χρόνια φυλακή. Αν δεν ομολογήσει κανείς δεν μπορούν να αποδείξουν ότι έκαναν την ληστεία αλλά θα τους καταδικάσουν για παράνομη οπλοφορία, 2 χρόνια τον καθένα. Αν ομολογήσουν και οι δύο καταδικάζονται και οι δύο, σε 4 χρόνια φυλακή.

Slide 5

� ράσινος C D Μπλε Ένα � αίγνιο Διαφήμισης C D Δύο εταιρείες πουλούν το ίδιο προϊόν, στην ίδια τιμή. Οι συνολικές πωλήσεις είναι 10 4 τεμάχια και αποφέρουν κέρδος 6 · 10 4 Euro. Αν καμμία εταιρεία δεν κάνει διαφημιστική καμπάνια, οι αγοραστές μοιράζονται εξίσου μεταξύ των δύο. Αν μόνο η � ράσινη εταιρεία κάνει διαφημιστική καμπάνια όλοι οι αγοραστές θα προτιμήσουν το προϊόν της … αλλά η καμπάνια στοιχίζει 10 4 Euro. Αν και η � ράσινη και η Μπλε εταιρεία κάνει διαφημιστική καμπάνια, οι αγοραστές δεν θα αλλάξουν προμηθευτή.

Slide 6

Δύο χρήστες θέλουν να στείλουν ο καθένας το δικό τους μήνυμα. Υπάρχει μόνο ένα διαθέσιμο κανάλι. Το κόστος αποστολής είναι 0.1 Euro . Αν μόνο ο � ράσινος στείλει το μήνυμα του, θα έχει κέρδος 1 Euro . Αν και ο � ράσινος και ο Μπλε στείλουν μήνυμα, το κανάλι θα μπλοκάρει και κανένα μήνυμα δεν θα περάσει. Ένα � αίγνιο Τηλεπικοινωνιών � ράσινος C D Μπλε C Τηλεπικοινωνίες (Channel Access) D

Slide 7

� ράσινος C D Μπλε Και Άλλα � αίγνια C Η Μάχη των Φύλων D � ράσινος C D Μπλε C Chicken D

Slide 8

� ράσινος C D Μπλε � αίγνια Μηδενικού Αθροίσματος C D � ράσινος C D Μπλε C D

Slide 9

� ράσινος C D Μπλε � αίγνια Μηδενικού Αθροίσματος C D � ράσινος C D Μπλε C D

Slide 10

� αίγνιο με Ν παίκτες

Slide 11

Το γενικό 2χ2 Συμμετρικό � αίγνιο

Slide 12

Το γενικό M Χ N Συμμετρικό � αίγνιο

Slide 13

Επαναλαμβανόμενο Δφ � ράσινος C D Μπλε C D Εδώ είναι ο πίνακας για το παίγνιο που αποτελείται από δύο γύρους Δφ.

Slide 14

Θεωρία � αιγνίων: Η μαθηματική θεωρία της σύγκρουσης και της συνεργασίας Ότι είναι η Θεωρία � ιθανοτήτων για τα παίγνια τύχης, είναι η Θεωρία � αιγνίων για τα στρατηγικά παίγνια Θεωρία � αιγνίων

Slide 15

Κεντρική Βελτιστοποίηση : Ενας «παίκτης» επιλέγει x 1 , x 2 για να μεγιστοποιήσει την f ( x 1 , x 2 ) Κατανεμημένη Βελτιστοποίηση : Ο «παίκτης» 1 επιλέγει την x 1 , για να μεγιστοποιήσει την f ( x 1 , x 2 ) και ο «παίκτης» 2 επιλέγει την x 2 , για να μεγιστοποιήσει την f ( x 1 , x 2 ). Εγωιστική Βελτιστοποίηση : Ο «παίκτης» 1 επιλέγει την x 1 , για να μεγιστοποιήσει την f 1 ( x 1 , x 2 ) και ο «παίκτης» 2 επιλέγει την x 2 , για να μεγιστοποιήσει την f 2 ( x 1 , x 2 ). Θεωρία � αιγνίων

Slide 16

Οικονομία (καρτέλ, ολιγοπώλια, διαφημιστικές εκστρατείες) Κούρσα εξοπλισμών (π.χ. Ελλάδα-Τουρκία) Χρήση προηγμένων τεχνολογιών πληροφορικής (Δφ με Ν παίκτες, μεγάλο Ν). Linux versus Windows C versus Fortran Peer-To-Peer ( να ανοίξω τον HD μου ή όχι?). Χρηματοδότηση έρευνας. Εκπαιδευτικές Εφαρμογές Κλέψιμο στις εξετάσεις. � ληθωρισμός βαθμών Κάθε περίπτωση στην οποία περισσότεροι του ενός παίκτες προσπαθούν να βελτιστοποιήσουν ο καθένας την δική του συνάρτηση κέρδους . Εφαρμογές της Θεωρίας � αιγνίων

Slide 17

Διάφορα � αίγνια Φτηνές υπεραστικές κλήσεις μετά τις 23:00 και συμφόρηση γραμμών. � ότε να πάρω τηλέφωνο, πριν ή μετά τις 23:00? Pennypot : Δύο παίκτες εναλάσσονται, σε κάθε γύρο ο ένας εκ των δύο ή προσθέτει ένα ευρώ στην μπάνκα ή παίρνει όλα τα ευρώ. Δφ με ανταλλαγές αγαθών ( Hofstadter 716) Γιατί στα στρατόπεδα συγκέντρωσης οι έγκλειστοι δεν επιτέθηκαν στου φρουρούς? Κανείς δεν θέλει να είναι στην πρώτη γραμμή σε μια διαδήλωση, αν όμως δεν σχηματιστεί πρώτη γραμμή δεν θα υπάρχει διαδήλωση. Κυκλοφοριακά: τήρηση/??�αραβίαση του κόκκινου, οδήγηση σε μια πλευρά του δρόμου. Γενικότερα: εγκαθίδρυση προτύπων, κανονισμών, (άγραφων) νόμων, ηθικής. Ειδικότερα: σταθεροποίηση γλώσσας. � αιχνίδια με μάθηση. � αιχνίδια με χωρική δομή.

Slide 18

� αίγνια Μηδενικού Αθροίσματος Μέγιστο ελάχιστο κέρδος του Α Ελάχιστη μέγιστη ζημία του Β Σαγματικό σημείο (saddle point)

Slide 19

� αράδειγμα 1 (έχει Minimax λύση) Λύση Minimax με Καθαρές Στρατηγικές � αράδειγμα 2 (Δεν έχει Minimax λύση)

Slide 20

Οι μικτές στρατηγικές είναι κατανομές πιθανοτήτων Το προσδοκώμενο κέρδος του Α είναι: Λύση Minimax με Μικτές Στρατηγικές Θεώρημα Minimax: Για κάθε παίγνιο μηδενικού αθροίσματος υπάρχουν p * ,q * τ.ω. Η αξία του παιγνίου για τον Α ισούται με και επιτυγχάνεται όταν

Slide 21

� αράδειγμα με Μικτές Στρατηγικές =1/5 =3/5 =17/5 Η αξία του παιγνίου για τον Α ισούται με

Slide 22

Μια στρατηγική είναι σημείο ισορροπίας Nash ανν για κάθε παίκτη i � αίγνια Μη Μηδενικού Αθροίσματος: Ισορροπία Nash όπου : Κέρδος του παίκτη i στρατηγική του παίκτη i Η βέλτιστη απόκριση του παίκτη i στις στρατηγικές s - i είναι η στρατηγική s i η οποία ικανοποιεί : Σημείο ισορροπίας Nash : Ένα σύνολο αμοιβαία βέλτιστων αποκρίσεων Ένα παίγνιο μπορεί να έχει περισσότερα από ένα σημεία ισορροπίας Nash

Slide 23

Θεώρημα: Κάθε πεπερασμένο παίγνιο Ν παικτών έχει τουλάχιστον ένα σημείο ισορροπίας Nash (στον χώρο των μικτών στρατηγικών). � ροσοχή: Ένα παίγνιο μπορεί να έχει περισσότερα από ένα σημεία ισορροπίας Nash

Slide 24

Μια στρατηγική s (1) υπερέχει κατά Pareto της s ( 2 ) ανν για κάθε παίκτη i � αίγνια Μη Μηδενικού Αθροίσματος: Βελτιστότητα Pareto Μια στρατηγική s * είναι Pareto βέλτιστη ανν δεν υπάρχει στρατηγική s η οποία υπερέχει της s * κατά Pareto . Δηλ. ένα σημείο είναι Pareto βέλτιστο ανν κανείς παίκτης δεν μπορεί να βελτιώσει το κέρδος του χωρίς να ελαττώσει το κέρδος κάποιου άλλου παίκτ

Recommended
View more...