BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/588
DTSTAMP:20230914T125930Z
SUMMARY:An Algorithm for Finding the Nucleolus of Assignment Games
DESCRIPTION:Speaker: T.E.S. Raghavan (University of Illinois at Chicago\nDe
partment of Mathematics\, Statistics\nand Computer Science\n851 S. Morgan\
nChicago\, IL 60607-7045\nUnited States of America)\n\nAbstract: \nAbstrac
t: Assignment games with side payments are models of certain two-sided mar
kets. It is known that prices which competitively balance supply and deman
d correspond to elements in the core. The nucleolus\, lying in the lexicog
raphic center of the nonempty core\, has the additional property that it s
atisfies each coalition as much as possible. The corresponding prices favo
r neither the sellers nor the buyers\, hence provide some stability for th
e market.\n\nAn algorithm is presented that determines the nucleolus of an
assignment game. It generates a finite numberof payoff vectors\, monotone
increasing on one side\, and decreasing on the other. The decomposition o
f the payoff space and the lattice-type structure of the feasible set are
utilized in associating a directed graph. Finding the next payoff is trans
lated into determining the lengths of longest paths to the nodes\, if the
graph is acyclic\, or otherwise\, detecting the cycle(s). In an $(m\, n)$-
person assignment game with $m = min(m\, n)$ the nucleolus is found in at
most 1/2 $m(m+3)$ steps\, each one requiring at most $O(m n)$ elementary o
perations.\n
URL:https://www.tcs.tifr.res.in/web/events/588
DTSTART;TZID=Asia/Kolkata:20150312T160000
DTEND;TZID=Asia/Kolkata:20150312T170000
LOCATION:AG-66 (Lecture Theatre)
END:VEVENT
END:VCALENDAR