Title: A graph theoretic algorithm to locate the nucleolus of assignment game
Speaker: Professor T. E. S. Raghavan
Time and Date: 11:45am, Saturday, March 14, 2015
Venue: 211, Mech. Engg. Building
Abstract: The nucleolus is the unique solution for a TU cooperative game which lexicographically maximizes the minimum happiness of coalitions. It is also the geometric center of an iterative family of polyhedral convex subsets of the imputation set. Since assignment games are determined by two person coalitions of sellers and buyers, the algorithm consists in decomposing the two person coalitions into equivalence classes and using them as vertices of a graph, directed arcs are introduced corresponding to currently most unhappy coalitions and when new directed arcs are introduced one faces cycles and we collapse any cycle into a single vertex and the graph has fewer vertices. The iterations continue till we reduce the graph to a single vertex. The outcome is a simultaneous shrinking of the polyhedra on which more and more coalitions are constant valued and finally terminate when it is a unique point.
About the Speaker: Professor Raghavan is an internationally wellknown game theorist, particularly for his contributions to stochastic games and cooperative games. He is currently with University of Illinois, Chicago, and has held many visiting positions.