Πέμπτη, 9 Ιανουαρίου 2014

Κωνσταντίνος Δασκαλάκης: από την πληροφορία στην πληροφορική, Konstantinos Daskalakis: Searching for Equilibrium

EECS professor Constantinos Daskalakis. In 2008, he won the Association for Computing Machinery’s dissertation prize by showing how techniques drawn from theoretical computer science could shed new light on one of the central concepts in game theory: equilibrium. Equilibrium is the idea that won Nash his Nobel, and the Nash equilibrium is the type of equilibrium most commonly studied. It describes a balance of strategies that no player of a game has a motive to change unilaterally. The most basic example of a Nash equilibrium involves the so-called penalty-kick game. In soccer, a penalty kick gives an offensive player a free shot on goal with only the goalie defending. The ball travels so quickly that the goalie has to guess which way to dive before it’s struck. In the game-theoretical version, if both players pick the same half of the goal, the goalie wins; if they pick different halves, the shooter wins.

Από την κρυπτογραφία έως τη θεωρία παιγνίων, και από τη θεωρία αριθμών στην υπολογιστική φυσική, η χθεσινή διάλεξη «Από την πληροφορία στην πληροφορική», του αναπληρωτή καθηγητή στο τμήμα Ηλεκτρολόγων Μηχανικών και Επιστήμης Υπολογιστών του ΜΙΤ Κωνσταντίνου Δασκαλάκη, στo πλαίσιo των hub science events, περιλάμβανε λίγα μόνο θέματα από τα πολλά και ενδιαφέροντα που ερευνά μαζί με τους συνεργάτες του.

Ο κ. Δασκαλάκης, 32 ετών σήμερα, αποφοίτησε από τη Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών του ΕΜΠ με το μεγαλύτερο βαθμό που έχει μέχρι σήμερα επιτύχει απόφοιτος της σχολής (9.98), πριν συνεχίσει με διδακτορικές σπουδές στο πανεπιστήμιο Μπέρκλεϋ στην Καλιφόρνια των ΗΠΑ.

Above is a link to a new release highlighting Constantinos Daskalakis and his important work. Together with Paul Goldberg and Christos Papadimitriou, Constantinos received the Game Theory and Computer Science Prize for his paper “The Complexity of Computing a Nash Equilibrium.” The prize is awarded once every four years at the World Congress of the Game Theory Society. A shorter and simpler version of the paper is available here

Η διατριβή του τιμήθηκε με το βραβείο ACM (Association for Computing Machinery) ως η καλύτερη διδακτορική εργασία για το 2008, ενώ μοιράστηκε με τους Πολ Γκόλντμπεργκ και Χρήστο Δασκαλάκη (τον επιβλέποντά του) το βραβείο Θεωρίας Παιγνίων και Θεωρίας Υπολογιστών για την εργασία τους «Η πολυπλοκότητα στον Υπολογισμό Ισορροπιών Νας», η οποία διευθέτησε ένα γρίφο της θεωρίας παιγνίων που κρατούσε από το 1950.

One of the oldest surviving fragments of Euclid's Elements, found at Oxyrhynchus and dated to circa AD 100 (P. Oxy. 29). The diagram accompanies Book II, Proposition 5.

Ξεκινώντας τη διάλεξή του με τον κλάδο της θεωρητικής πληροφορικής και των μαθηματικών, εισήγαγε το κοινό μιας κατάμεστης συνεδριακής αίθουσας στις έννοιες της πληροφορίας και των αλγορίθμων χρησιμοποιώντας παραδείγματα από την καθημερινότητά μας. Ιδιαίτερο ενδιαφέρον είχε η αναφορά στον Ευκλείδη, ο οποίος επινόησε τον 3ο αιώνα π.Χ. ένα αλγόριθμο για την εύρεση του μέγιστου κοινού διαιρέτη δύο αριθμών που σήμερα χρησιμοποιείται ευρέως από προγράμματα κρυπτογραφίας και είναι εκθετικά γρηγορότερος στην εφαρμογή του σε σχέση με άλλους. Κλειδί σύμφωνα με τον κ. Δασκαλάκη για έναν καλό αλγόριθμο είναι η σαφήνεια και η βαθιά κατανόηση του προβλήματος.

Η χρήση της υπολογιστικής θεωρίας έχει πλέον μεταδοθεί σε όλους τους επιστημονικούς κλάδους, με τον ομιλητή να σκιαγραφεί ένα παράδειγμα υπολογιστικής βιολογίας το οποίο ερεύνησε με συναδέλφους του. Στη συγκεκριμένη έρευνα αναλύθηκε το φαινόμενο της φυλογένεσης, της εξέλιξης δηλαδή του γονιδιώματος ενός είδους με το χρόνο. Το ενδιαφέρον στη συγκεκριμένη έρευνα ήταν ο συσχετισμός του φαινομένου αυτού με το φαινομενικά άσχετο φαινόμενο του φερρομαγνητισμού, της εξάρτησης δηλαδή του μαγνητισμού ενός αντικειμένου από τη θερμοκρασία του. Οι ερευνητές βρήκαν στην προκειμένη περίπτωση πως τα μαθηματικά που ορίζουν τις πιθανότητες μετάλλαξης του γονιδιώματος ενός είδους είναι τα ίδια με αυτά που εξαρτούν τη θερμοκρασία των φερρομαγνητικών υλικών με τη μαγνήτισή τους (Daskalakis, Mossel, Roch ’06).

H διάλεξη συνεχίστηκε με εφαρμογές κρυπτογραφίας, έναν τομέα όπου το Διαδίκτυο είχε την τιμητική του. Σύμφωνα με τον καθηγητή η μετάδοση πληροφοριών μέσω Διαδικτύου γίνεται εντέλει και μέσω κάποιου φυσικού μέσου (αέρας, καλώδια κτλ). Οποιοσδήποτε αποκτήσει πρόσβαση στο φυσικό αυτό μέσο έχει τη δυνατότητα να υποκλέψει πληροφορίες, και για αυτή τη δραστηριότητα υπάρχει στην αργκό της ειδικότητας ο ειδικός όρος «σνιφάρισμα». Με αυτό τον τρόπο οι προσωπικές μας πληροφορίες δεν είναι πάντα όσο ασφαλείς νομίζουμε, με τον ομιλητή να αναφέρεται σε τρόπους που μπορούν να μας προστατεύσουν (όπως το κρυπτογραφικό πρωτόκολλο RSA, του οποίου παρουσίασε μία εφαρμογή), ενώ επέμεινε στην ανάγκη εκπαίδευσης των χρηστών γύρω από θέματα του Διαδικτύου.

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

Bust titled 'Solon' (National Museum, Naples). This realistic representation of Solon bears little resemblance to the kind of sculpture that was produced in the archaic age.

Το πρώτο παράδειγμα αφορούσε το θεσμό της Αντίδοσης, που εισήγαγε ο νομοθέτης Σόλωνας στην αρχαία Αθήνα. Ο νόμος όριζε τότε πως οι άρχοντες της πόλης επέλεγαν κάθε χρόνο κάποιους από του πλούσιους της πόλης ως χορηγούς για κοινά έξοδα (θέατρο, κατασκευή πλοίων, αγώνες κτλ). Ένας επιλεγμένος Αθηναίος είχε τη δυνατότητα να μην πληρώσει, επικαλούμενος την Αντίδοση, η οποία του επέτρεπε να κατονομάσει έναν άλλο πολίτη που ήταν κατά τη γνώμη του πλουσιότερος. Ο δεύτερος πολίτης είχε τότε την δυνατότητα να πληρώσει (εάν πίστευε πως είναι όντως πλουσιότερος) αλλιώς ο πρώτος πολίτης μπορούσε να προτείνει την ανταλλαγή των περιουσιών μεταξύ των δύο πλουσίων. Σε περίπτωση που ο δεύτερος αρνιόταν την ανταλλαγή, τη διαφορά έλυνε το δικαστήριο, με τον πλουσιότερο τελικά να πληρώνει τη χορηγία.

Goethe, age 38, painted by Angelica Kauffman 1787.

Το δεύτερο ευφυές παράδειγμα αφορούσε το Γερμανό συγγραφέα Γκαίτε, ο οποίος θέλοντας να εξασφαλίσει την πληροφορία για το μέγεθος του ποσού που ήταν διατεθειμένος να πληρώσει ο εκδότης του για το έργο «Χέρμαν και Δωροθέα», έκανε την παρακάτω συμφωνία με αυτόν: Ο Γκαίτε θα παρέδιδε στο δικηγόρο του ένα σφραγισμένο φάκελο με το ποσό που ζητούσε για το έργο του. Στη συνέχεια ο εκδότης θα ανακοίνωνε την προσφορά του στον δικηγόρο. Εάν το ποσό της προσφοράς ήταν χαμηλότερο από το ποσό που αναγραφόταν στο φάκελο, ο Γκαίτε θα απέσυρε το ενδιαφέρον του για συνεργασία. Σε αντίθετη περίπτωση θα έκλεινε συμφωνία με τον εκδότη, λαμβάνοντας όμως το ποσό που είχε ζητήσει αρχικά στο φάκελο. Το κέρδος για το συγγραφέα θα ήταν η γνώση των προθέσεων του εκδότη του, που θα μπορούσε να εκμεταλλευθεί στο μέλλον.

Πάνω στις συγκεκριμένες αλλά και άλλες πρακτικές στηρίχτηκε ένας ολόκληρος κλάδος μαθηματικών που σήμερα ονομάζεται θεωρία παιγνίων και μελετά μεταξύ άλλων τις δημοπρασίες, οι οποίες όπως φανέρωσε ο ομιλητής διαδραματίζουν πολύ σημαντικό ρόλο στο Διαδίκτυο αλλά και την καθημερινή ζωή. Για παράδειγμα, κάθε φορά που επισκεπτόμαστε μία ιστοσελίδα, η διαφήμιση που βλέπουμε κάθε άλλο τυχαία δεν είναι αφού είναι προϊόν μιας δημοπρασίας που λαμβάνει χώρα στο παρασκήνιο, και σχετίζεται με τις πληροφορίες που έχει ο υπολογιστής μας για τις συνήθειες και τις προτιμήσεις μας (cookies).

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

Σε έναν αξιοσημείωτο διαχωρισμό, ο κ. Δασκαλάκης μίλησε για τις διαφορές μεταξύ σύνθετων συστημάτων εφαρμοσμένης Μηχανικής (διαστημόπλοια, γέφυρες κτλ) και κοινωνικών συστημάτων όπως η πολιτική και η οικονομία. Τα πρώτα διέπονται από πολυπλοκότητα, κεντρικό σχεδιασμό, πολλά και συνεργαζόμενα μέρη και περιορισμένους πόρους. Στα δεύτερα οι περιορισμένοι πόροι και η πολυπλοκότητα παραμένουν, ωστόσο τα μέρη είναι πλέον ανταγωνιζόμενα και ο σχεδιασμός κατανεμημένος.

Με τον παραπάνω διαχωρισμό υπόψη, μίλησε για την ιδιαιτερότητα του Διαδικτύου που ξεκίνησε ως ένα σύστημα Μηχανικής, για να καταλήξει σε ένα μη κατανεμημένο σύστημα που μοιάζει με αυτά της οικονομίας. Η εύρεση ενός τρόπου περαιτέρω σχεδιασμού ενός τέτοιου συστήματος είναι πλέον από τα κεντρικά ερωτήματα στην έρευνα του ομιλητή.

Από την Οικονομία έχουμε διδαχτεί πως η συμπεριφορά μεγάλων συστημάτων ανταγωνιζόμενων μερών τις περισσότερες φορές δε μπορεί καν να προσεγγισθεί (Daskalakis et al. ’06, ‘11). Επομένως, τα Οικονομικά δεν έχουν τα κατάλληλα εργαλεία για την περιγραφή τέτοιων συστημάτων και είναι ανοικτό το ερώτημα της νέας θεωρίας που θα καλύψει αυτό το κενό.

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

Πιθανή ανακάλυψη ενός αστρικού αντικειμένου Thorne–Żytkow, Bizarre star could host a neutron star in its core

Τα αντικείμενα Θορμ-Ζίτλοφ υποτίθεται ότι σχηματίζονται όταν ένας κόκκινος γίγαντας καταπιεί ένα άστρο νετρονίων (δεξιά). Thorne-Zytkow objects could form when a red giant swallows a neutron star (right). John Foster/Science Photo Library

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

Η νέα μελέτη, η οποία παρουσιάστηκε στο συνέδριο της Αμερικανικής Αστρονομικής Εταιρείας στην Ουάσινγκτον, προσφέρει «τις πιο πειστικές ενδείξεις» για την ύπαρξη των αλλόκοτων αντικειμένων «Thorne–Żytkow».

Η ύπαρξη αυτών των αντικειμένων είχε προταθεί τη δεκαετία του 1970 τον Kip Thorne και την Anna Żytkow. Οι δύο αστροφυσικοί είχαν υπολογίσει ότι τα άστρα αυτά σχηματίζονται όταν ένας κόκκινος γίγαντας καταπιεί ένα άστρο νετρονίων.

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

NEUTRON STAR: Known as the dense remains of a supernova, scientists now believe they have found a neutron star within a red giant, or what is theoretically known as a Thorne-Zytkow object. Image: Casey Reed/Penn State University/Wikimedia Commons

Τα άστρα νετρονίων, αντίθετα, είναι τα κουφάρια μεγάλων άστρων, τα υπολείμματα της έκρηξης σουπερνόβα. Είναι εξαιρετικά θερμά και πυκνά – η πυκνότητά τους φτάνει την πυκνότητα των ατομικών πυρήνων.

«Βρήκαμε τις πιο πειστικές ενδείξεις για αυτό την ύπαρξη αυτού του μοντέλου» δηλώνει στο δικτυακό τόπο του Nature η Emily Levesque, η επικεφαλής της μελέτης.

Η ομάδα της Levesque χρησιμοποίησε τα τηλεσκόπια «Μαγγελάνος» στη Χιλή για να πραγματοποιήσει φασματικές αναλύσεις σε 22 ερυθρούς υπεργίγαντες στο Μικρό Νέφος του Μαγγελάνου, έναν νάνο γαλαξία δορυφόρο του δικού μας γαλαξία.

Το άστρο που εντόπισαν περιέχει υψηλά επίπεδα Λιθίου, Ρουβιδίου και Μολυβδαινίου, στοιχείων που σπανίζουν στα κανονικά άστρα και θα μπορούσαν να παράγονται από ασυνήθιστες πυρηνικές αντιδράσεις στα αντικείμενα Thorne–Żytkow.

Σύμφωνα με τον Kip Thorne που είχε προτείνει την ιδέα, το άστρο που εντοπίζει η τελευταία μελέτη είναι ο καλύτερος υποψήφιος που έχει δει μέχρι σήμερα.

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