Μεταπτυχιακές Εργασίες
Μόνιμο URI για αυτήν τη συλλογήhttps://pyxida.aueb.gr/handle/123456789/7
Περιήγηση
Πλοήγηση Μεταπτυχιακές Εργασίες ανά Θέμα "Fair division"
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω
Τώρα δείχνει 1 - 3 από 3
- Αποτελέσματα ανά σελίδα
- Επιλογές ταξινόμησης
Τεκμήριο Solution concepts and algorithms for fair division under constraints(2025-10-01) Mancho, Alviona; Amanatidis, Georgios; Sgouritsa, Alkmini; Markakis, VangelisΤο πρόβλημα της δίκαιης ανάθεσης πόρων—πώς να διαμοιραστούν οι πόροι μεταξύ ατόμων με διαφορετικές προτιμήσεις με δίκαιο τρόπο—έχει απασχολήσει τους μαθηματικούς και τους οικονομολόγους από την αρχαιότητα, με το πρόβλημα κατανομής της γης, έως τα προβλήματα που ανακύπτουν σε σύγχρονα περιβάλλοντα, όπως η ανάθεση πόρων στο cloud ή ο διαμοιρασμός της κληρονομιάς. Ενώ, όμως, τα διαιρετά αγαθά μπορούν να κατανεμηθούν χρησιμοποιώντας γνωστά πρωτόκολλα, τα αδιαίρετα αγαθά παρουσιάζουν προκλήσεις. Ένα καθιερωμένο κριτήριο δικαιοσύνης είναι η απουσία φθόνου (EF), η οποία απαιτεί κανένας συμμετέχοντας (στο εξής πράκτορας) να μην προτιμά το μερίδιο (στο εξής πακέτο) ενός άλλου από το δικό του. Ωστόσο, όσον αφορά τα αδιαίρετα αγαθά, η απουσία φθόνου είναι συχνά ανέφικτη, γεγονός που οδηγεί στη μελέτη χαλαρώσεων, όπως η απουσία φθόνου έως ένα αγαθό (envy-freeness up to one good, EF1) και η απουσία φθόνου έως οποιοδήποτε αγαθό (envy-freeness up to any good, EFX). Η παρούσα διπλωματική εργασία επικεντρώνεται στην περίπτωση όπου ισχύουν πρόσθετοι περιορισμοί σχετικά με τις εφικτές αναθέσεις. Ένα πραγματικό σενάριο είναι όταν οι πράκτορες πρέπει να λάβουν τον ίδιο αριθμό αγαθών. Για να αντιμετωπιστούν τέτοιες καταστάσεις, πρόσφατες εργασίες έχουν εισαγάγει έννοιες δικαιοσύνης βασισμένες στην ανταλλαγή, όπως οι EFF1 και EFFX, όπου ο φθόνος μπορεί να εξαλειφθεί με την ανταλλαγή ενός (ή, αντίστοιχα, οποιουδήποτε) αγαθού μεταξύ των πακέτων. Αυτοί οι ορισμοί ευθυγραμμίζονται φυσικά με τον περιορισμό που περιγράψαμε, αλλά οι ιδιότητές τους παραμένουν σε μεγάλο βαθμό ανεξερεύνητες. Η συμβολή της διπλωματικής εργασίας εκτείνεται σε δύο άξονες. Πρώτον, παρέχει μια ολοκληρωμένη επισκόπηση της βιβλιογραφίας σχετικά με τη δίκαιη κατανομή αδιαίρετων αγαθών, με έμφαση σε μοντέλα με περιορισμούς (πληθικότητας, συνδεσιμότητας, προϋπολογισμού και μητροειδών). Δεύτερον, παρουσιάζει νέα αποτελέσματα σχετικά με τα κριτήρια δικαιοσύνης βάσει ανταλλαγής, διερευνώντας την ύπαρξή τους και την επίδοση γνωστών αλγορίθμων όπως ο Envy Cycle Elimination. Επιπλέον, μελετάμε σε ποιο βαθμό μπορούν να συνυπάρξουν η δικαιοσύνη και η αποδοτικότητα.Τεκμήριο Algorithms for fair division with indivisible items(2019-07-01) Ντόκος, Απόστολος; Ntokos, Apostolos; Athens University of Economics and Business, Department of Informatics; Κουτσόπουλος, Ιορδάνης; Τελέλης, Ορέστης; Μαρκάκης, ΕυάγγελοςThe theory of fair division addresses the fundamental problem of allocating goods, items,tasks or chores among agents in a fair and efficient manner. Such problems arise in many real-world settings such as government auctions or divorce settlements. To model such allocationproblems, one needs to specify the preferences of the agents, and the fairness criterion. Forthe preferences, the usual assumption is to associate each agent with an additive valuationfunction on a set of goods. As for fairness criteria, two of the classic notions that have beenproposed are:• proportionality: A proportional division is a division of a resource among n agents suchthat each agent receives a part worth for him at least a 1/n fraction of the whole, wheren is the number of the agents.• envy-freeness: Envy-freeness requires that each agent prefers her own allocation overthat of any other agent.The envy-freeness notion is stronger than proportionality. For the divisible setting of the prob-lem, it has been proved that there always exists an allocation that is envy-free. Unfortunately,these results do not extend to the setting of indivisible goods. In fact, many of the classicalsolution concepts and algorithms that have been developed for divisible goods are not directlyapplicable to indivisible goods. Existence of envy-free allocations cannot be guaranteed andthe relevant algorithmic and approximability questions are also computationally hard. Theseconsiderations have motivated recent work in theoretical computer science on developing rel-evant relaxed notions of fairness. Four such notions are: envy-freeness up to one good (EF1),envy-freeness up to any good (EFX), maximin share fairness (MMS) and pairwise maximinshare fairness (PMMS). These relaxations of envy-freeness seem more appropriate for settingswith indivisible items. All these capture different ways of allowing envy in an allocation. Inthis work, we will mainly focus on the EFX relaxation and we investigate further the issuesof existence and computation. We show that in some special cases an EFX allocation can befound using polynomial time algorithms. We also examine experimentally how often an EFXallocation is also envy-free and how often an EF1 allocation is EFX, too. Finally, we examinehow the number of agents and items affects the existence of EFX allocations.Τεκμήριο Development of web application implementing Fair Division algorithms(2024-10-27) Κιβωτός, Κωνσταντίνος; Kivotos, Konstantinos; Athens University of Economics and Business, Department of Informatics; Markakis, Evangelos; Dimakis, Antonios; Sgouritsa, AlkminiΗ δίκαιη κατανομή αδιαίρετων πόρων μεταξύ των πρακτόρων αποτελεί μια μακροχρόνια πρόκληση στο πεδίο της Αλγοριθμικής Θεωρίας Παιγνίων. Με την πάροδο των ετών, έχουν αναπτυχθεί διάφορα κριτήρια δικαιοσύνης για την αντιμετώπιση αυτού του ζητήματος, οδηγώντας στο σχεδιασμό αλγορίθμων που στοχεύουν στη δίκαιη κατανομή των πόρων. Παρά τη σημαντική πρόοδο, αυτοί οι αλγόριθμοι παρουσιάζονται συνήθως σε ψευδοκώδικα, με τη μόνη πρακτική εφαρμογή να είναι το Spliddit, το οποίο έχει τους δικούς του περιορισμούς. Η παρούσα πτυχιακή όχι μόνο διερευνά τους αλγορίθμους που σχετίζονται με δύο από τις πιο ευρέως μελετημένες έννοιες δικαιοσύνης, την Envy-Freeness up to One Good (EF1) και την Envy-Freeness up to Any Good (EFX), αλλά και τους υλοποιεί σε μια πλήρως λειτουργική διαδικτυακή εφαρμογή. Η εφαρμογή που αναπτύχθηκε επιτρέπει στους χρήστες να εισάγουν τις επιθυμητές παραμέτρους, να επιλέγουν μεταξύ αλγορίθμων και να λαμβάνουν λεπτομερή αποτελέσματα μαζί με πρόσθετες ιδιότητες δικαιοσύνης των κατανομών. Επιπλέον, η παρούσα διατριβή χρησιμεύει ως ένας ολοκληρωμένος οδηγός για την εφαρμογή, παρέχοντας πληροφορίες σχετικά με το σχεδιασμό, τη λειτουργικότητα και τη χρήση της.