Ο Κωνσταντίνος Δασκαλάκης (γεν. 29 Απριλίου 1981) είναι Έλληνας επιστήμονας θεωρίας υπολογισμού, καθηγητής του Τμήματος Ηλεκτρολόγων Μηχανικών και Επιστήμης Υπολογιστών του ΜΙΤ και μέλος του Εργαστηρίου Πληροφορικής και Τεχνητής Νοημοσύνης του MIT. Το 2018 διακρίθηκε με το περίβλεπτο Βραβείο Νεβάνλινα και το Βραβείο Γκρέις Μάρεϊ Χόπερ.
Μετά το διδακτορικό του πέρασε ένα χρόνο ως μεταδιδακτορικός ερευνητής στην ομάδα της Jennifer Chayes στο τμήμα Microsoft Research της Νέας Αγγλίας.
Ο Δασκαλάκης ασχολείται με τη θεωρία του υπολογισμού και τη διασύνδεσή της με τη θεωρία παιγνίων, τα οικονομικά, τη θεωρία πιθανοτήτων, τη στατιστική και τη μηχανική μάθηση.
Έχει επιλύσει επί μακρόν ανοικτά προβλήματα σχετικά με την υπολογιστική πολυπλοκότητα της ισορροπίας Nash, τη μαθηματική δομή και την υπολογιστική πολυπλοκότητα των δημοπρασιών πολλαπλών στοιχείων και τη συμπεριφορά των μεθόδων μηχανικής μάθησης, όπως ο αλγόριθμος μεγιστοποίησης προσδοκιών. Έχει επιτύχει υπολογιστικά και στατιστικά αποτελεσματικές μεθόδους για τον στατιστικό έλεγχο υποθέσεων και τη μάθηση σε περιβάλλοντα υψηλών διαστάσεων, καθώς και αποτελέσματα που χαρακτηρίζουν τη δομή και τις ιδιότητες συγκέντρωσης των κατανομών μεγάλων διαστάσεων.
Ο Δασκαλάκης συνέγραψε την εργασία The Complexity of Computing a Nash Equilibrium με τον διδακτορικό του σύμβουλο Χρήστο Παπαδημητρίου και τον Paul W. Goldberg, για την οποία έλαβαν το 2008 το βραβείο Kalai Game Theory and Computer Science Prize από την Game Theory Society για την “καλύτερη εργασία στη διεπαφή της θεωρίας παιγνίων και της επιστήμης των υπολογιστών”, ιδίως “για τις βασικές εννοιολογικές και τεχνικές συνεισφορές της”- και το βραβείο εξαιρετικής εργασίας από την Society for Industrial and Applied Mathematics (SIAM).
Διορίστηκε μόνιμος καθηγητής στο MIT τον Μάιο του 2015.
https://el.wikipedia.org/wiki/Κωνσταντίνος_Δασκαλάκης
Πόσος χρόνος χρειάζεται για να λυθεί ένα πρόβλημα σε έναν υπολογιστή; Αυτή η φαινομενικά αθώα ερώτηση, μη απαντήσιμη εν γένει, βρίσκεται στο επίκεντρο της θεωρίας της υπολογιστικής πολυπλοκότητας. Με βαθιές ρίζες στα μαθηματικά και τη λογική, ο τομέας αυτός της έρευνας προσπαθεί να κατανοήσει το όριο μεταξύ του ποια προβλήματα επιλύονται αποτελεσματικά από υπολογιστή και ποια όχι.
Η θεωρία υπολογιστικής πολυπλοκότητας είναι ένας από τους πιο δυναμικούς και ευρηματικούς κλάδους της επιστήμης των υπολογιστών, και ο Κωνσταντίνος Δασκαλάκης ξεχωρίζει ως ένας από τους πιο λαμπρούς νέους φωστήρες της. Το έργο του έχει μετασχηματίσει την κατανόηση της υπολογιστικής πολυπλοκότητας πολλών θεμελιωδών προβλημάτων στη θεωρία παιγνίων, τις αγορές, τις δημοπρασίες και άλλες οικονομικές δομές. Η πολύπλευρη περιέργεια, η τεχνική εφευρετικότητα και η βαθιά θεωρητική διορατικότητα επέτρεψαν στον Δασκαλάκη να φέρει θεμελιώδεις νέες προοπτικές σε αυτά τα προβλήματα.
Η θεωρία παιγνίων έχει ευρεία εφαρμογή, όχι μόνο στα οικονομικά, αλλά ακόμη και σε τομείς όπως οι διεθνείς σχέσεις και η βιολογία. Είναι σαφές ότι θα ήταν χρήσιμο να υπάρχει ένας τρόπος αποτελεσματικού υπολογισμού των ισορροπιών Nash, προκειμένου να προβλεφθεί τι θα μπορούσαν να κάνουν οι στρατηγικοί παράγοντες. Έτσι, αμέσως αφότου ο Nash απέδειξε το θεώρημά του, ξεκίνησε μια μακρά σειρά ερευνών, στις οποίες οι ερευνητές ανέπτυξαν αλγόριθμους για τον υπολογισμό των ισορροπιών Nash. Μέχρι τις αρχές της δεκαετίας του 2000, ωστόσο, κανένας από αυτούς τους αλγορίθμους δεν ήταν γνωστό ότι ήταν αποτελεσματικός, ενώ ορισμένοι είχαν αποδειχθεί αναποτελεσματικοί. Δημιουργήθηκαν υποψίες ότι το πρόβλημα του υπολογισμού μιας ισορροπίας Nash μπορεί να είναι δυσεπίλυτο. Και αν είναι δυσεπίλυτο, δεν θα υπήρχε λόγος να πιστεύεται ότι οι ισορροπίες θα ανακαλύπτονταν πάντα από στρατηγικούς παράγοντες, δηλαδή από ανθρώπους με περιορισμένο μυαλό. Ένα τέτοιο συμπέρασμα θα μείωνε τις προσδοκίες για το πόσο καλά η ισορροπία Nash μπορεί να προβλέψει την ανθρώπινη συμπεριφορά.
Τα ερωτήματα της υπολογιστικής εφικτότητας συχνά εξετάζονται στο πλαίσιο του γνωστού παραδείγματος “Πρόβλημα P έναντι NP”, το οποίο προέκυψε τη δεκαετία του 1970 και σύντομα έγινε κεντρικό θέμα της θεωρίας της υπολογιστικής πολυπλοκότητας. Σε γενικές γραμμές, το P συμβολίζει την κατηγορία προβλημάτων που είναι εύκολο να επιλυθούν με υπολογιστή, δηλαδή υπάρχει ένας αποτελεσματικός αλγόριθμος για την επίλυσή τους. Αντίθετα, η κατηγορία NP περιέχει προβλήματα που πιστεύεται ότι είναι δύσκολο να επιλυθούν, πράγμα που σημαίνει ότι, αν δοθεί μια προτεινόμενη λύση, υπάρχει ένας αποτελεσματικός τρόπος για τον έλεγχό της, αλλά δεν είναι γνωστός κάποιος αποτελεσματικός αλγόριθμος για την παραγωγή λύσεων.
Τα προβλήματα στα NP αντλούν τη δυσκολία τους από την πιθανότητα ότι μπορεί να μην υπάρχει λύση. Αντίθετα, για το πρόβλημα του υπολογισμού μιας ισορροπίας Nash, η απόδειξη του Nash εγγυάται ότι υπάρχει λύση. Για το λόγο αυτό, το πρόβλημα ισορροπίας Nash δεν ταιριάζει στο παράδειγμα “P έναντι NP”. Το 1994, ο Χρήστος Παπαδημητρίου όρισε μια νέα κατηγορία πολυπλοκότητας που ονομάζεται PPAD, κατάλληλη για προβλήματα όπως το πρόβλημα ισορροπίας Nash, για τα οποία υπάρχουν πάντα λύσεις και για τα οποία δεν είναι γνωστός κάποιος αποτελεσματικός αλγόριθμος για τον υπολογισμό λύσεων. Το PPAD αντιστοιχεί σε “πολυωνυμικό επιχείρημα ισοτιμίας για κατευθυνόμενους γράφους” και αναφέρεται σε ένα συγκεκριμένο τυπικό επιχείρημα που χρησιμοποιείται για την απόδειξη αποτελεσμάτων ύπαρξης στη συνδυαστική. Το επιχείρημα είναι μια κατευθυνόμενη εκδοχή ενός αποτελέσματος γνωστού ως λήμμα χειραψίας. Το PPAD περιέχει όλα τα υπολογιστικά προβλήματα των οποίων η λύση μπορεί να αποδειχθεί ότι υπάρχει με τη χρήση αυτού του λήμματος.
Ένα από τα πιο σημαντικά προβλήματα στο PPAD είναι μια υπολογιστική εκδοχή ενός αποτελέσματος από τα καθαρά (ή θεωρητικά) μαθηματικά που ονομάζεται θεώρημα σταθερού σημείου του Brouwer. Ορίζει ότι μια συνεχής απεικόνιση από μια σφαίρα στον εαυτό της δεν μπορεί να μετατοπίσει όλα τα σημεία- τουλάχιστον ένα σημείο παραµένει σταθερό βάσει της απεικόνισης. Αυτό το θεμελιώδες αποτέλεσμα, που αποδείχθηκε από τον L.E.J. Brouwer το 1911, αποτελεί τη βάση για αμέτρητες αποδείξεις στα μαθηματικά, συμπεριλαμβανομένης της απόδειξης του Nash για την ύπαρξη ισορροπιών. Η απόδειξη του Brouwer είναι μη εποικοδομητική, δηλαδή εγγυάται την ύπαρξη σταθερών σημείων αλλά δεν δείχνει πώς μπορούν να βρεθούν. Η υπολογιστική εκδοχή του θεωρήματος σταθερών σημείων του Brouwer ζητά έναν αλγόριθμο για την εύρεση σταθερών σημείων. Στην δημοσίευσή του το 1994, ο Παπαδημητρίου κατέδειξε ότι αυτή η υπολογιστική εκδοχή είναι “PPAD-complete”, που σημαίνει ότι είναι στο PPAD και οποιοδήποτε πρόβλημα στο PPAD μπορεί να αναχθεί σε αυτό, ή, με άλλα λόγια, είναι ακριβώς τόσο δύσκολο όσο το PPAD.
Ο Δασκαλάκης έγινε διδακτορικός φοιτητής του Παπαδημητρίου και άρχισε να εργάζεται πάνω στο πρόβλημα της ισορροπίας Nash. Έκανε μεγάλη πρόοδο όταν, μαζί με τον Παπαδημητρίου και τον Paul Goldberg, απέδειξε ότι το πρόβλημα ισορροπίας Nash είναι υπολογιστικά ισοδύναμο με το πρόβλημα εύρεσης σταθερών σημείων Brouwer και επομένως είναι επίσης PPAD-complete. Δείχνοντας ότι το πρόβλημα ισορροπίας Nash είναι δυσεπίλυτο, η εργασία των Δασκαλάκη κ.ά. σπάει την καθολικότητα των ισορροπιών Nash: Δεν γίνεται να περιμένει κάποιος/-α ότι οι ισορροπίες Nash θα προκύπτουν πάντα από αλληλεπιδράσεις μεταξύ στρατηγικών παραγόντων, επειδή αυτοί οι παράγοντες δεν μπορούν να εκτελέσουν δυσεπίλυτους υπολογισμούς. Με αυτή την πρακτική έννοια, οι ισορροπίες Nash δεν είναι πάντα υπαρκτές.
Η εργασία καταδεικνύει επίσης γιατί ένας αποτελεσματικός αλγόριθμος για το πρόβλημα της ισορροπίας Nash ήταν τόσο δύσκολο να βρεθεί. Αν κοιτάξει κανείς τα σπλάχνα των αλγορίθμων που είχαν αναπτύξει οι άνθρωποι για τον υπολογισμό των ισορροπιών Nash, θα δει τη χαρακτηριστική δομή της κατηγορίας PPAD να κρύβεται στο παρασκήνιο. Η εργασία των Δασκαλάκη κ.ά. έδειξε ότι αυτή η δομή είναι αναπόφευκτη.
https://www.mathunion.org/fileadmin/IMU/Prizes/Nevanlinna/daskalakis-final.pdf
Επιστήμονας Θεωρίας Υπολογισμού, Σύγχρονα Μαθηματικά
