BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T210837Z
UID:Seminar-EcCo-989@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20210303T130000
DTEND:20210303T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Martin Gairing: In Congestion Games, Taxes Achieve Optimal Approximation\n\nWe consider the problem of minimizing social cost in atomic congestion games and show, perhaps surprisingly, that efficiently computed taxation mechanisms yield the same performance achievable by the best polynomial time algorithm, even when the latter has full control over the players’ actions. It follows that no other tractable approach geared at incentivizing desirable system behavior can improve upon this result, regardless of whether it is based on taxations, coordination mechanisms, information provision, or any other principle. In short: judiciously chosen taxes achieve optimal approximation.\n\nThree technical contributions underpin this conclusion. First, we show that computing the minimum social cost is NP-hard to approximate within any factor smaller than a given expression depending solely on the class of admissible resource costs. Second, we design a tractable taxation mechanism whose efficiency (price of anarchy) matches the hardness factor, and, thus, is optimal. As these results extend to coarse correlated equilibria, any no-regret algorithm inherits the same performances, allowing us to devise polynomial time approximation algorithms with optimal performance.\n\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=989
LOCATION:
END:VEVENT
END:VCALENDAR