Bodossaki Lectures on Demand
ΙΔΡΥΜΑ ΜΠΟΔΟΣΑΚΗ

Πώς να μοιράσετε την πίτα: αλγόριθμοι για προβλήματα ανάθεσης αγαθών

Μαρκάκης Βαγγέλης

16 Ιανουαρίου 2017

ΟΜΙΛΙΕΣ
EXIT FULL SCREEN VIDEO & SLIDES
ΔΙΑΡΚΕΙΑ 66:49 ΠΡΟΒΟΛΕΣ 1348
ΔΙΑΦΑΝΕΙΕΣ /

 Στην ομιλία εστιάζουμε σε μια κατηγορία αλγοριθμικών προβλημάτων, που αναφέρονται στην βιβλιογραφία ως "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) και μετέπειτα ως Επίκουρος Καθηγητής στο Τμήμα Πληροφορικής. Τα ερευνητικά του ενδιαφέροντα εστιάζονται στη θεωρητική πληροφορική, και την ανάλυση αλγορίθμων, με έμφαση σε προβλήματα ανάθεσης πόρων, στη σχεδίαση μηχανισμών για δημοπρασίες, σε προβλήματα τιμολόγησης και γενικότερα σε αλγοριθμικά θέματα συνδυαστικής βελτιστοποίησης.

Σχετικές ομιλίες