| Abstract : | 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.
Η θεωρία της δίκαιης διαίρεσης αντιμετωπίζει το θεμελιώδες πρόβλημα της κατανομής αγαθών και αντικειμένων μεταξύ πρακτόρων με δίκαιο και αποτελεσματικό τρόπο. Τέτοια προβλήματα προκύπτουν σε πολλές πραγματικές συνθήκες όπως κρατικές δημοπρασίες ή διακανονισμοί διαζυγίου. Για να μοντελοποιήσουμε αυτά τα προβλήματα ανάθεσης αγαθών, πρέπει να καθορίσουμε τις προτιμήσεις των πρακτόρων και το κριτήριο της δικαιοσύνης, που καθορίζει τι σημαίνει "δίκαιη" ανάθεση. Για τις προτιμήσεις, η συνηθισμένη υπόθεση είναι η συσχέτιση κάθε πράκτορα με μια συνάρτηση αποτίμησης (αθροιστική συνάρτηση) σε ένα σύνολο προϊόντων. Όσον αφορά τα κριτήρια δικαιοσύνης οι δύο σημαντικότερες έννοιες είναι οι εξής:- "Αναλογικότητα": Μια αναλογική ανάθεση αντικειμένων είναι μια ανάθεση ενός πόρου μεταξύ n παραγόντων έτσι ώστε κάθε πράκτορας να λαμβάνει ένα μερίδιο που αξίζει για αυτόν το 1/n του συνόλου, όπου n είναι ο αριθμός των παραγόντων.- "envy-freeness": Το κριτήριο αυτό απαιτεί ο κάθε πράκτορας να προτιμά το δικό του μερίδιο σε σχέση με κάθε άλλου πράκτορα.Το κριτήριο "envy-freeness" είναι ισχυρότερο από αυτό της αναλογικότητας.Στην περίπτωση όπου τα αγαθά μπορούν να διαιρεθούν, έχει αποδειχθεί ότι υπάρχει πάντα μια κατανομή που είναι απαλλαγμένη από ζήλια. Δυστυχώς, αυτό τα αποτέλεσμα δεν επεκτείνεται στην περίπτωση των αδιαίρετων αγαθών. Η ύπαρξη "envy-free" αναθέσεων δεν μπορεί να διασφαλιστεί. Τα σχετικά αλγοριθμικά ερωτήματα και τα ερωτήματα προσέγγισης είναι επίσης υπολογιστικά δύσκολα. Αυτά τα αποτελέσματα έχουν παρακινήσει τους ερευνητές στη θεωρητική πληροφορική να αναπτύξουν πιο χαλαρές έννοιες δικαιοσύνης. Τέσσερις τέτοιες έννοιες είναι οι EF1, EFX, MMS, PMMS. Όλες αυτές οι έννοιες καταγράφουν διαφορετικούς τρόπους που επιτρέπουν το φθόνο σε μια ανάθεση αγαθών. Σε αυτή την εργασία, θα επικεντρωθούμε κυρίως στο EFX κριτήριο και θα διερευνήσουμε περαιτέρω τα θέματα της ύπαρξης και υπολογισμού. Δείξαμε ότι σε ορισμένες ειδικές περιπτώσεις μπορεί να βρεθεί μια EFX ανάθεση χρησιμοποιώντας αλγόριθμους πολυωνυμικού χρόνου. Επίσης, εξετάσαμε πειραματικά πόσο συχνά μία EFX ανάθεση είναι επίσης envy-free και πόσο συχνά μια EF1 ανάθεση είναι και EFX. Τέλος, εξετάσαμε πώς ο αριθμός πρακτόρων και αγαθών επηρεάζει την ύπαρξη EFX αναθέσεων.
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.