BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T185311Z
UID:Seminar-EcCo-577@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20180530T130000
DTEND:20180530T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Bart de Keijzer: Facility Reallocation on the Line\n\nWe consider a multi-stage facility reallocation problem on the real line, where a facility is being moved between stages based on the locations reported by n agents. The aim of the reallocation mechanism is to minimize the social cost, i.e., the sum over the total distance between the facility and all agents at all stages, plus the cost incurred for moving the facility. We study this problem both in the offline setting and online setting. In the offline case the mechanism has full knowledge of the agent locations in all future stages, and in the online setting the mechanism does not know these future locations and must decide the location of the facility on a stage-per-stage basis. We derive the optimal mechanism in both cases. For the online setting we show that its competitive ratio is (n+2)/(n+1). As neither of these mechanisms turns out to be strategyproof, we propose another strategyproof  mechanism which has a competitive ratio of (n + 3)/(n + 1) for odd n and (n + 4)/n for even n, which we conjecture to be the best possible. We also consider a generalization with multiple facilities and weighted agents, for which we show that the optimum can be computed in polynomial time for a fixed number of facilities.\n\nJoint work with Dominik Wojtczak.\nTo appear in IJCAI 2018.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=577
LOCATION:
END:VEVENT
END:VCALENDAR