BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T052510Z
UID:Seminar-EcCo-590@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20190116T130000
DTEND:20190116T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Piotr Krysta: An Impossibility Result for Equal-cost Mechanism Design with Monitoring for Binary Covering Problems\n\nWe apply the equal-cost mechanism design paradigm with monitoring to the class of problems which are binary covering problems with the objective function of minimising the social cost. This class contains many natural network design problems, for instance, minimum cost Steiner tree problem, minimum cost 2-edge-connected spanning subgraph problem, etc. We prove that no deterministic b-approximation algorithm for any problem in this class is an equal-cost truthful mechanism with monitoring for any b > 1, even if agents are single-dimensional. This is an unconditional impossibility result. On the other hand, we also show that any such b-approximation algorithm implies an equal-cost b-truthful mechanism with monitoring for any such problem.\n\nThis is joint work with Dimitris Fotakis and Carmine Ventre.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=590
LOCATION:
END:VEVENT
END:VCALENDAR