BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260826T060039Z
UID:Seminar-dept-963@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20201109T110000
DTEND:20201109T120000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Vangelis Markakis: Approximation Guarantees for Fairness Notions under Indivisible Resources\n\nWe consider fair division problems where a set of resources needs to be allocated to a set of agents. Within the last decade, several fairness criteria have been introduced, that are tailored to settings with indivisible goods. However, due to the lack of general existence results for most of these concepts, great attention has been paid to establishing approximation guarantees.\n\n\n\nThe talk will begin with an overview of such fairness notions. Out of these, we will first focus on the EFX criterion (envy-freeness up to any item) and propose a simple algorithm that achieves a 0.618-approximation (i.e., equal to \phi-1, with \phi being the golden ratio). This improves upon the previously known ½-approximation algorithms. We then exhibit that our algorithm is “universally” fair in the sense that it returns allocations that have good guarantees with respect to other notions as well. In particular, the same algorithm achieves at the same time a better than ½-approximation for the criteria of GMMS and PMMS (groupwise and pairwise maximin share fairness) and also satisfies EF1 (envy-freeness up to one item). Finally, we will elaborate on further connections between these fairness notions, and conclude with open problems that stem from this line of research.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=963
LOCATION:Microsoft Teams
END:VEVENT
END:VCALENDAR