Βασικές Έννοιες Θεωρίας Παιγνίων › courses › old › 2011-12... · Εάν δε συνεργαστώ , παίρνω 4 χρόνια Βασικές Έννοιες

Παύλος Σ. Εφραιμίδης

Βασικές Έννοιες Θεωρίας Παιγνίων

Παύλος Σ. Εφραιμίδης

ΕΚΑΠΒασικές Έννοιες Θεωρίας Παιγνίων

Περιεχόµενα

� Τι είναι η θεωρία παιγνίων

� Ο ρόλος ενός µαθηµατικού µοντέλου

� Το δίληµµα του φυλακισµένου

� Σηµείο ισορροπίας Nash


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

� Η θεωρία παιγνίων (game theory) µας βοηθάει στην

κατανόηση καταστάσεων στις οποίες αλληλεπιδρούν

decision-makers

� Παίγνιο: Ένα σύνολο παικτών που ανταγωνίζονται µε

βάση ένα προκαθορισµένο σύνολο κανόνων


βάση ένα προκαθορισµένο σύνολο κανόνων

� Οι παίκτες πρέπει να πάρουν αποφάσεις σε συνθήκες

συναγωνισµού/ανταγωνισµού λαµβάνοντας υπόψη τις

πιθανές κινήσεις των αντιπάλων

Εφαρµογές

� Η θεωρία παιγνίων μπορεί να εφαρμοστεί σε

πολλές καταστάσεις:

� Εταιρείες που ανταγωνίζονται

� Πολιτικοί που διεκδικούν ψήφους

� Ένορκοι που αποφασίζουν για μια ετυμηγορία


� Ένορκοι που αποφασίζουν για μια ετυμηγορία

� Ζώα που μάχονται για λεία

� Παίκτες που συμμετέχουν σε έναν πλειστηριασμό

� Η εξέλιξη της συμπεριφοράς μεταξύ διδύμων

� ...

Πεδία Εφαρµογής

� Η θεωρία παιγνίων σχετίζεται ιδιαίτερα με

κοινωνικά, πολιτικά και οικονομικά αντικείμενα.

� Τα τελευταία χρόνια στο χώρο της πληροφορικής

ερευνάται η ακόλουθη εφαρμογή της θεωρίας

παιγνίων:


παιγνίων:

Έλλειψη συντονισμού – κεντρικού ελέγχου

Μοντέλα

� Η θεωρία παιγνίων περιλαμβάνει ένα σύνολο μοντέλων

� Το μοντέλο είναι μια αφαίρεση που

χρησιμοποιούμε για να κατανοήσουμε

πραγματικές καταστάσεις


πραγματικές καταστάσεις

� Ένα μοντέλο

� είναι σημαντικό να είναι απλό, να επικεντρώνεται σε

ουσιώδη στοιχεία

� δεν πρέπει να βασίζεται σε υποθέσεις που απέχουν

υπερβολικά πολύ από την πραγματικότητα

Ορθότητα ενός µοντέλου

� Ένα μοντέλο δεν μπορεί να κριθεί με απόλυτα

κριτήρια ως σωστό ή λανθασμένο

� Η χρησιμότητα ενός μοντέλου καθορίζεται από

το σκοπό για τον οποίο χρησιμοποιείται

Παράδειγμα: Βέλτιστη διαδρομή


� Παράδειγμα: Βέλτιστη διαδρομή

� Για την απόσταση μεταξύ Ξάνθης και Καβάλας

μπορούμε να υποθέσουμε ότι η γη είναι επίπεδη

� Για την απόσταση Ξάνθης και Μελβούρνης όμως ίσως

θα πρέπει να λάβουμε υπόψη τη σφαιρικότητα της

γης

∆ιαδικασία Μοντελοποίησης

� Τα βασικά βήματα:

� Μια αρχική ιδέα που σχετίζεται με την αλληλεπίδραση

ιθυνόντων

� Διατύπωση της ιδέας με τη μορφή ενός μοντέλου,

συμπεριλαμβάνοντας στο μοντέλο χαρακτηριστικά που

φαίνονται σχετικά


φαίνονται σχετικά

Το βήμα αυτό είναι και λιγάκι τέχνη:

� Επιθυμούμε αρκετά γνωρίσματα ώστε το μοντέλο να έχει

ουσιαστική σημασία

� Επιθυμούμε μια όσο γίνεται απλή δομή

� Ανάλυση του μοντέλου. Κατά την ανάλυση μπορεί να

προκύψει πρέπει να γίνουν προσαρμογές στο μοντέλο

Ορθολογική Επιλογή

� Η θεωρία ορθολογικής επιλογής (rational choice)

ουσιαστικά λέει ότι ένας ιθύνοντας (decision-

maker) επιλέγει τον καλύτερη - σύµφωνα µε τις

προτιµήσεις του – ενέργεια που έχει στη διάθεσή

του.


του.

� Ορθολογική επιλογή σε αυτή την περίπτωση

σηµαίνει ότι ο παίκτης απλά προσπαθεί να

βελτιστοποιήσει την επιλογή του µε βάση µόνο τις

προτιµήσεις του

Παίγνια σε στρατηγική µορφή

� Ένα παίγνιο σε στρατηγική µορφή αποτελείται από

� Ένα σύνολο παικτών

� Για κάθε παίκτη, ένα σύνολο κινήσεων

� Για κάθε παίκτη, ένα σύνολο προτιµήσεων για κάθε

πιθανό προφίλ στρατηγικών


πιθανό προφίλ στρατηγικών

� Ας ξεκινήσουµε µε ένα από τα πιο διάσηµα

παραδείγµατα, ένα παίγνιο σε στρατηγική µορφή:

Το δίληµµα του φυλακισµένου


(The prisoner’s dilemma)



� Δύο κρατούμενοι κατηγορούνται για κάποια

εγκλήματα

� Οι δύο κατηγορούμενοι είναι συνένοχοι

ΟΜΩΣ, οι δικαστικές αρχές έχουν ελλιπή � ΟΜΩΣ, οι δικαστικές αρχές έχουν ελλιπή

αποδεικτικά στοιχεία

� χωρίς άλλες αποδείξεις κάθε κρατούμενος θα

τιμωρηθεί με 1 χρόνο φυλάκισης

� εάν αποδειχθούν όλες οι κατηγορίες τότε κάθε

κρατούμενος θα φυλακιστεί για 4 χρόνια

Το δίληµµα� Οι δικαστικές αρχές προ-φυλακίζουν χωριστά τους δύο

κρατούμενους, και � καλούν τον καθένα να συνεργαστεί,

� βεβαιώνοντάς τον ότι εάν συνεργαστεί θα τιμωρηθεί με επιείκεια (δηλαδή -1 χρόνο)

� Τώρα οι πιθανές εκβάσεις είναι: � Κανείς δε συνεργάζεται, και τιμωρείται ο καθένας με ένα χρόνο

φυλάκιση

� Και οι δύο συνεργάζονται, και τιμωρούνται και οι δύο με 3 χρόνια

� Ένας συνεργάζεται και ένας δε συνεργάζεται:

� Αυτός που συνεργάζεται παίρνει 0 χρόνια, δηλαδή απαλλάσσεται

� Αυτός που δε συνεργάζεται τιμωρείται με το μέγιστο της ποινής, δηλαδή 4 χρόνια

Οι δυνατές στρατηγικές (Strategies) για κάθε κρατούµενο

�Ο κρατούμενος μπορεί

�είτε να συνεργαστεί με τις αρχές (να

προδώσει δηλαδή) και να καταθέσει προδώσει δηλαδή) και να καταθέσει

εναντίον του συνεργάτη/συνενόχου

του

�να μη συνεργαστεί με τις αρχές

Το δίληµµα του κρατούµενου

� Δύο κρατούμενοι

� Είναι συνένοχοι

� Οι δικαστικές αρχές

έχουν ελλιπή

αποδεικτικά

στοιχεία

Να µιλήσω ;

Να µη µιλήσω ;

Προλαβαίνω να διαβάσω

θεωρία παιγνίων ;

στοιχεία Θα µιλήσεις !!

Το δίληµµα ως παίγνιο

� Πολυπλοκότητα: Οι πιθανές στρατηγικές είναι 2 για

κάθε παίκτη και επομένως η υπολογιστική

πολυπλοκότητα του προβλήματος είναι τετριμμένη:

4 συνολικά σενάρια4 συνολικά σενάρια

� Πρόβλημα: Το πρόβλημα είναι πως να επιλέξει την

καλύτερη δυνατή στρατηγική;

� Συνεργασία; Είναι σαφές ότι μία ικανοποιητική λύση

και για τους δύο κρατούμενους είναι το (1,1), δηλαδή

να μη συνεργαστεί κανείς

� ΌΜΩΣ, κάθε παίκτης αποφασίζει μόνος του !

Το δίληµµα του φυλακισµένου ως

παίγνιο σε στρατηγική µορφή

B B

Συνεργάζεται µε

τις αρχές

(Προδίδει)

∆εν

συνεργάζεται

Συνεργάζεται µε τις 3 , 3 0 , 4A

Συνεργάζεται µε τις

αρχές (Προδίδει) 3 , 3 0 , 4

A ∆εν συνεργάζεται 4 , 0 1 , 1

Τα έτη φυλάκισης για κάθε παίκτη για κάθε πιθανή

εκδοχή του παιγνίου.

Συνάρτηση Απόδοσης για το δίληµµα

του φυλακισµένου

� Για τον κρατούµενο-παίκτη Α:

� 1η Περίπτωση: Έστω ότι ο Β δε συνεργάζεται µε τις αρχές

� Εάν δε συνεργαστώ και εγώ , παίρνω 1 χρόνο

� Εάν εγώ συνεργαστώ, παίρνω 0 (0 < 1) χρόνια

� 2η Περίπτωση: Έστω ότι ο Β συνεργάζεται µε τις αρχές

� Εάν δε συνεργαστώ, παίρνω 4 χρόνια



� Εάν εγώ συνεργαστώ και εγώ, παίρνω 3 (3 < 4) χρόνια

� Στο παραπάνω παράδειγµα η συνάρτηση απόδοσης (utility

function) δίνει το «κόστος» που θα πρέπει να πληρώσει ο

παίκτης και εποµένως ο «ορθολογικός στόχος» του παίκτη

είναι να την ελαχιστοποιήσει

Ορθολογική Συµπεριφορά (Rational Behaviour)

� Θεωρούµε ότι οι παίκτες έχουν «ορθολογική συµπεριφορά»:

Κάθε παίκτης επιλέγει µία βέλτιστη κίνησή του µε βάση τις προτιµήσεις

(preferences) που έχει.

� Ανεξάρτητα από τη φύση των προτιµήσεων του παίκτη σε ένα παίγνιο,

συµπεριφέρεται ορθολογικά µε την έννοια ότι προσπαθεί να ικανοποιήσει


συµπεριφέρεται ορθολογικά µε την έννοια ότι προσπαθεί να ικανοποιήσει

τις προτιµήσεις αυτές.

� Συνήθως οι προτιµήσεις των παικτών δίνονται µε τη µορφή συναρτήσεων

απόδοσης (utility functions ή payoff functions) ή ενός πίνακα (matrix

game)

Το δίληµµα του κρατούµενου Α� 1η Περίπτωση: Έστω ότι ο Β δε συνεργάζεται με τις αρχές

� Εάν δε συνεργαστώ και εγώ , παίρνω 1 χρόνο

� Εάν εγώ συνεργαστώ, παίρνω 0 (0 < 1) χρόνια

� 2η Περίπτωση: Έστω ότι ο Β συνεργάζεται με τις αρχές


� Εάν εγώ συνεργαστώ και εγώ, παίρνω 3 (3 < 4) χρόνια� Εάν εγώ συνεργαστώ και εγώ, παίρνω 3 (3 < 4) χρόνια

∆ηλαδή, µε συµφέρει ούτωςή άλλως να συνεργαστώ !!;;

?

Κυριαρχούµενη στρατηγική

� Κυριαρχούµενη στρατηγική

� Αυστηρά Κυριαρχούµενη στρατηγική

� ∆ίδαγµα 1: ∆εν έχει νόηµα ο παίκτης να επιλέξει µια

αυστηρά κυριαρχούµενη στρατηγική


αυστηρά κυριαρχούµενη στρατηγική

Λύση του παιγνίου


Λύση του παιγνίου� Ο φυλακισμένος, σκεπτόμενος ορθολογικά, θα πρέπει

να συνεργαστεί με τις αρχές και να προδώσει τον άλλο

φυλακισμένο!

� Ο άλλος φυλακισμένος θα σκεφτεί με τον ίδιο ακριβώς

ορθολογικό τρόπο και θα προδώσει και αυτός.


� Αποτέλεσμα: Οι δύο φυλακισμένοι θα πάρουν από 3

χρόνια φυλακής ο καθένας! Μια πολύ κακή λύση (από

την μεριά των φυλακισμένων).

� Δίδαγμα 2: Οι ορθολογικές επιλογές μπορεί να

οδηγήσουν σε κακές εκβάσεις.

Να προδίδουµε πάντοτε;

� Το γεγονός ότι σύμφωνα με τη λύση πρέπει

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

επιστημονική κοινότητα

� Ίσως, εάν υπάρχει η έννοια της μνήμης, της � Ίσως, εάν υπάρχει η έννοια της μνήμης, της

συνέχειας κτλ. να μπορεί να φερθεί πιο

αλτρουϊστικά

� Τι θα συμβεί λοιπόν εάν παίξουμε το παιχνίδι

αρκετές στη σειρά;

Τουρνουά του Axelrod

� Στο τέλος της δεκαετίας του 1970, ο Axelrod(Πολιτικές Επιστήμες στο Πανεπιστήμιο του Michigan), κάλεσε

� οικονομολόγους, ψυχολόγους, μαθηματικούς και � οικονομολόγους, ψυχολόγους, μαθηματικούς και

κοινωνιολόγους

να υποβάλλουν λύση (με τη μορφή κώδικα)

για το Δίλημμα του Φυλακισμένου

Τουρνουά του Axelrod

� 14 συμμετοχές

� Έπαιξαν όλοι εναντίον όλων

� Νικητής: tit-for-tat (Anatol Rapoport) • Στο πρώτο γύρω: δεν µιλάω

• Σε κάθε επόµενο γύρω: ανταποδίδω

• Ανακοινώνονται τα αποτελέσµατα και

προκηρύσσεται νέος διαγωνισµός:

• 62 συµµετοχές

• Νικητής: Και πάλι το tit-for-tat που υπέβαλλε

πάλι ο Rapoport

Τουρνουά του Axelrod (2)� Ο Axelrod χρησιμοποίησε τις στρατηγικές του δεύτερου

διαγωνισμού για ένα evolutionary τουρνουά

� Στρατηγικές που αποδίδουν καλά αναπαράγονται ταχύτερα

� Πιθανόν έτσι στρατηγικές που αρχικά τα καταφέρνουν

καλά, να μην αποδίδουν στη συνέχεια διότι θα έχουν

εξαλειφθεί οι στρατηγικές έναντι των οποίων υπερίσχυανεξαλειφθεί οι στρατηγικές έναντι των οποίων υπερίσχυαν

� Μετά από ένα μεγάλο πλήθος “γενεών”, νικητής

(πολυπληθέστερη ομάδα) ήταν η στρατηγική:

Και πάλι το tit-for-tat !!

Ισορροπία Nash

(Nash Equilibrium)


Ενέργειες των Παικτών

� Ποιες ενέργειες/κινήσεις επιλέγουν οι παίκτες σε

ένα παίγνιο;

� Υποθέσαµε ότι οι παίκτες είναι ορθολογικοί και επιλέγει ο

καθένας το καλύτερο σύµφωνα µε τις προτιµήσεις του


καθένας το καλύτερο σύµφωνα µε τις προτιµήσεις του

� Όµως η έκβαση του παιγνίου για κάθε παίκτη εξαρτάται

από τις επιλογές όλων των παικτών

� Εποµένως ο ορθολογικός παίκτης πρέπει να λάβει υπόψη

του και τι θα επιλέξουν οι υπόλοιποι παίκτες

«Λύση» ενός παιγνίου

� Ποιες κινήσεις επιλέγουν οι παίκτες ενός παιγνίου;

� Μπορούµε να υποθέσουµε ότι οι παίκτες, ως

ορθολογικές οντότητες, επιλέγουν την καλύτερη

δυνατή κίνηση ο καθένας

� Σε ένα παίγνιο όµως, η καλύτερη κίνηση για


� Σε ένα παίγνιο όµως, η καλύτερη κίνηση για

οποιοδήποτε παίκτη εξαρτάται από τις κινήσεις των

υπολοίπων παικτών

�Εποµένως ο παίκτης θα πρέπει να έχει µία εκτίµηση

(belief) για τις κινήσεις των άλλων παικτών

Ισορροπία Nash

(Nash Equilibrium)

� Μια ισορροπία Nash είναι µια κατάσταση του παιγνίου

στην οποία

� κανένας παίκτης δεν µπορεί να βελτιώσει τη θέση του

επιλέγοντας µια άλλη κίνηση, µε την προϋπόθεση ότι όλοι


επιλέγοντας µια άλλη κίνηση, µε την προϋπόθεση ότι όλοι

οι υπόλοιποι παίκτες δεν θα αλλάξουν την κίνησή τους.

� Η ισορροπία Nash και οι παραλλαγές της είναι η

δηµοφιλέστερη έννοια λύσης παιγνίων.

Συµβολισµοί - Ορολογία� στρατηγική

� αγνή στρατηγική (pure strategy): Ορίζει ντετερµινιστικά τη συµπεριφορά του παίκτη για κάθε ενέργεια που θα πρέπει να κάνειΠχ: Το δίληµµα του κρατούµενου

� µικτή στρατηγική (mixed strategy): Μια κατανοµή πιθανότητας πάνω στις κινήσεις του παίκτη. Πχ. Πέτρα-ψαλίδι-χαρτί


Πχ. Πέτρα-ψαλίδι-χαρτί

� προφίλ ή περίγραµµα στρατηγικών α (profile): ένα διάνυσµα που καθορίζει µια στρατηγική για κάθε παίκτη

� προφίλ ή περίγραµµα µικτών στρατηγικών: ένα διάνυσµα που καθορίζει µια µικτή στρατηγική για κάθε παίκτη

� α-i :δεδοµένου ενός προφίλ α συµβολίζουµε α-i το προφίλ µε τις κινήσεις όλων των παικτών εκτός του παίκτη i όπως στο προφίλ a

Ισορροπία Nash (Nash Equilibrium)

� Χρησιµοποιώντας την έννοια του προφίλ ενεργειών ο

ορισµός της ισορροπίας Nash είναι:

Μια ισορροπία Nash είναι ένα προφίλ ενεργειών α* µε

την ιδιότητα ότι κανένας παίκτης δεν βελτιώνει τη θέση


την ιδιότητα ότι κανένας παίκτης δεν βελτιώνει τη θέση

του επιλέγοντας µια ενέργεια διαφορετική από αυτή στο

προφίλ α*, µε δεδοµένο ότι οι υπόλοιποι παίκτες δεν θα

αλλάξουν την κίνησή τους.

Εύρεση ισορροπίας Nash

� Εάν το πλήθος των παικτών και των κινήσεων είναι

πολύ περιορισµένο τότε είναι δυνατό να εξετάσουµε

όλα τα πιθανά προφίλ (brute force search) από την

οπτική γωνία κάθε παίκτη για να βρούµε τις pure

ισορροπίες Nash.


ισορροπίες Nash.

� Πολλές φορές είναι πιο αποτελεσµατικό να

χρησιµοποιήσουµε τις συναρτήσεις βέλτιστης

αντίδρασης.

Πολυπλοκότητα εύρεσης NE� Πρόσφατα αποτελέσµατα έδειξαν ότι είναι µάλλον µη

αναµενόµενο να υπάρχει αποτελεσµατικός (πολυωνυµικός)

αλγόριθµος για την εύρεση ισορροπίας Nash

� C. Daskalakis, P. W. Goldberg and C. H. Papadimitriou.


� C. Daskalakis, P. W. Goldberg and C. H. Papadimitriou.

The Complexity of Computing a Nash Equilibrium,"

Proceedings of STOC, 2006.

� X. Chen and X. Deng. Settling the Complexity of 2-Player

Nash-Equilibrium," Proceedings of FOCS, 2006.

Συνάρτηση Βέλτιστης Απόκρισης

(Best Response Function)


Συναρτήσεις βέλτιστης απόκρισης

� ∆εδοµένου ενός προφίλ α-i η συνάρτηση βέλτιστης

απόκρισης του παίκτη i δίνει το σύνολο των κινήσεων

του παίκτη που επιτυγχάνουν το καλύτερο δυνατό

αποτέλεσµα για αυτόν


Ισορροπία Nash και βέλτιστη απόκριση

� Χρησιµοποιώντας την έννοια του προφίλ ενεργειών µπορούµε να επαναδιατυπώσουµε τον ορισµό της ισορροπίας Nash:

Ένα προφίλ κινήσεων α* είναι µια ισορροπία Nash εάν η ενέργεια κάθε παίκτη i στο προφίλ είναι η βέλτιστη


η ενέργεια κάθε παίκτη i στο προφίλ είναι η βέλτιστη απόκριση στο προφίλ α-i των υπολοίπων παικτών

� Heuristic: Μπορούµε να χρησιµοποιήσουµε τις συναρτήσεις βέλτιστης απόκρισης για να αναζητήσουµε ισορροπίες Nash (ο αλγόριθµος αυτός δεν είναι απαραίτητα πολυωνυµικού χρόνου)

Παράδειγµα 39.1: Μια σχέση

συνεργασίας

� Osborne, Ενότητα 2.8, Παράδειγµα 39.1

� ∆ύο άτοµα έχουν µια σχέση συνεργασίας, πχ. ένα

κοινό project

� Συγκεκριµένα κάθε παίκτης προσφέρει έργο αi

� Η απόδοση του παίκτη i είναι α (c+α -α ), όπου c > 0


� Η απόδοση του παίκτη i είναι αi(c+αj-αi), όπου c > 0

είναι µια σταθερά

παράδειγµα 39.1

� κάθε παίκτης έχει ένα άπειρο πλήθος κινήσεων.

Επομένως δεν μπορούμε να χρησιμοποιήσουμε την

αναπαράσταση με πίνακα

� θα χρησιμοποιήσουμε τις συναρτήσεις βέλτιστης

απόκρισης


απόκρισης

� Δεδομένου του αj η βέλτιστη απόκριση του αi ποια

είναι;

παράδειγµα 39.1: οι συναρτήσεις

βέλτιστης απόκρισης


παράδειγµα: συνεισφορά σε δηµόσιο

αγαθό (public good)

� δύο παίκτες i = 1, 2 αποφασίζουν εάν και πόσο θα συνεισφέρουν σε ένα δηµόσιο αγαθό

� παίκτης i:

� έχει περιουσία (wealth) wi

� συνεισφέρει ci: 0≤ ci ≤ wi


i i i

� συνάρτηση απόδοσης: vi(c1 + c2) + wi – ci

και δεδοµένου ότι wi είναι σταθερό, µπορούµε να θεωρήσουµε ως συνάρτηση απόδοσης: ui(c1, c2) = vi(c1 + c2) – ci

(παράδειγµα ενότητας 2.8.4, βιβλίο Osborne)

συνάρτηση βέλτιστης απόκρισης


συναρτήσεις βέλτιστης απόκρισης


Κυριαρχούµενες Ενέργειες� Αυστηρή Κυριαρχία (Strict Domination)

Σε στρατηγικό παίγνιο µια στρατηγική α2i κυριαρχεί επί της στρατηγικής α1i, εάν

για κάθε προφίλ α-i, ui(α2i,α-i) > ui(α1i,α

-i)

� Ασθενής Κυριαρχία (Weak Domination)


� Ασθενής Κυριαρχία (Weak Domination)

Σε στρατηγικό παίγνιο µια στρατηγική α2i κυριαρχεί επί της στρατηγικής α1i, εάν

για κάθε προφίλ α-i, ui(α2i,α-i) ≥ ui(α1i,α

-i)

και υπάρχει ένα τουλάχιστον προφίλ α-i για το οποίο:

ui(α2i,α-i) > ui(α1i,α

-i)

Συµµετρικό Παίγνιο (Symmetric Game)

� Συµµετρικό Παίγνιο µεταξύ δύο παικτών: Οι

παίκτες έχουν τις ίδιες κινήσεις και για τις αποδόσεις

των παικτών ισχύει: u1(a1,a2) = u2(a2,a1) για κάθε

πιθανό προφίλ α=(a1,a2)

� Συµµετρική Ισορροπία Nash: σε στρατηγικό παίγνιο


� Συµµετρική Ισορροπία Nash: σε στρατηγικό παίγνιο

όλοι οι παίκτες έχουν τις ίδιες κινήσεις, ένα προφίλ α*

είναι µία συµµετρική ισορροπία Nash εάν είναι σηµείο

ισορροπίας Nash και επιπλέον το αi* να είναι ίδιο για

κάθε παίκτη i (όλοι οι παίκτες επιλέγουν την ίδια

κίνηση).

Τι είναι λοιπόν η θεωρία παιγνίων


Τι είναι λοιπόν η θεωρία παιγνίων� Η θεωρία παιγνίων

� μελετά την αλληλεπίδραση (ανταγωνισμό, συνεργασία κτλ.) μεταξύ ανεξάρτητων ορθολογικών (rational) οντοτήτων

� χρησιμοποιεί μαθηματικά μοντέλα για την μοντελοποίηση των προβλημάτων

� υπάρχει και το εμπειρικό/πρακτικό μέρος: experimental game theory


theory

� βρίσκει εφαρμογή εδώ και αρκετά χρόνια στην ΟικονομικήΘεωρία

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

� αφορμή: η ανάπτυξη δικτυωμένων/κατανεμημένων συστημάτων με κύριο παράδειγμα το διαδίκτυο

Εφαρµογές της Θεωρίας Παιγνίων

� εταιρείες που ανταγωνίζονται

� υποψήφιοι πολιτικοί που ανταγωνίζονται για

ψήφους

υποψήφιοι αγοραστές ανταγωνίζονται σε έναν


� υποψήφιοι αγοραστές ανταγωνίζονται σε έναν

πλειστηριασμό

� Βιολογία/ διαδικασίες φυσικής επιλογής

� Εφαρμογές στην Επιστήμη Υπολογιστών

Θεωρία Παιγνίων και Επιστήµη Υπολογιστών

� Αλγόριθμοι για Επίλυση Παιγνίων� Υπάρχει λύση για ένα παίγνιο;

� Μπορούμε να την υπολογίσουμε; Τι Πολυπλοκότητα έχει;

� Είναι πολλές οι λύσεις;

� Μπορούμε να βρούμε την καλύτερη ή μια αρκετά καλή;

� Μοντελοποίηση προβλημάτων της Επιστήμης Υπολογιστών


� Μοντελοποίηση προβλημάτων της Επιστήμης Υπολογιστών

ως παίγνια:� Παγκόσμιος Ιστός

� Διαδίκτυο και γενικότερα κάθε Δίκτυο

� Agents, Κατανεμημένα συστήματα

� Κρυπτογραφία

� Επίσης ασφάλεια, εξοικονόμηση ενέργειας, …

Πηγές/Αναφορές

� Κεφάλαια 1 και 2: An introduction to Game Theory,

M. Osborne, Oxford University Press, 2004

� Σηµειώσεις του µαθήµατος «Οικονοµική Θεωρία και

Αλγόριθµοι» του τµ. Μηχ. ΗΥ και Πληροφορικής,

Παν/µιο Πατρών


Παν/µιο Πατρών

http://www.ceid.upatras.gr/courses/game_theory/

� Game Theory, Video Course, Benjamin Polak, Yale

http://academicearth.org/courses/game-theory

Documents

Βασικές Έννοιες Θεωρίας Παιγνίων › courses › old › 2011-12... · Εάν δε συνεργαστώ , παίρνω 4 χρόνια Βασικές Έννοιες