Graphical Algorithms for Finding the Nucleolus of Binary-Valued Matching Games

In cooperative game theory, the class of assignment games models a hypothetical market with two groups of people (for instance, buyers and sellers, or men and women). When a player from one group pairs up with a player from the other group, they receive a payoff, which is specified for each potential pair. The players work together to maximize the total payoff for the market. But then the real problem arises, which is how to split that payoff amongst everyone. One popular solution for cooperative games, and especially for assignment games, is the nucleolus. This is a way of splitting the payoff which maximizes everyone's satisfaction, and minimizes possible incentive for deviating from the group. In this thesis, we expand upon previous work by Solymosi and Raghavan, which gives an algorithm for calculating the nucleolus of assignment games. We focus on a special case, in which all pairs' payoffs are either 0 or 1. This can be interpreted as a measure of compatibility for the pair, and the way each pair splits their payoff can be viewed as their balance of power. In this special case, the previous algorithm can be recontextualized and streamlined using purely graphical methods. We also provide an algorithm for a more general class of games, called matching games. These are defined similarly to assignment games, but without the restriction that the market must be bipartite. This gives us deeper insight into societal applications: for instance, the matching game can be used to model a marriage market in our modern society, while the assignment game would only apply to societies where same-sex marriage is not allowed.