On the existence and computation of approximately groupwise maximin share fair allocations

Abstract

The fair division of indivisible goods among agents with heterogeneous preferences is a central problem in computational game theory. In this thesis, we study the existence and computation of approximately fair allocations under the Groupwise Maximin Share (GMMS) fairness notion, a strong guarantee requiring fairness within every possible subgroup of agents. Our contributions are threefold. First, for agents with submodular valuation functions, we establish that every EF1 allocation is also 1/n-GMMS, and furthermore that a simple algorithm achieves a 1/(4n−3)-GMMS guarantee via EFX. Second, we show that a classical reduction technique used for MMS does not extend to GMMS, revealing a fundamental structural gap between the two notions. Third, for three agents with additive valuations, we prove that a well-known algorithm guarantees a 0.68-GMMS allocation, strictly exceeding the previously known bound of 2/3.Η δίκαιη κατανομή αδιαίρετων αγαθών μεταξύ πρακτόρων με διαφορετικές προτιμήσεις αποτελεί κεντρικό ζήτημα της αλγοριθμικής θεωρίας παιγνίων. Στην παρούσα εργασία μελετάμε την ύπαρξη και τον υπολογισμό προσεγγιστικά δίκαιων κατανομών υπό την έννοια του Groupwise Maximin Share (GMMS), μια ισχυρή έννοια δικαιοσύνης που απαιτεί ικανοποίηση του κάθε πράκτορα σε κάθε δυνατή υποομάδα. Τα αποτελέσματά μας είναι τρία. Πρώτον, για πράκτορες με υποπρόσθετες συναρτήσεις αποτίμησης, αποδεικνύουμε ότι κάθε EF1 κατανομή είναι και 1/n-GMMS, και επιπλέον ότι ένας απλός αλγόριθμος παράγει εγγύηση 1/(4n−3)-GMMS μέσω EFX. Δεύτερον, δείχνουμε ότι μια κλασική τεχνική αναγωγής που χρησιμοποιείται για το MMS δεν επεκτείνεται στο GMMS, αναδεικνύοντας τη δομική δυσκολία της έννοιας. Τρίτον, για τρεις πράκτορες με προσθετικές αποτιμήσεις, αποδεικνύουμε ότι ένας γνωστός αλγόριθμος εγγυάται κατανομή 0.68-GMMS, υπερβαίνοντας το προηγουμένως γνωστό όριο των 2/3