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

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

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

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

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

(Σημείωμα του ομιλητή)