Tutte Colloquium - Jochen Koenemann

Title: Matching Games: From Bargaining to the Nucleolus

Abstract:

Cooperative matching games were first introduced in seminal work by Shapley and Shubik in their classic 1971 paper. In this talk, I will first review some of the key concepts and results in this area. I will then use these tools to (re-)derive several facts and algorithms for network generalizations of the famous Nash bargaining concept.
The second part of this talk focuses on a specific solution concept for matching games: the so called nucleolus. I will report on recent joint work with K. Pashkovich and J. Toth, and show that the nucleolus of a weighted matching game instance can be computed in polynomial time, resolving a long-standing open question by Kern & Paulusma.

Joint work with K. Pashkovich and J. Toth