BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/711
DTSTAMP:20230914T125935Z
SUMMARY:Computing Equilibria in Atomic Splittable Routing Games
DESCRIPTION:Speaker: Phani Raj Lolakapuri\n\nAbstract: \nAn atomic splittab
le routing game (ASRG) is a network congestion problem where each player h
as some finite amount of flow he wants to send in the network\, while mini
mizing his cost due to congestion. It is known that equilibria exist in th
ese games\, and can be computed in polynomial-time for the case of linear
cost functions. However\, the case of equilibrium computation with more ge
neral cost functions has been an open problem for many years.\n\nWe give a
n algorithm for computing an equilibrium in the case of parallel-edge grap
hs with quadratic cost functions and two players. Our algorithm is obtaine
d by using support enumeration\, along with convex programming and results
about the structure of equilibrium with quadratic cost functions. We also
present some obstacles to generalizing our algorithm to more general case
s.\n\nFinally\, we present some hardness results regarding equilibrium com
putation in more general games\, when different players may experience dif
ferent delays on an edge.\n
URL:https://www.tcs.tifr.res.in/web/events/711
DTSTART;TZID=Asia/Kolkata:20160914T140000
DTEND;TZID=Asia/Kolkata:20160914T153000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR