Statistics and Data Science Seminar
John Hardwick / Brian Powers
UIC
A Graphical Algorithm for the Nucleolus of Binary Assignment Games / Multivariate Final-Offer Arbitration
Abstract: (Hardwick) An assignment game is a cooperative game with its player set divided into
two groups, where a coalition receives a positive payoff if and only if it
contains at least one player from both groups. In other words, it concerns
a bipartite matching, with a payoff defined for each pair (payoffs for
larger coalitions are determined additively). The 1994 paper by Solymosi
and Raghavan gives an algorithm for finding the nucleolus (an optimal
solution) of such a game, requiring O(n4) operations (assuming that n is
the size of both groups). In this paper, we examine the special case in
which the payoffs for each pair take only binary values, which we can
think of as an indicator of whether or not the pair is compatible. For
this case, we present a new algorithm which capitalizes on the graphical
aspect of the previous one. This algorithm is shown to be an improvement,
requiring only O(n3) operations. We also discuss sociological implications
of this solution, considering each pair’s split of the payoff to be their
relationship’s balance of power.
(Powers) Final-Offer Arbitration is used in major league baseball to determine
players' salaries, and has been used in various other wage disputes. In
Final-Offer Arbitration, two contesting parties each provide a mediator
with a final offer. The mediator must choose one of the two offers with no
option for compromise. Under certain conditions, Nash equilibria are known
for the single-variable case. Here we will explore solution points when
players have multiple components to their offer, effectively bringing the
dimension of the game to 2 or higher.
Wednesday April 22, 2015 at 4:00 PM in SEO 636