BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T124517Z
UID:Seminar-EcCo-982@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20210203T130000
DTEND:20210203T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Alkmini Sgouritsa:  A Little Charity Guarantees Almost Envy-Freeness\n\nThe goal of this work is to distribute m goods to n agents in a “fair” manner, where every agent has a valuation for each subset of goods. "Envy-freeness up to any good" (EFX) is currently the most promising relaxation of envy freeness for the case of indivisible goods. An allocation satisfies EFX when no agent envies another agent after the removal of any single good from the latter’s bundle. It is not known if such an allocation always exists for more than 3 agents.\n\nWe show that there is always a partition of the set of goods into n+1 subsets (X1,...,Xn,P) where Xi is the bundle allocated to agent i and the set P is unallocated (or donated to charity) such that:\n\n- EFX is satisfied among agents,\n\n- no agent envies P and\n\n- fewer than n goods go to charity.\n\nOur proof is constructive and leads to a pseudo-polynomial time algorithm to find such an allocation. \n\n\n\nJoint work with Bhaskar Ray Chaudhury, Telikepalli Kavitha and Kurt Mehlhorn.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=982
LOCATION:
END:VEVENT
END:VCALENDAR