Tata Institute of Fundamental Research
An Algorithm for Locating the Nucleolus of Assignment Games
Seminar
Speaker:
Professor 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:
Monday, 6 Jan 2014, 16:00 to 17:00
Venue:
AG-80
(Scan to add to calendar)
Abstract:
Abstract: In cooperative game theory, Shapley value and the nucleolus are two fundamental solution concepts. They associate a unique imputation for the players whose coalitional worth $s$ are given a priori.
Assignment games are two sided matching games (say between sellers and buyers) where the coalitional worths between a buyer and seller are specified by a nonnegative matrix. (Here, the rows of the matrix represent sellers and the columns of the matrix represent buyers). While an optimal assignment correspond to best deal, for real estate agent eyeing on commissions from both sellers and buyers, he can always initiate an imputation from the core , via the dual optimal solutions. The algorithm at the end of the first iteration reaches the unique corner that favors all sellers. Nucleolus is invariably a relative interior point of the core and the algorithm at each iteration always selects the this most favorable imputation for all sellers in a shrinking family of imputation polytopes. Here the shrinking process correspond to the faces of the polytope moving inside at varying speeds. We can associate with each face of the current polytope, the so called unsettled coalitions that clamor for greater satisfaction for its members. Improvements correspond to redistributions captured through the notion of squeezing the faces of the polytope by applying different levels of pressure and reducing the dimension of the current subset of the imputation set. The algorithm terminates when this squeezing process terminates in a single point. The determination of applying such varied pressures is achieved through the longest path ending at each vertex of an associated graph. The algorithm starts with just a set of vertices of a graph with no arcs to start with. In each intermediate stage, 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 equivalent and are shrunk to just one representative vertex. This way, at the end of an iteration, the number of vertices of the graph are reduced at least by one. New directed arcs are introduced in the next iteration and this process continues till just one vertex survives. The algorithm terminates at this stage and the associated imputation is the nucleolus. The algorithm exploits the special lattice structure of the core for assignment games and all computations involve only dealing with the small class of buyer seller pairs.
Many other subclasses of cooperative games like the connected games and some subclass of permutation games have similar algorithms for locating the nucleolus. As for locating the Shapley value, the problems are wide open.
| Speaker: | Professor 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: | Monday, 6 Jan 2014, 16:00 to 17:00 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
Abstract: In cooperative game theory, Shapley value and the nucleolus are two fundamental solution concepts. They associate a unique imputation for the players whose coalitional worth $s$ are given a priori.
Assignment games are two sided matching games (say between sellers and buyers) where the coalitional worths between a buyer and seller are specified by a nonnegative matrix. (Here, the rows of the matrix represent sellers and the columns of the matrix represent buyers). While an optimal assignment correspond to best deal, for real estate agent eyeing on commissions from both sellers and buyers, he can always initiate an imputation from the core , via the dual optimal solutions. The algorithm at the end of the first iteration reaches the unique corner that favors all sellers. Nucleolus is invariably a relative interior point of the core and the algorithm at each iteration always selects the this most favorable imputation for all sellers in a shrinking family of imputation polytopes. Here the shrinking process correspond to the faces of the polytope moving inside at varying speeds. We can associate with each face of the current polytope, the so called unsettled coalitions that clamor for greater satisfaction for its members. Improvements correspond to redistributions captured through the notion of squeezing the faces of the polytope by applying different levels of pressure and reducing the dimension of the current subset of the imputation set. The algorithm terminates when this squeezing process terminates in a single point. The determination of applying such varied pressures is achieved through the longest path ending at each vertex of an associated graph. The algorithm starts with just a set of vertices of a graph with no arcs to start with. In each intermediate stage, 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 equivalent and are shrunk to just one representative vertex. This way, at the end of an iteration, the number of vertices of the graph are reduced at least by one. New directed arcs are introduced in the next iteration and this process continues till just one vertex survives. The algorithm terminates at this stage and the associated imputation is the nucleolus. The algorithm exploits the special lattice structure of the core for assignment games and all computations involve only dealing with the small class of buyer seller pairs.
Many other subclasses of cooperative games like the connected games and some subclass of permutation games have similar algorithms for locating the nucleolus. As for locating the Shapley value, the problems are wide open.
Assignment games are two sided matching games (say between sellers and buyers) where the coalitional worths between a buyer and seller are specified by a nonnegative matrix. (Here, the rows of the matrix represent sellers and the columns of the matrix represent buyers). While an optimal assignment correspond to best deal, for real estate agent eyeing on commissions from both sellers and buyers, he can always initiate an imputation from the core , via the dual optimal solutions. The algorithm at the end of the first iteration reaches the unique corner that favors all sellers. Nucleolus is invariably a relative interior point of the core and the algorithm at each iteration always selects the this most favorable imputation for all sellers in a shrinking family of imputation polytopes. Here the shrinking process correspond to the faces of the polytope moving inside at varying speeds. We can associate with each face of the current polytope, the so called unsettled coalitions that clamor for greater satisfaction for its members. Improvements correspond to redistributions captured through the notion of squeezing the faces of the polytope by applying different levels of pressure and reducing the dimension of the current subset of the imputation set. The algorithm terminates when this squeezing process terminates in a single point. The determination of applying such varied pressures is achieved through the longest path ending at each vertex of an associated graph. The algorithm starts with just a set of vertices of a graph with no arcs to start with. In each intermediate stage, 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 equivalent and are shrunk to just one representative vertex. This way, at the end of an iteration, the number of vertices of the graph are reduced at least by one. New directed arcs are introduced in the next iteration and this process continues till just one vertex survives. The algorithm terminates at this stage and the associated imputation is the nucleolus. The algorithm exploits the special lattice structure of the core for assignment games and all computations involve only dealing with the small class of buyer seller pairs.
Many other subclasses of cooperative games like the connected games and some subclass of permutation games have similar algorithms for locating the nucleolus. As for locating the Shapley value, the problems are wide open.