Cafe Scientifique: Πώς να μοιράσετε δίκαια τα αγαθά, με την βοήθεια των μαθηματικών

Στην ομιλία θα εστιάσουμε σε μια κατηγορία αλγοριθμικών προβλημάτων, που αναφέρονται στην βιβλιογραφία ως "cake-cutting problems". Ο βασικός στόχος της λύσης σε όλα αυτά τα προβλήματα είναι να μοιράσουμε με δίκαιο τρόπο ένα σύνολο από αντικείμενα ή ένα σύνολο από δουλειές, σε κάποιες εμπλεκόμενες οντότητες (π.χ. άνθρωποι, υπολογιστές, ρομπότ).

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

Σε όλα αυτά τα προβλήματα, το κοινό χαρακτηριστικό είναι ότι κάθε οντότητα έχει τις δικές της προτιμήσεις και απολαμβάνει κάποια “ωφέλεια” για κάθε αντικείμενο που της ανατίθεται (η ωφέλεια μπορεί να είναι θετική ή αρνητική ανάλογα με το αν υπάρχει χαρά ή δυσαρέσκεια για την εν λόγω ανάθεση). Ο στόχος μας επομένως είναι να μοιράσουμε τα διαθέσιμα αντικείμενα έτσι ώστε η τελική ανάθεση να είναι όσο το δυνατόν πιο δίκαιη με βάση τις υπάρχουσες προτιμήσεις. Πώς όμως αξιολογούμε πόσο δίκαιη είναι μια ανάθεση; Και πόσο εύκολα θα μπορούσαμε να παράγουμε αυτοματοποιημένα τέτοιες αναθέσεις;

Στην ομιλία θα εξηγήσουμε καταρχήν πώς μπορούμε να μοντελοποιήσουμε μαθηματικά τέτοια προβλήματα. Στη συνέχεια, θα παρουσιάσουμε κάποια από τα επικρατέστερα κριτήρια δικαιοσύνης που έχουν μελετηθεί. Για κάθε κριτήριο θα παρουσιάσουμε εν συντομία αλγορίθμους (ξεκινώντας από το κλασικό πλέον "cut and choose" protocol) οι οποίοι μπορούν να παράγουν δίκαιες μοιρασιές των αντικειμένων υπό προϋποθέσεις, ακόμα και όταν ο αριθμός των αντικειμένων ή ο αριθμός των οντοτήτων γίνεται πολύ μεγάλος. Τέλος, θα κλείσουμε παρουσιάζοντας τρέχοντα ερευνητικά θέματα.

Για την παρακολούθηση της ομιλίας δεν απαιτούνται πρότερες γνώσεις στην επιστήμη υπολογιστών.

Ο Βαγγέλης Μαρκάκης αποφοίτησε από τη Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών του ΕΜΠ, και έλαβε το μεταπτυχιακό του δίπλωμα (M.Sc.) και το διδακτορικό του δίπλωμα (Ph.D.) στην Επιστήμη Υπολογιστών από το Georgia Institute of Technology (ΗΠΑ) το 2005. Στη συνέχεια πραγματοποίησε μεταδιδακτορική έρευνα στο University of Toronto (Καναδάς, 2005-2006) και στο CWI (Center for Mathematics and Computer Science, Ολλανδία, 2007-2008). Από το 2009 εργάζεται στο Οικονομικό Πανεπιστήμιο Αθηνών, αρχικά ως Λέκτορας (2009-2014) και μετέπειτα ως Επίκουρος Καθηγητής στο Τμήμα Πληροφορικής. Τα ερευνητικά του ενδιαφέροντα εστιάζονται στη θεωρητική πληροφορική, και την ανάλυση αλγορίθμων, με έμφαση σε προβλήματα ανάθεσης πόρων, στη σχεδίαση μηχανισμών για δημοπρασίες, σε προβλήματα τιμολόγησης και γενικότερα σε αλγοριθμικά θέματα συνδυαστικής βελτιστοποίησης.

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

Οι ομιλίες γίνονται μια φορά το μήνα, ημέρα Δευτέρα, στις 7μμ, στο κελάρι του Athenaeum (Αδριανού 3, Θησείο, 210 3210239). Η είσοδος στις εκδηλώσεις είναι ελεύθερη, αλλά υπάρχει μια ελάχιστη κατανάλωση 3 ευρώ.

Για περισσότερες πληροφορίες σχετικά με το CAFΕ SCIENTIFIQUE στην Ελλάδα,μπορείτε να επικοινωνήσετε με την Δρ. Λίλα Κουμάντου στο email: cafesci.gr@gmail.com.

Επόμενη ομιλία: Δευτέρα 13 Φεβρουαρίου 2017

«DNA, διατροφή και μακροζωία»
Αντιγόνη Δήμα, Ερευνήτρια Γ', Τομέας Μοριακής Βιολογίας και Γενετικής, Ερευνητικό Κέντρο Βιοϊατρικών Επιστημών Αλέξανδρος Φλέμινγκ.