Speaker: |
T.E.S. Raghavan (University of Illinois at Chicago Department of Mathematics, Statistics and Computer Science 851 S. Morgan Chicago, IL 60607-7045 United States of America) |

Organiser: |
Sandeep K Juneja |

Date: |
Thursday, 12 Mar 2015, 16:00 to 17:00 |

Venue: |
AG-66 (Lecture Theatre) |

(Scan to add to calendar)

An 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 of the payoff space and the lattice-type structure of the feasible set are utilized in associating a directed graph. Finding the next payoff is translated 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 operations.