BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/438
DTSTAMP:20230914T125924Z
SUMMARY:An Algorithm for Locating the Nucleolus of Assignment Games
DESCRIPTION:Speaker: Professor T.E.S. Raghavan (University of Illinois at C
hicago\nDepartment of Mathematics\, Statistics and Computer Science\n851 S
. Morgan\nChicago\, IL 60607-7045\nUnited States of America)\n\nAbstract:
\nAbstract: In cooperative game theory\, Shapley value and the nucleolus
are two fundamental solution concepts. They associate a unique imputati
on for the players whose coalitional worth $s$ are given a priori. \
nAssignment games are two sided matching games (say between sellers and bu
yers) where the coalitional worths between a buyer and seller are specif
ied by a nonnegative matrix. (Here\, the rows of the matrix represent
sellers and the columns of the matrix represent buyers). While an opti
mal assignment correspond to best deal\, for real estate agent eyeing on
commissions from both sellers and buyers\, he can always initiate an impu
tation from the core \, via the dual optimal solutions. The algorithm
at the end of the first iteration reaches the unique corner that favors al
l sellers. Nucleolus is invariably a relative interior point of the core a
nd the algorithm at each iteration always selects the this most favorabl
e imputation for all sellers in a shrinking family of imputation polyt
opes. Here the shrinking process correspond to the faces of the polytope m
oving inside at varying speeds. We can associate with each face of the c
urrent polytope\, the so called unsettled coalitions that clamor for grea
ter satisfaction for its members. Improvements correspond to redistributio
ns captured through the notion of squeezing the faces of the polytope by
applying different levels of pressure and reducing the dimension of the c
urrent subset of the imputation set. The algorithm terminates when this sq
ueezing process terminates in a single point. The determination of applyin
g such varied pressures is achieved through the longest path ending at eac
h vertex of an associated graph. The algorithm starts with just a set of v
ertices of a graph with no arcs to start with. In each intermediate stag
e\, one introduces directed arcs corresponding to the equivalence class of
unsettled and unhappy coalitions. When more and more arcs are introduced\
, we reach cycles and the vertices within a cycle are identified as equiva
lent and are shrunk to just one representative vertex. This way\, at the e
nd of an iteration\, the number of vertices of the graph are reduced at le
ast by one. New directed arcs are introduced in the next iteration and thi
s process continues till just one vertex survives. The algorithm termina
tes at this stage and the associated imputation is the nucleolus. The algo
rithm exploits the special lattice structure of the core for assignment ga
mes and all computations involve only dealing with the small class of buye
r seller pairs. \nMany other subclasses of cooperative games like the conn
ected games and some subclass of permutation games have similar algorithms
for locating the nucleolus. As for locating the Shapley value\, the p
roblems are wide open.\n
URL:https://www.tcs.tifr.res.in/web/events/438
DTSTART;TZID=Asia/Kolkata:20140106T160000
DTEND;TZID=Asia/Kolkata:20140106T170000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR