Computing the (pre)Nucleolus of general cooperative games Seminar

Event details

Cooperative game theory models various types of cooperation, often considering certain fair or stable division problems. The Nucleolus is one of the most widely known and studied solution concepts in the field, it is desirable due to its numerous attractive properties (such as existence and uniqueness, among many others). However, computing it requires finding a payoff lexicographically minimising ordered vectors of exponential lengths, which is an immensely challenging task, even for relatively small (starting from n~25 players) general games and many classes of structured games. The most frequently used formulation of the problem involves solving a sequence of at most n-1 linear programs of size O(2^n)*(n+1). We present a new algorithm for finding the (pre)Nucleolus of general cooperative games, based on duality and balancedness considerations of tight (active) sets of coalitions. This new approach benefits from the lack of necessity to formulate large linear programs, solving these LPs by focusing on much smaller systems.