«Πώς να μοιράσετε την πίτα» εξηγεί ο Β. Μαρκάκης στο Cafe Scientifique

Το Cafe Scientifique υποδέχεται τη νέα χρονιά κόβοντας τη βασιλόπιτα με τον πιο επιστημονικό τρόπο! Στην εκδήλωση, η οποία είναι ανοικτή για το κοινό και θα πραγματοποιηθεί τη Δευτέρα 16 Ιανουαρίου, ο ομιλητής Βαγγέλης Μαρκάκης, Επίκουρος Καθηγητής στο Τμήμα Πληροφορικής του Οικονομικού Πανεπιστημίου Αθηνών θα εξηγήσει πώς μπορούν να βοηθήσουν τα μαθηματικά και η επιστήμη υπολογιστών στη δίκαιη μοιρασιά αγαθών.

Η ομιλία, που θα λάβει χώρα στις 19:00 μ.μ. στο κελάρι του Athenaeum (Αδριανού 3, Θησείο, με ελεύθερη, αλλά ελάχιστη κατανάλωση 3 ευρώ) θα εστιάσει σε μια κατηγορία αλγοριθμικών προβλημάτων, που αναφέρονται στην βιβλιογραφία ως «cake-cutting problems». Ο βασικός στόχος της λύσης σε όλα αυτά τα προβλήματα είναι να μοιράσουμε με δίκαιο τρόπο ένα σύνολο από αντικείμενα ή ένα σύνολο από δουλειές, σε κάποιες εμπλεκόμενες οντότητες (π.χ. άνθρωποι, υπολογιστές, ρομπότ). Τέτοια προβλήματα έχουν εφαρμογές σε πεδία όπως η πληροφορική (σε θέματα δρομολόγησης διεργασιών και ανάθεσης πόρων), οι πολιτικές επιστήμες (στην ανάλυση εκλογικών κανόνων) και η μικροοικονομική θεωρία (σε θέματα ανάθεσης/πώλησης αγαθών). Για παράδειγμα, τα αντικείμενα μπορεί να αναπαριστούν τους πόρους ενός υπολογιστικού συστήματος (μνήμη, κτλ) και τότε οι οντότητες στις οποίες θα ανατεθούν είναι οι διαφορετικοί επεξεργαστές του συστήματος. Εναλλακτικά, τα αντικείμενα μπορεί να αποτελούν μια κληρονομιά (από αγαθά, ακίνητα, και άλλα περιουσιακά στοιχεία) και οι εμπλεκόμενες οντότητες να είναι οι κληρονόμοι. Ως ένα ακόμα παράδειγμα, τα αντικείμενα μπορούν να εκφράζουν τις πτήσεις μιας αεροπορικής εταιρείας και οι οντότητες να είναι τα αεροσκάφη στα οποία θα ανατεθούν οι πτήσεις.

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

Πώς όμως αξιολογούμε πόσο δίκαιη είναι μια ανάθεση; Και πόσο εύκολα θα μπορούσαμε να παράγουμε αυτοματοποιημένα τέτοιες αναθέσεις;

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

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

tech.in.gr