Weighted nucleoli and dually essential coalitions (extended version) - Tamás Solymosi (Hungarian Academy of Sciences, Institute of Economics, 2019)
We study linearly weighted versions of the least core and the (pre)nucleolus and investigatethe reduction possibilities in their computation. We slightly extend some well-known related results and establish their counterparts by using the dual game. Our main results imply, for example, that if the core of the game is not empty, all dually inessential coalitions (which can be weakly minorized by a partition in the dual game) can be ignored when we compute the per-capita least core and the per-capita (pre)nucleolus from the dual game. This could lead to the design of polynomial time algorithms for the per-capita (and other monotone nondecreasingly weighted versions of the) least core and the (pre)nucleolus in specific classes of balanced games with polynomial many dually essential coalitions.
Keywords: C71; 330; nucleolus; least core; weighted nucleoli; efficient computation; cooperative game