Computing solutions for matching games

Biró, Péter and Kern, W. and Paulusma, D. (2012) Computing solutions for matching games. INTERNATIONAL JOURNAL OF GAME THEORY, 41 (1). pp. 75-90. ISSN 0020-7276

Preview

Text BKP2012ijgt_last.pdf Download (679kB) | Preview

Abstract

A matching game is a cooperative game ( N; v ) de�ned on a graph G = ( N; E ) with an edge weighting w : E ! R + . The player set is N and the value of a coalition S � N is de�ned as the maximum weight of a matching in the subgraph induced by S . First we present an O ( nm + n 2 log n ) algorithm that tests if the core of a matching game de- �ned on a weighted graph with n vertices and m edges is nonempty and that computes a core member if the core is nonempty. This algorithm im- proves previous work based on the ellipsoid method and can also be used to compute stable solutions for instances of the stable roommates prob- lem with payments. Second we show that the nucleolus of an n -player matching game with a nonempty core can be computed in O ( n 4 ) time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we prove that is NP -hard to determine an impu- tation with minimum number of blocking pairs, even for matching games with unit edge weights, whereas the problem of determining an imputa- tion with minimum total blocking value is shown to be polynomial-time solvable for general matching games.

Actions (login required)

Edit Item