Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


Durham Research Online
You are in:

On solution concepts for matching games.

Biro, P. and Kern, W. and Paulusma, Daniel (2010) 'On solution concepts for matching games.', in Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings. Berlin ; Heidelberg: Springer, pp. 211-221. Lecture notes in computer science. (6108).

Abstract

A matching game is a cooperative game (N,v) defined on a graph G = (N,E) with an edge weighting . The player set is N and the value of a coalition S ⊆ N is defined as the maximum weight of a matching in the subgraph induced by S. First we present an O(nm + n 2logn) algorithm that tests if the core of a matching game defined on a weighted graph with n vertices and m edges is nonempty and that computes a core allocation if the core is nonempty. This improves previous work based on the ellipsoid method. Second we show that the nucleolus of an n-player matching game with nonempty core can be computed in O(n 4) time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we show that determining an imputation with minimum number of blocking pairs is an NP-hard problem, even for matching games with unit edge weights.

Item Type:Book chapter
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1007/978-3-642-13562-0_12
Record Created:07 Oct 2010 11:50
Last Modified:03 Apr 2013 16:17

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library