|
2.00 pm, Seminar Hall An algorithm to compute the nucleolus of binary assignment games T.E.S. Raghavan University of Illinois at Chicago. 08-03-17 Abstract Suppose "n" boys and "n" girls are to find suitable mates of opposite sex from among them. Each boy could indicate his acceptable set of girls among them. Similarly each girl can indicate her acceptable set of boys among them. Suppose we are able to find full matching, with say boy "k" acceptable to girl "k", and vice versa k=1, 2,... n. The main question is to determine the dominating persons between the matched pairs. It is possible to convert this problem into a cooperative TU game and use either the Shapley value or the nucleolus of this game as a measure of the relative strengths of the person within a matched pair. While the Shapley value has an explicit formula, it is hopelessly difficult to compute it even for these simpler class of TU games. In fact nucleolus is more amenable and we can exploit an alternative characterization of the nucleolus as the lexicographic geometric center as found by Maschler, Peleg and Shapley. While Solymosi and Raghavan gave an algorithm exploiting MPS theorem for the general assignment games, for binary assignment games one can straight away start with the southwest corner core element and one is able to search for the longest path with an associated graph and settle down the relative strengths of mates represented by vertices of the graph along this path. Unlike the algorithm of Solymosi and Raghavan, here Hardwick works on the same digraph by removing all edges whose end vertices are settled (we know their nucleolus values for the individual members of the pairs). In many Western societies, same sex marriage is becoming a more acceptable mate system and this leads to the problem of measuring the relative strength of mates who are part of the maximal matching on a general graph. While Kuhns Hungarian algorithm locates the maximal matching in the bipartite case, Edmunds blossom algorithm and Berge-Tuttes theorem on the number of odd components of a graph and the minmax connection is used to split the graph into components containing blossoms and the determination of the nucleolus which works with such a split and via coloring algorithm.
|
