BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/89
DTSTAMP:20230914T125909Z
SUMMARY:Reducibility Among Fractional Stability Problems
DESCRIPTION:Speaker: Rajmohan Rajaraman\nNortheastern University\nCollege o
f Computer & Information Science\nBoston\, MA 02115\nUnited\n\nAbstract: \
nIn a landmark paper\, Papadimitriou introduced several syntactic subclass
es of the search class TFNP (Total Function Nondeterministic Polynomial) b
ased on proof styles that (unlike TFNP) admit complete problems. One part
icularly notable subclass of TFNP is PPAD (Polynomial Parity Arguments on
Directed graphs)\, which includes a number of important stability problems
\, including the celebrated problem of finding Nash equilibria in matrix f
orm games. A recent series of results has culminated in showing that find
ing Nash equilibria in multi-player games is complete for PPAD.\n\nIn this
work\, we establish the PPAD-completeness of a number of outstanding stab
ility problems that arise in diverse applications\, including the followin
g: Fractional Stable Paths Problem (FSPP) -- Internet routing Core of Bal
anced Games -- Economics and Game theory Scarf's Lemma -- Combinatorics
Hypergraph Matching - Social Choice and Preference Systems. In fact\, we
show that no fully polynomial-time approximation schemes exist for these p
roblems unless PPAD is in FP. In addition to enhancing our repertoire of
PPAD-complete problems\, we expect the concepts and techniques in this wor
k to find future use in algorithmic game theory.\n\nIn the talk\, I will m
otivate the fractional stability problems being studied and will largely f
ocus on the Fractional Stable Paths Problem. I will present two new conce
pts that play a key role in our completeness reductions -- preference game
s and personalized equilibria. The talk will be largely self-contained n
o significant knowledge of algorithmic game theory will be assumed (joint
work with Shiva Kintali\, Laura Poplawski\, Ravi Sundaram\, and Shanghua T
eng).\n\nBio: Rajmohan Rajaraman is a Professor of Computer Science at Nor
theastern University in Boston. He received his Bachelor's in Computer Sc
ience at IIT Kanpur in 1991 and his PhD in Computer Science at the Univers
ity of Texas at Austin in 1997. He was a postdoctoral fellow at DIMACS be
fore joining the Northeastern faculty in 1998. His research interests inc
lude approximation algorithms\, algorithmic game theory\, distributed comp
uting\, and complex networks.\n
URL:https://www.tcs.tifr.res.in/web/events/89
DTSTART;VALUE=DATE:20100520
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR