Παίγνια δύο παικτών, υπολογιστικά θέματα και αλγόριθμοι

• Main Author: Δελιγκάς, Αργύρης
• Other Authors: Καββαδίας, Δημήτριος
• Format: Thesis
• Language: Greek
• Published: 2012
• Subjects: Αλγοριθμική θεωρία παιγνίων; Παίγνια διπίνακα; Game theory; Bimatrix games; Lemke Howson; PPAD; 519.3

Σε αυτή τη διπλωματική εργασία μελετάμε το πρόβλημα εύρεσης ενός Nash σημείου ισορροπίας για παίγνια δύο παικτών. Παρουσιάζεται ο αλγόριθμος Lemke - Howson, η πολυπλοκότητα του αλγορίθμου καθώς και η κλάση πολυπλοκότητας PPAD, όπου και αποδεικνύεται ότι το πρόβλημα εύρεσης ενός Nash σημείου ισορροπ...