Tata Institute of Fundamental Research
An Algorithm for Finding the Nucleolus of Assignment Games
STCS Seminar
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)
Abstract:
Abstract: Assignment games with side payments are models of certain two-sided markets. It is known that prices which competitively balance supply and demand correspond to elements in the core. The nucleolus, lying in the lexicographic center of the nonempty core, has the additional property that it satisfies each coalition as much as possible. The corresponding prices favor neither the sellers nor the buyers, hence provide some stability for the market.
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.
| 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)
Abstract:
Abstract: Assignment games with side payments are models of certain two-sided markets. It is known that prices which competitively balance supply and demand correspond to elements in the core. The nucleolus, lying in the lexicographic center of the nonempty core, has the additional property that it satisfies each coalition as much as possible. The corresponding prices favor neither the sellers nor the buyers, hence provide some stability for the market.
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.
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.