Kempten Autumn Talks
Title of the lecture
“Computing the nucleolus of cooperative games: lexicographical optimisation with LPs”
Dr. Marton Benedek
Time of the lecture
November 11, 2020, 13:45 o’clock ETC
90 minutes (including discussion)
After introducing the basic notions of cooperative games (with transferable utilities) the talk focuses on the computation of one of the most widely spread solution concepts, the nucleolus. The solution has attractive properties, as it exists under very mild assumptions, it is unique, and in many aspects it offers the most stable outcome of the game. However, computationally it comes with many challenges, as it involves lexicographically minimising a vector of exponential size in the number of players. Among the various formulations, we are focusing on solving the lexicographical optimisation problem with a sequence of linear programs (LPs): both from a primal and from a dual perspective, focusing on the major tasks along the way, offering possible solutions for them, and highlighting the possible computational trade-offs that one could encounter.