BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T212118Z
UID:Seminar-EcCo-966@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20201202T130000
DTEND:20201202T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Julian Nickerl: Congestion Games: The Minimum Tollbooth Problem and Games with Uncertainty\n\nIn congestion games, players have to share a set of resources to achieve personal goals. Cars in a road network are a typical intuitive example. While everybody has a different origin and destination, they have to share the same roads, creating congestion on the way. To reduce stress on the network it would be beneficial if some participants of the network diverted to less favorable routes. Assuming selfish behavior, there is little incentive to do so, however. In the tollbooth problem tolls can be levied for the use of a road to create a financial incentive for such a diversion. The goal of the minimum tollbooth problem is to additionally minimize the tolled roads. In a separate branch of research on congestion games the reliability of the resources is in question, assuming that each is available only with a given probability. Even basic properties have to be reconsidered, in particular the definition of a strategy requires an extension.\n\nIn this talk, I present recent algorithmic and complexity theoretic research in both fields. In particular, I consider the minimum tollbooth problem in games with finite player and strategy sets, outlining a hardness result in the general case and a polynomial-time algorithm on series-parallel networks. I introduce a new model of games with uncertainty and demonstrate its completeness for a new complexity class based on PLS.\n\n\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=966
LOCATION:
END:VEVENT
END:VCALENDAR