Δίκαιη Διανομή Ανομοιογενούς Αγαθού: Κόψιμο Του Κέικ

Abstract

Τα τελευταία χρόνια, εντός των ορίων των θεμάτων που πραγματεύεται η θεωρητική πληροφορική, μεγάλο έδαφος στις έρευνες και τη βιβλιογραφία έχει κερδίσει το mechanism design. Ο κλάδος αυτός είναι ένα υποσύνολο της θεωρίας παιγνίων, που προσφέρει διάφορα σενάρια λύσεων σε μια κλάση παιχνιδιών με μυστική ατομική πληροφορία για τους παίκτες. Τα σημαντικότερα χαρακτηριστικά του mechanism design επικεντρώνονται κυρίως σε δυο σημεία: αφενός οι άμεσα ενδιαφερόμενοι με ένα παιχνίδι επιλέγουν τη δομή του παρά την υιοθετούν, και αφετέρου οι σχεδιαστές του ενδιαφέρονται για το αποτέλεσμα του. Ένα από τα προβλήματα στα οποία έχει εφαρμογή το mechanism design είναι η δίκαιη κατανομή αγαθών. Το πρόβλημα αυτό μας είναι γνωστό από πολλές πτυχές του δημόσιου βίου, και η εφαρμογή της μαθηματικής θεωρίας πάνω σε αυτό το καθιστά γνωστό ως το πρόβλημα «τομής του κέικ». Το σύνολο της βιβλιογραφίας που έχει αναπτυχθεί πάνω στο θέμα αυτό έχει να κάνει με την παρουσίαση πρωτοκόλλων που καλύπτουν μερικές ποικιλόμορφες ανάγκες, παρουσιασμένες από την ποικιλόμορφη και πολυπρισματική μελέτη του. Οι ανάγκες αυτές άλλοτε είναι ατομικές, και άλλοτε ομαδικές, μιας και το ζητούμενο κάθε φορά είναι η υπερκάλυψη διαφορετικών κριτηρίων μέσω αλγοριθμικών λύσεων.Στην παρούσα εργασία θα γίνει μια σύνοψη της βιβλιογραφίας για το κόψιμο του κέικ από τα τελευταία περίπου 70 χρόνια, όπου έχει καταγραφεί μια πλούσια μελέτη επί του θέματος. Στην ανασκόπηση αυτή θα παρατεθούν επίσης ορισμένα ιστορικά στοιχεία για το πρόβλημα αυτό, καθώς και συμπεράσματα που προκύπτουν, αναθεωρημένα πάντα από την οπτική του γράφοντος.